防走失，電梯直達
安全島
報人劉亞
東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) = 1
f(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的另一半。（約瑟夫環的簡化版本）
結語
人類對數學的探究可以追溯到古代文明時期。從古至今，數學在人類文明開發中扮演了重要角色，不僅在科學、技術、經濟等領域發揮著基礎性作用，還在哲學和藝術等方面產生了深遠影響。
不由得讓我們感嘆，春晚的魔術中都蘊含著古人深刻的數學思想，難怪平時的我學起數學來迷迷糊糊，看魔術時候的我也汗流浹背(小尼臉)
