约瑟夫环问题(Josephus problem)是一个古老而经典的数学问题。问题的场景通常是有n个人(编号从1到n)站在一个圆形排列的位置上。接下来,从第一个人开始,每隔k个人就删除一个人,然后重新开始数,直到所有人都被删除。问题的目标是确定最后剩下的那个人的编号。
具体来说,约瑟夫环问题可以用递归的方式来解决。解决问题的一种方法是使用数学推导,而另一种方法是使用模拟或递归算法。
这个问题的应用涉及到许多领域,包括计算机科学、组合数学和编程等。
假设有2张牌,编号分别是1和2。
首先将1放到后面,扔掉2。剩下的就是最开始放在最上边的那张1。
比如有8张牌,编号分别是1、2、3、4、5、6、7、8。
第一轮会把2、4、6、8扔掉,剩下1、3、5、7按顺序放在后面,又退化成了4张牌的情况。
第二轮会把3、7扔掉,剩下1、5按顺序放在后面,又退化成了2张牌的情况。
第三轮把5扔掉,剩下1,就是最初在最前面的那张。
结论:如果牌的张数是2^n,最后剩下的一定是最开始放在牌堆顶的那张。
比如牌的张数是11,等于8+3。把1放到后面,把2扔掉,把3放到后面,把4扔掉,把5放到后面,把6扔掉,现在剩下的编号序列是7、8、9、10、11、1、3、5,这又是8张牌的情况!最后一定剩下的是现在牌堆顶的7!
因此,只要提前知道牌的张数,就一定能马上推导出最终是剩下哪一张牌。一切的魔法都是数学!!都是算法!!
下面是完整的 JavaScript 代码实现:
// 定义一个函数,用于把牌堆顶n张牌移动到末尾
function moveCardBack(n, arr) {
// 循环n次,把队列第一张牌放到队列末尾
for (let i = 0; i < n; i++) {
const moveCard = arr.shift(); // 弹出队头元素,即第一张牌
arr.push(moveCard); // 把原队头元素插入到序列末尾
}
return arr;
}
// 定义一个函数,用于把牌堆顶n张牌移动到中间的任意位置
function moveCardMiddleRandom(n, arr) {
// 插入在arr中的的位置,随机生成一个idx
// 这个位置必须是在n+1到arr.length-1之间
const idx = Math.floor(Math.random() * (arr.length - n - 1)) + n + 1;
// 执行插入操作
const newArr = arr.slice(n, idx).concat(arr.slice(0, n)).concat(arr.slice(idx));
return newArr;
}
// 步骤1:初始化8张牌,假设为"ABCDABCD"
let arr = ["A", "B", "C", "D", "A", "B", "C", "D"];
console.log("步骤1:拿出4张牌,对折撕成8张,按顺序叠放。");
console.log("此时序列为:" + arr.join('') + "\n---");
// 步骤2(无关步骤):名字长度随机选取,这里取2到5(其实任意整数都行)
const nameLen = Math.floor(Math.random() * 4) + 2;
// 把nameLen张牌移动到序列末尾
arr = moveCardBack(nameLen, arr);
console.log(`步骤2:随机选取名字长度为${nameLen},把第1张牌放到末尾,操作${nameLen}次。`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤3(关键步骤):把牌堆顶三张放到中间任意位置
arr = moveCardMiddleRandom(3, arr);
console.log(`步骤3:把牌堆顶3张放到中间的随机位置。`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤4(关键步骤):把最顶上的牌拿走
const restCard = arr.shift(); // 弹出队头元素
console.log(`步骤4:把最顶上的牌拿走,放在一边。`);
console.log(`拿走的牌为:${restCard}`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤5(无关步骤):根据南方人/北方人/不确定,把顶上的1/2/3张牌插入到中间任意位置
// 随机选择1、2、3中的任意一个数字
const moveNum = Math.floor(Math.random() * 3) + 1;
arr = moveCardMiddleRandom(moveNum, arr);
console.log(`步骤5:我${moveNum === 1 ? '是南方人' : moveNum === 2 ? '是北方人' : '不确定自己是哪里人'},\
把${moveNum}张牌插入到中间的随机位置。`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤6(关键步骤):根据性别男或女,移除牌堆顶的1或2张牌
const maleNum = Math.floor(Math.random() * 2) + 1; // 随机选择1或2
for (let i = 0; i < maleNum; i++) { // 循环maleNum次,移除牌堆顶的牌
arr.shift();
}
console.log(`步骤6:我是${maleNum === 1 ? '男' : '女'}生,移除牌堆顶的${maleNum}张牌。`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤7(关键步骤):把顶部的牌移动到末尾,执行7次
arr = moveCardBack(7, arr);
console.log(`步骤7:把顶部的牌移动到末尾,执行7次`);
console.log(`此时序列为:${arr.join('')}\n---`);
// 步骤8(关键步骤):执行约瑟夫环过程。把牌堆顶一张牌放到末尾,再移除一张牌,直到只剩下一张牌。
console.log(`步骤8:把牌堆顶一张牌放到末尾,再移除一张牌,直到只剩下一张牌。`);
while (arr.length > 1) {
const luck = arr.shift(); // 好运留下来
arr.push(luck);
console.log(`好运留下来:${luck}\t\t此时序列为:${arr.join('')}`);
const sadness = arr.shift(); // 烦恼都丢掉
console.log(`烦恼都丢掉:${sadness}\t\t此时序列为:${arr.join('')}`);
}
console.log(`---\n最终结果:剩下的牌为${arr[0]},步骤4中留下来的牌也是${restCard}`);
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。