劉謙春晚魔術揭祕：約瑟夫環的數學魅力，JS 實現下！

今年春晚劉謙的魔術堪稱驚豔全場，那麼他這個魔術實現的原理是什麼呢？今天，就讓咱們使用 JS 是實現這個魔術。

約瑟夫環問題簡介

約瑟夫環問題源自古羅馬，由歷史學家約瑟夫斯提出，而其數學模型則在 19 世紀被命名。問題設定如下：n 個人圍成一圈，從第一人開始報數，每報到第 k 個人，該人就會被淘汰。遊戲繼續進行，直到最後只剩下一個人。我們的目標是找出這個倖存者的編號。

用撲克牌解讀約瑟夫環

情景一：最簡單的情況

設想我們有兩張牌，編號爲 1 和 2。我們先將 1 號放到底部，然後移除 2 號。結果，最初位於頂部的 1 號牌倖存下來。

情景二：牌數爲 2 的 n 次冪

設想有 8 張牌，編號從 1 到 8。在第一輪中，我們會移除所有偶數編號的牌（2、4、6、8），剩餘 1、3、5、7。這些剩下的牌按順序放到底部，問題就變成了 4 張牌的情況。

重複這個過程，最終我們發現，如果牌數是 2^n 張，倖存的總是最初位於頂部的那張牌。

情景三：任意數量的牌

對於任意數量的牌（比如 11 張），我們可以將其表示爲 2^n+m（在這個例子中是 8+3）。通過重複上述過程，我們會發現最終倖存的牌是最初位於頂部第 m+1 位的牌（在這個例子中是 7 號牌）

見證奇蹟的時刻！

  1. 從 4 張牌開始，對摺撕成 8 張排成 ABCDABCD。

  2. 根據名字長度將頂部牌放到底部，位置變化不影響結果。譬如 2 次，最後變成 CDABCDAB；譬如 3 次，最後換成 DABCDABC。但無論怎麼操作，第 4 張和第 8 張牌都是一樣的。

  3. 將頂部 3 張牌隨意插入中間，確保第 1 張和第 8 張牌相同。這一步非常重要！因爲操作完之後必然出現第 1 張和第 8 張牌是一樣的！以名字兩個字爲例，可以寫成 BxxxxxxB（這裏的 x 是其他和 B 不同的牌）。

  4. 拿掉頂上的牌放到一邊，記爲 B。剩下的序列是 xxxxxxB，一共 7 張牌。

  5. 南方人 / 北方人 / 不確定，分別拿頂上的 1/2/3 張牌插到中間，但是不會改變剩下 7 張牌是 xxxxxxB 的結果。

  6. 男生拿掉 1 張，女生拿掉 2 張。也就是男生剩下 6 張，女生剩下 5 張。分別是 xxxxxB 和 xxxxB。

  7. 循環 7 次，把最頂上的放到最底下，男生和女生分別會是 xxxxBx 和 xxBxx。

  8. 最後執行約瑟夫環過程！操作到最後只剩下 1 張。當牌數爲 6 時（男生），剩下的就是第 5 張牌；當牌數爲 5 時（女生），剩下的就是第 3 張牌。Bingo！就是第 4 步拿掉的那張牌！

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

通過上述代碼，我們可以模擬劉謙春晚魔術的整個過程，並驗證其背後的數學邏輯。

以下爲執行結果：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/1jz1TTbEj6y7QiZyWJlaZA

猜你喜歡