昨日看韩顺平的 Linux 视频,里面提到一个丢手帕问题,也叫 约瑟夫问题,觉得很有趣,今天上班早到了会儿,用自己的思路解决了下,先记录如下:

问题描述:

  • n 个人围成一个圆圈,编号 1,2,3,… n
  • 从编号为 m(m>=1 && m<=n) 的人开始报数(报数从 1 开始报)
  • 报数报到 k 的那个人就自杀,然后从下一个人继续游戏,继续从1开始报,到下一个报到 k 的人再自杀,依次循环,直到最后一个人活下来,
  • 给定n,m,k 求最后活下来的是谁?

JS 的一种实现方案

  • 我的思路是从最开始报数那个人开始 , 其索引自加1 加k-1次(期间判断如果索引大于了数组length-1 就置0),每次循环删掉数组中的一个元素 这样直到数组剩下最后一个元素,就是最后活下来的人
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function throwHandkerchief(n,m,k) {
//n----一共多少个人围成一圈
//m----从第几个人(索引就是m-1)开始数数 m>=1 && m<=5
//k----数到几(往下走k-1个人) 的人退出
let arr = [];//表示所有人的数组
for (var i=0;i<n;i++) {
arr.push(i+1);
}
let sIndex = m - 1;//最初的报数人的索引
while(arr.length>=2) {
for (let j=0;j<k-1;j++) {
sIndex++;
sIndex = sIndex > (arr.length -1) ? 0 : sIndex;
}
arr.splice(sIndex,1);
sIndex = sIndex > (arr.length -1) ? 0 : sIndex;
}
return arr[0];
}
console.log(throwHandkerchief(8,4,3));