4667 积分	0 好友	645 主题

发消息

JavaScript实现约瑟夫环算法，深度解析刘谦春晚扑克牌魔术原理

发表于 3 天前 | 查看: 22| 回复: 0

今年春晚刘谦的魔术表演吸引了众多观众的目光，大家是否好奇其背后的原理呢？今天，我们将从编程的角度出发，使用 JavaScript 来完整复现这个魔术，并揭示其核心数学逻辑——约瑟夫环问题。

约瑟夫环问题简介

约瑟夫环问题是一个经典的数学与计算机科学问题。它描述了这样一个场景：n个人围成一圈，从第一个人开始报数，每数到第k个人就将其淘汰。如此循环，直到最后只剩下一个人。我们的目标是找出这个幸存者的位置。

用扑克牌模拟约瑟夫环

为了让理论更直观，我们用扑克牌来类比。

情景一：最简单的情况
假设有两张牌，编号为1和2。先将1号牌移到底部，然后移除顶部的2号牌。最终，最初位于顶部的1号牌成为了幸存者。

情景二：牌数为2的n次幂
假设有8张牌（2^3）。在第一轮中，所有偶数编号的牌（2, 4, 6, 8）会被移除，剩下1, 3, 5, 7。这个过程可以重复，最终你会发现，如果牌数恰好是2^n，那么幸存者总是最开始位于顶部的那张牌。

情景三：任意数量的牌
对于任意数量（例如11张）的牌，我们可以将其表示为 2^n + m（这里8+3）。通过模拟淘汰过程可以证明，最终的幸存者是最初位于队列中第 m+1 位的牌。

魔术步骤与原理揭秘

刘谦的魔术正是巧妙地运用了上述原理。让我们结合代码，一步步拆解：

初始状态：4张牌对折撕开，变成8张，排列为 ABCDABCD。注意，此时第1张（A）和第5张（A）相同，第4张（D）和第8张（D）相同。
按名字长度移动：根据名字字数（假设为k），将前k张牌依次移动到末尾。这个操作不会改变牌的相对循环顺序，第1张和第8张牌依然保持相同。
插入关键牌：将顶部3张牌随机插入中间。这一步是魔术的“障眼法”和“关键设置”。无论怎么插入，最终序列的首尾两张牌必定相同。假设序列变为 BxxxxxxB。
藏起一张牌：拿走最顶上的牌（记为B）放在一边。此时剩余序列为 xxxxxxB，共7张牌。
地域选择：根据南方人/北方人/不确定，分别将顶部1/2/3张牌插入中间。这一步不会改变剩余序列末尾的牌B。
性别选择：男生移除1张牌，剩余6张（xxxxxB）；女生移除2张，剩余5张（xxxxB）。注意末尾的牌B依然未被触动。
“七”次循环：将顶部牌移动到底部，执行7次。这个操作是为了调整牌序，为最终的约瑟夫环淘汰做准备。经过操作，序列会变成xxxxBx（男）或xxBxx（女）。
约瑟夫环淘汰：执行“好运留下来，烦恼丢出去”的淘汰规则（即经典的约瑟夫环过程，k=2）。你会发现，无论最初剩下5张还是6张牌，最后幸存下来的那张牌，一定就是第4步我们藏起来的那张B！

下面是完整的 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}`);

运行上述代码后，你会在控制台看到每一步的操作和序列变化，最终验证剩下的牌与之前藏起的牌完全一致。

魔术步骤与序列变化示意图