js解决约瑟夫问题

// 用数组的方式解决
function getLastNum(n,m) {
	if(n <= 1 || m < 1) return;
	let arr = new Array(n).fill(1);
	let count = 0 ; // 记录出圈人数
	let num = 0; // 报时器

	while(count < n -1) {
		for(let i = 0; i < arr.length; i++) {
			if(arr[i] === 1) {
			    num++;
			　　if(num === m) {// 当遇到相同的那个时出局，
				// 并将该值标记为0 表示已出局，同时出局人数加1 报数重新初始化
				arr[i] = 0;
				count++;
				num = 0;
			  }
		     }
		}
		if(count === n -1) {
			break;
		}
	}
	let lastNum 
	for(let i = 0; i < arr.length;i++) {
		if(arr[i] === 1) {
			lastNum = i + 1;
			break
		}
	}
	return lastNum;
}

　注：　传说罗马人占领了乔塔帕特，41 个犹太人被围堵在一个山洞里。他们拒绝被俘虏，而决定集体自杀，大家决定了一个自杀方案，41 个人围成一个圈，由第 1 个人开始顺时针报数，每报数为 3 的人立刻自杀，然后再由下一个人重新从 1 开始报数，依旧是每报数为 3 的人立刻自杀，依次循环下去。其中两位犹太人并不想自杀，是数学家约瑟夫和他的朋友，他们发现了自杀方案的规律，选了两个特定的位置，最后只剩下他们两人，而活了下来。那么这两个位置分别是什么？

// 使用递归方式实现
/*
n 个人，只要有一个人出局，就变成了n-1个人，此时要处理的问题就是n-1个
依次类推，要处理的就是n=2 的问题，当n= 1 时，游戏结束
用一个方法来表示就是f(2,m)
然后要找f(3,m)和f(2,m)的对应关系，准确的说是f(n,m)和f(n-1,m)的关系

*/

/*当n = 5,m = 2;
0 1 2 3 4 从0开始 1是第一个出局的
0 2 3 4 出局的第一个数

2 3 4 0 （*）上面可以写成这样，因为是从2开始的
0 1 2 3 （**）n= 4 ，m= 2，是接下来要处理的事
0 2 3 出局的第二个数
比较（*）和（**）的规律 （（**）+ 2）% 5 这可转化为（*）注： * 代表出局的数

上面的可以写成下面这样 ，因为是从2开始的
2 3 0 （*）
0 1 2 （**）
（（**）+ 2）% 4 
*/


function getLastPerson(n,m) {
　　let r = 0;
　　for(let i = 2; i <= n; i++) {
  　　r = (r + m )% i;
   }

　　return r + 1;
}