思路

約瑟夫環(huán)問(wèn)題 ：
題目是 假設(shè)有N個(gè)小朋友按順序圍成一圈，每個(gè)小朋友都有一個(gè)編號(hào)愧口，假設(shè)從第m個(gè)小朋友從1開(kāi)始報(bào)數(shù)局义，報(bào)到k的小朋友出圈，從出圈的下一個(gè)小朋友繼續(xù)報(bào)數(shù)当窗，重復(fù)上面的報(bào)數(shù)够坐。直到所有的人出圈位置。
求出圈的小朋友的順序是什么

解決方案：
我們使用的是單向的環(huán)形鏈表作為數(shù)據(jù)結(jié)構(gòu)
思路大致分為

1. 尋找指定開(kāi)始節(jié)點(diǎn)
2. 跳動(dòng)指定的步長(zhǎng)-1（需要獲取彈出節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)崖面，才可以做刪除）
3. 顯示彈出節(jié)點(diǎn)

代碼

package com.xipenhui.cn

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._

/**
 * 約瑟夫環(huán)問(wèn)題 ：
 * 題目是  假設(shè)有N個(gè)小朋友按順序圍成一圈元咙，每個(gè)小朋友都有一個(gè)編號(hào)，假設(shè)從第m個(gè)小朋友從1開(kāi)始報(bào)數(shù)
 * 報(bào)到k的小朋友出圈巫员，從出圈的下一個(gè)小朋友繼續(xù)報(bào)數(shù)庶香，重復(fù)上面的報(bào)數(shù)。直到所有的人出圈位置疏遏。求出圈
 * 的小朋友的順序是什么
 * 解決方案：
 *   我們使用的是單向的環(huán)形鏈表作為數(shù)據(jù)結(jié)構(gòu)
 */
object JosephuDemo {
  def main(args: Array[String]): Unit = {

    val josephu = new Josephu()
    val boys = josephu.addBoy(5)
    println("=======創(chuàng)建出來(lái)的boys是=======")
    josephu.show()
    println("===彈出小朋友===")
    josephu.popBoy(2,3,5)
  }
}

/**
 * 環(huán)形單向鏈表
 * 1. 添加小孩子
 * 2. 按照規(guī)則彈出小孩子
 * 3. 顯示環(huán)形隊(duì)列的值脉课，做過(guò)程校驗(yàn)
 */
class Josephu {
  var head = Boy(-1)

  /**
   *
   * @param num 添加小孩的個(gè)數(shù)
   */
  def addBoy(num: Int) {

    //參數(shù)校驗(yàn)
    if (num < 1) {
      throw new RuntimeException("input num must big than 1")
    }

    var currBoy: Boy = null
    for (i <- 1 to num) {
      val boy = new Boy(i)
      if (i == 1) {
        head = boy
        head.next = head
        currBoy = boy
      } else {
        currBoy.next = boy
        boy.next = head
        currBoy = boy
      }
    }
  }


  /**
   * 按照給定的規(guī)律彈出元素
   * 1. 從開(kāi)始數(shù)到第m個(gè)小朋友，拿到當(dāng)前的小朋友
   * 2. 在當(dāng)前節(jié)點(diǎn)進(jìn)行后移财异，移動(dòng)到k個(gè)小朋友的前一個(gè)節(jié)點(diǎn)（單向鏈表刪除需要使用前一個(gè)節(jié)點(diǎn)輔助）
   *   彈出當(dāng)前小朋友倘零，刪除當(dāng)前節(jié)點(diǎn)，
   * 3. 這里可以使用兩個(gè)for循環(huán)戳寸，
   *    第一次循環(huán)的長(zhǎng)度為鏈表長(zhǎng)度
   *    第二次循環(huán)的長(zhǎng)度為移動(dòng)的長(zhǎng)度 k -1 (因?yàn)橐耙粋€(gè)節(jié)點(diǎn))
   *
   * @param startNum 從第num個(gè)位置開(kāi)發(fā)數(shù)數(shù)字
   * @param countNum 數(shù)數(shù)的長(zhǎng)度為len
   * @param len      環(huán)形鏈表的長(zhǎng)度
   */
  def popBoy(startNum: Int, countNum: Int, len: Int): Unit = {
    //val resArr = ArrayBuffer[Boy]
    if (head.next == null || startNum < 1 || startNum > len) {
      println("輸入?yún)?shù)錯(cuò)誤呈驶，請(qǐng)重新輸入")
      System.exit(0)

    }
    var currBoy: Boy = head
    //可以找到起始位置的節(jié)點(diǎn)
    breakable {
      while (currBoy.next != head) {
        if (currBoy.num == startNum) {
          break()
        } else {
          currBoy = currBoy.next
        }
      }
    }
    if (currBoy.next == head) throw new RuntimeException("can not find input element")

    //點(diǎn)名的次數(shù)為 len次
    for (i <- 0 until len) {
      //從currBoy開(kāi)始點(diǎn)名，點(diǎn)名的長(zhǎng)度為countNum,這里是單向鏈表疫鹊，要借助前一個(gè)節(jié)點(diǎn)進(jìn)行刪除
      for (j <- 1 until countNum-1) {
        currBoy = currBoy.next
      }
      //這里 currBoy已經(jīng)移動(dòng)到需要移除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
      print(s"output element is ${currBoy.next.num} \n")
      currBoy.next = currBoy.next.next
      currBoy = currBoy.next
    }
  }

  //顯示當(dāng)前鏈表的內(nèi)容
  def show(): Unit = {
    var currBoy = head
     while (currBoy.next != head){
       println(s"input boy's num is ${currBoy.num}")
       currBoy=currBoy.next
     }
   println(s"input boy's num is ${currBoy.num}")
  }
}

case class Boy(num: Int) {
  var next: Boy = null
}