約瑟夫斯問題，誰知道如何解決約瑟夫斯問題

1 所有主題]：我聽說過乙個古老的傳說，64名戰士被敵人俘虜。

敵人命令他們圍成乙個圓圈，做數字 1、2、3......，64。敵人殺了一號和三號，他們乙個接乙個地殺了，他們繞著圈子轉。 最後，只剩下乙個人，那個人就是約瑟夫斯。

約瑟夫斯的號碼是多少？ （這是“約瑟夫斯”問題。 ）

這個問題的答案相對簡單：敵人從第1個開始，乙個接乙個地殺，第一輪殺掉所有奇數戰士。 剩下的 32 名戰士需要重新編號，敵人在第二圈用重新編號的奇數殺死。

由於第一圈只剩下偶數 2、4、6,...，64。用 2 將它們全部刪除以獲得 1、2、3 ,...，32。這是第二個圓圈的數字。

第二輪過後，所有奇數都被殺了，只剩下16人。 如果再這樣下去，可以想象，最後剩下的一定是64號。

64=26，連續能被2整除6次，是從1到64最多能被2整除的數字，所以最後不可避免地會留下64。

如果俘虜了 65 名戰士，而敵人仍然以上述相同的方式屠殺戰士，那麼約瑟夫斯最終會留下來嗎？

經過計算，很容易得出事實並非如此的結論。 因為第乙個人被殺之後，也就是1號被殺之後，第二個被殺的人必然是3號。 如果排除1號，那麼還剩下64人，新的1號是3號。

這樣，原來的2號就變成了新的64號，所以剩下的一定是2號。

進一步分類，不難發現，如果原本有2k人，最後剩下的人數一定是2k; 如果原來有2k+1人，最後就剩下2人了; 如果有 2k+2 人，則會有 4 ......左如果原版中有 2k+m 人，最後會剩下 2m 人。

例如：原來有 100 人，由於 100 = 64 + 36 = 26 + 36，最後剩下的是 36 2 = 72; 另乙個例子：最初有 111 人，由於 100 = 64 + 47 = 26 + 47，最後剩下的是 47 2 = 94。

當 m 比較小時，可以用筆計算求解，m=2

即n人圍成乙個圓圈，1、2、1、2報數，報2，死，直到只剩下乙個人。

當 n=2 k 時，第乙個報告數字的人是最後乙個死亡的人，對於任何自然數 n 都可以表示為 n=2 k+t，其中 tn mod 3 則最後乙個死亡的人是新一輪的 f（n-[n 3]）-n mod 3） 人。

3.新一輪第k人對應原來的3*[（K-1）2]+（K-1）mod 2+1人。

綜合產量 1,2,3：

f（1）=1， f（2）=2， f（3）=2， f（4）=1， f（5）=4， f（6）=1， 當 f（n-[n 3]）<=n mod 3 k=n-[n 3]+f（n-[n 3]）-n mod 3）， f（n）=3*[（k-1） 2]+（k-1）mod 2+1

當 f（n-[n 3]）>n mod 3， k=f（n-[n 3]）-n mod 3） 時，f（n）=3*[（k-1） 2]+（k-1）mod 2+1

該演算法需要計算 [log（3 2）2009] 次 這個數字不大於 22，可以用筆計算。

所以：第一輪，669人被殺，這個圈子裡最後乙個被殺的人是2007年，還剩下1340人，第二輪，446人被殺，剩下894人。

在第三輪中，有298人被殺，剩下596人。

在第四輪中，有198人被殺，剩下398人。

在第五圈，有132人遇難，剩下266人。

在第六圈，88人被殺，剩下178人。

在第七輪中，有59人被殺，剩下119人。

在第八圈，39人遇難，剩下80人。

在第九圈，有26人被殺，剩下54人。

在第十圈，有18人被殺，剩下36人。

11圈，12人死亡，剩下24人。

十二圈，8人死亡，剩下16人。

13圈，5人死亡，剩下11人。

十四圈，3人死亡，8人離開。

十五圈，2人死亡，6人離開。

f（1）=1， f（2）=2， f（3）=2， f（4）=1， f（5）=4， f（6）=1，然後推回去。

f（8）=7 f（11）=7 f（16）=8 f（24）=11 f（36）=16 f（54）=23 f（80）=31 f（119）=43 f（178）=62 f（266）=89 f（398）=130

f（596）=191 f（894）=286 f（1340）=425 f（2009）=634

-來自。

提圖斯·弗拉维烏斯·約瑟夫斯（公元 37-100 年），也被稱為約瑟夫，在希伯來聖經中被稱為約瑟夫·本·馬蒂亞胡，位於耶路撒冷的猶太省份羅春。

出生於公元一世紀，是一位猶太歷史學家。

代表作有《猶太古代史》等。

和猶太戰爭。 在第一次猶太-羅馬戰爭期間，他擔任猶太叛軍的軍官，投降後，他擔任羅馬**的參謀和翻譯，並被授予羅馬公民身份。

約瑟夫問題是乙個眾所周知的問題：n個人圍成一圈，從第乙個開始數，m將被殺死，最後乙個將被留下，其餘的將被殺死。 例如，n = 6，m = 5，遇難者的序列號為 5、4、6、2、3。

最後，1號仍然存在。

假設圈子裡的前 k 個人是好人，最後 k 個人是壞人，你的任務是確定最小 m，以便在第乙個好人之前殺死所有壞人。

據說，著名的猶太歷史學家約瑟夫斯講過這樣乙個故事：羅馬人占領喬塔帕特後，39個猶太人和約瑟夫斯和他的朋友們躲在乙個洞裡，39個猶太人決定寧願死也不願被敵人抓住，於是他們決定自殺，41人排成一圈， 第乙個人開始數數，每三個人都必須自殺，然後下乙個人繼續數數，直到他們都自殺了。然而，約瑟夫斯和他的朋友們不想服從。

從乙個人開始，越過 k-2 人（因為第乙個人已經被越過），然後殺死第 k 個人。 然後，越過 K-1 並殺死 k-1 人。 這個過程沿著圓圈繼續，直到最終只剩下乙個人，這個人可以繼續活下去。

問題是，鑑於 and，你首先必須站在哪裡才能避免被處決？ 約瑟夫斯讓他的朋友假裝順從，他把他放在第 16 和第 31 位，從而逃脫了死亡遊戲。

17世紀的法國數學家加斯帕爾在《數字遊戲的問題》中講過乙個故事，15個信徒和15個非信徒在海上遇險，其中一半人必須被扔進海浬，剩下的才能活下來，於是他想出了乙個解決方案：30個人圍成乙個圓圈，從第一人稱開始， 每九個人就被扔進海浬，依此類推，直到只剩下 15 個人。

問如何安排律法，讓每次你把自己扔進海浬，你都是不信的。

問題分析和演算法設計。

約瑟夫的問題並不難，但有很多方法可以解決; 該主題也有許多變體。 下面是乙個實現方法。

在問題中，30個人圍成乙個圓圈，這啟發了我們用乙個圓鏈來表示它，我們可以用乙個結構的陣列來形成乙個圓鏈。 結構中有兩個成員，其中乙個是指向下乙個人的指標，形成乙個圓形鏈; 第二個是該人是否被扔到船外的標記，1 表示他仍然在船上。 從第一人稱開始，數一數尚未被扔進海浬的人，每次數到9時，將結構中的標記改為0，表示這個人已經被扔進海浬了。

這個迴圈一直持續到 15 人被扔進海浬。