小孩数数 击鼓传花 约瑟夫环 丢手绢

问题描述

一般经常是以这样的形式出现的：

有30个小孩儿，编号从1-30，围成一圈依此报数，1、2、3 数到 3 的小孩儿退出这个圈， 然后下一个小孩 重新报数 1、2、3，问最后剩下的那个小孩儿的编号是多少?

或者我们可以看到约瑟夫环、击鼓传花、丢手绢
这些问题都是换汤不换药，同属于一类问题

思路分析

初读完题目能够想到什么，从一些关键字眼我们就可以大概推断出可能会用什么。

• 每次都重复123，可能会用到循环
• 当只有一个孩子时停止报数，可能用到while
• 同一个数字可能会数多次

我们可以考虑使用队列的方式去实现

• 每次数完，如果不符合就将它放到队尾
• 将符合条件的删除

可以在本子上画一画具体的过程

核心代码

 while (result.length > 1) {
    for (let i = 1; i < num; i++) {
      result.push(result.shift())
    }
    result.shift()
  }

完整代码

const passGame = (names, num) => {
  let result = [...names]
  while (result.length > 1) {
    for (let i = 1; i < num; i++) {
      result.push(result.shift())
    }
    result.shift()
    // console.log(`${result.shift()}被删除了`)
  }
  //索引是从0开始
  return names.indexOf(result[0]) + 1
}
//生成数字数组，如果其他需要我们可以替换数组内容
let people = []
for (let i = 1; i < 11; i++) {
  people.push(i)
}
console.log(passGame(people, 3))