約瑟夫問題的遞迴解與直接解
一、問題背景
來自一個傳說：
1
世紀著名歷史學家——
以夫拉維約瑟夫
——靠著自己數學天賦存活的故事。
在猶太羅馬戰爭期間，包括約瑟夫在內的
41
個猶太反抗者困在了羅馬人包圍的洞穴之中。他們寧願自殺也不願意被活捉，於是圍城一個圈，並且沿著圓圈每隔
兩個人
殺死一個人，直到剩下兩個人為止。但是，得益於自己的數學天賦，約瑟夫站到了合適的位置，最後活了下來。
那麼他是如何做到的呢？這個問題有什麼快速的解嗎？
二、遞迴解
我們討論這樣一個問題：圍成一圈，每隔一個人刪去一個人，看最後剩誰。
我們先來熟悉一下流程，假設有
10
個人：
那麼消去的順序依次為
2、4、6、8、10（綠色標記）
、
3、7、1（粉紅色標記）
、
9（橙色標記）
，最後剩下
5
。
透過這個消去的過程，得到了什麼？
偶數項一定會被消去，最後結果一定是奇數項。
為什麼？因為第一輪就把偶數項全都消去了。
然後，我們將討論
n
個人的情況。
從直覺來上來看，這個n是奇數或者偶數對結果會有影響。
2。1
n
為偶數
當總數為偶數時，第一輪把偶數項全都刪掉了（圖中綠色標記），剩下的呢？如果仔細觀看和琢磨，會發現過程和第一輪非常類似，只不過
被刪除的數變成了對應的加倍然後減1
。
不難推斷出：
2。2
n
為奇數
當總數為奇數時，第一波把全部偶數項刪去（綠色標記），然後第一項也會被刪除（粉紅色的回憶）。重複的情況又發生了，和第一輪非常類似，
這次從3開始，因此只不過被刪除的資料變成了對應的數加倍然後加1。
因此，我們不難看出：
綜上，我們得出遞迴解
：
三、直接解
當然，這個遞迴解絕對比斐波那契數列的遞迴解“
有效
”的多。關於斐波那契數列的討論，可以參考我的文章
。
比如
J（1000000）
參照上述遞迴解，只要
19
步就能算出結果。時間複雜度約為
，
。
但是，有沒有更直接的解呢，不需要我們遞迴求解。
找規律。
為了找規律，列出前幾項
啊！一眼便能看出這個排列的貓膩：
可以按照2的冪將表中的資料分組（圖中用紅色線段分開），每一組的J值是一個1為首項，2為公差的等差數列。
好的，規律找到了。
重點是如何分組：如果我們將
n
寫成
那麼
。
這就是直接解。
用這個直接解來計算，比如剛才的當為
1000000
時：
一句話總結：學好數理化，走遍天下都不怕！
參考來源
1、具體數學（計算機科學基礎第2版）