防走失，電梯直達
安全島
報人劉亞東A
來源：進步的階梯eacc
作者：辰子進步的階梯
❝
約瑟夫環（約瑟夫問題）的起源可以追溯到公元1世紀，當時有一個名叫約瑟夫的猶太歷史學家。據傳，他和他的同伴被敵人包圍，在面臨絕境時，他們決定寧死不屈，於是決定通過自殺的方式結束生命。為了執行這個決定，他們圍成一個圈，然後按照一定的規則來選擇自殺的人，直到只剩下最後一個人。約瑟夫，作為一個不願意自殺的人，快速地計算出了一個位置，使得他成為了最後一個存活的人，從而有機會逃脫。
數學模型
將這個故事抽象成數學模型，我們得到了約瑟夫環問題：假設有n個人圍成一圈，從某個人開始，按順時針方向逐一編號。接著從編號為1的人開始報數，每數到m就將該人從圈中排除，然後從下一個人重新開始報數，直到圈中只剩下一個人。
比如說，如果有6個人(n = 6)參與遊戲（編號為1到6），選擇的m是3，那麼遊戲進行的過程大概是這樣的：
從編號1的人開始報數，數到3的人是編號3的人，所以編號3的人離開遊戲。
接下來，從編號4的人開始報數，數到3的人是編號6的人，因此編號6的人離開遊戲。
現在，從編號1的人開始報數，數到3的人是編號2的人，所以編號2的人離開遊戲。
然後，從編號4的人開始報數，數到3的人是編號5的人，因此編號5的人離開遊戲。
最後，剩下編號1和編號4的人，從編號1的人開始報數，數到3的人是編號4的人，所以編號4的人離開遊戲。
最終，只剩下編號1的人，他就是遊戲的贏家。
我們用偽代碼解答：
f( n, m){
return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
邏輯
這個函數f接收兩個參數：
n：圈中的人數。
m：報數的數字，每報到這個數字的人就要退出遊戲。
函數
f返回的是最後存活的人的編號，這個編號是基於初始時圈中人的排列順序。假設有n個人圍成一個圈，按順序編號從1到n，並且按照規則每數到第m個人就將其從圈中移除，那麼f(n, m)就會返回在這個過程結束時，即圈中只剩下一個人時，那個人的原始編號。例如，如果有
5個人 (n = 5) 圍成一圈，選擇的m是3，那麼f(5, 3)將計算並返回在這些人按照規則開始報數，每報到3時就有一個人離開圈子，直到最後只剩下一個人時，那個人的編號。
這個函數的計算方法確保了不管 n和m的值如何，它都能準確計算出在這種特定報數規則下最後一個剩餘的人的編號。
這是利用遞歸思想解決問題，讓我們逐步分解這個函數：
基本情況：如果
n == 1，這意味著圈中只剩下一個人，那麼這個人就是贏家，函數返回這個人的編號，即1。這是遞歸的基本結束條件。遞歸步驟：如果
n > 1，則需要進行遞歸調用來縮小問題的規模。
f(n - 1, m) + m - 1：首先，將上一輪的贏家編號（在減少一個人之後的情況）加上m - 1，因為我們從下一個人開始重新計數，直到數到m。% n：然後，對當前人數n取模，這樣可以確保如果數字超過了人數n，它會從頭開始計算。+ 1：最後，加1是因為我們的編號是從1開始的，而非0開始。這樣就能正確映射到從1開始的編號。f(n - 1, m)：首先，函數遞歸調用自身，人數減少一個（因為每一輪遊戲都會有一個人被淘汰），直到只剩一個人，遞歸才會結束。(f(n - 1, m) + m - 1) % n + 1：這部分是計算經過一輪淘汰後，剩餘人員重新編號後的贏家編號。其中：
接下來我們看看具體是怎麼做的：
舉例
開始點：
f(5, 3)
需要計算
f(4, 3), 並將其結果加上3 - 1, 然後對5取模，最後加1。
計算 f(4, 3)
類似地，
f(4, 3)需要計算f(3, 3), 並將其結果加上3 - 1, 對4取模，再加1。
計算 f(3, 3)
f(3, 3)需要計算f(2, 3), 並將其結果加上3 - 1, 對3取模，再加1。
計算 f(2, 3)
f(2, 3)需要計算f(1, 3), 並將其結果加上3 - 1, 對2取模，再加1。
計算 f(1, 3)
當
n = 1,f(1, 3)返回1，因為只剩一個人時，那個人就是贏家。
讓我們反著來看思考過程，這會更容易一點：
回溯過程
f(1, 3) = 1f(2, 3)：將f(1, 3)的結果1加上2（即3 - 1），得到3，然後對2取模得到1，再加1得到2。（這裡說f(2, 3) = 2 ，也就是編號為2的人活了下來，下文同理。）f(3, 3)：將f(2, 3)的結果2加上2（即3 - 1），得到4，然後對3取模得到1，再加1得到2。f(4, 3）：將f(3, 3)的結果2加上2（即3 - 1），得到4，然後對4取模得到0，再加1得到1。f(5, 3)：將f(4, 3)的結果1加上2（即3 - 1），得到3，然後對5取模得到3，再加1得到4。
結果
因此，f(5, 3)的最終結果是4，意味著在有5個人圍成一圈，按照每數到3就讓一個人離開的規則下，最後剩下的是最初編號為4的那個人。
何以遞歸？
約瑟夫環問題如何能成為遞歸演算法的經典案例？結合計算思維，我們進一步探討。
自相似性
遞歸演算法的核心思想是將問題分解成更小的子問題，直到這些子問題足夠小，可以直接解決。約瑟夫環問題本質上具有自相似的結構：每當一個人被淘汰，剩下的人又形成了一個較小的圈，規則不變，這就構成了一個更小規模的約瑟夫環問題。這種自相似性質使得約瑟夫環問題非常適合用遞歸方法來解決。
分而治之
遞歸演算法是分而治之策略的一種體現。在約瑟夫環問題中，通過遞歸調用，我們不斷縮小問題的規模（即每次減少一個人），直到達到一個基本情況（只剩下一個人）。這種方法能夠將一個複雜問題簡化為易於管理和解決的小問題，是計算思維中分解問題的典型例證。
劉謙魔術的把戲
在劉謙的魔術中，約瑟夫問題的核心思想被巧妙地應用於控制過程的結果。約瑟夫問題是通過固定間隔來選擇和排除序列中的對象，直到只剩一個對象。在這個魔術中，儘管沒有直接使用固定間隔的排除方法，但通過一系列精心設計的操作步驟（如牌的摺疊、插入、丟棄等），實現了類似的控制效果，即無論參與者如何執行這些步驟，都會以一種預定的方式減少牌的數量，最終留下一張特定的牌。
讓我們試著逐步分析：
初始狀態是四張不同的牌，標記為A、B、C、D。
撕開後變成兩副牌，順序為ABCDABCD。這意味著每張牌都有一個另一半，形成了兩套完全相同的序列。
接著，規則允許任意數量的牌從前面移動到後面，新的排序用abcdabcd表示，這是說序列可能被重新排列，但仍然是兩個重複的四牌序列。
然後，最前面的三張牌被插入到後面某個位置，導致序列中的兩個d分開，但因為只有這三張牌移動了位置，所以這兩個d之間的其他牌仍然保持原有的相對順序。
移除序列中的第一張牌（d），這不會影響剩餘牌的相對順序。
接下來，將剩下的1、2或3張牌插入到後面的牌中，這可能會改變某些牌的相對順序，但因為操作是有限的，所以這種影響是可控的。
丟棄最上面的一張或兩張牌，這減少牌的數量，但保留了牌的相對位置。
按順序將7張牌移動到最後，這個步驟確保了在完成這些移動後，原來的第一張d牌（已經被移除）的另一半現在在倒數第二的位置。（請讀者證明）
最後，通過交替地放置一張牌到最後和丟棄一張牌，最終剩下一張牌，這張牌是d的另一半。（約瑟夫環的簡化版本）
結語
人類對數學的探究可以追溯到古代文明時期。從古至今，數學在人類文明發展中扮演了重要角色，不僅在科學、技術、經濟等領域發揮著基礎性作用，還在哲學和藝術等方面產生了深遠影響。
不由得讓我們感嘆，春晚的魔術中都蘊含著古人深刻的數學思想，難怪平時的我學起數學來迷迷糊糊，看魔術時候的我也汗流浹背(小尼臉)
