2019-02-15 09:01:43 咱小二

約瑟夫問題由來

據說著名猶太曆史學家 Josephus有過以下的故事:在羅馬人佔領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人抓到，於是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友並不想遵從。首先從一個人開始，越過k-2個人(因為第一個人已經被越過)，並殺掉第k個人。接著，再越過k-1個人，並殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了人數總和，一開始要站在什麼地方才能避免被處決?Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡遊戲。

17世紀的法國數學家加斯帕在《數目的遊戲問題》中講了這樣一個故事:15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其餘的人才能倖免於難，於是想了一個辦法:30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海，如此循環進行，直到僅餘15個人為止。問怎樣的排法，才能使每次投入大海的都是非教徒。

約瑟夫問題算法思想

由於用到四種不同的存儲結構，它們的算法思想依次是：

首先建立一個順序表模擬整個約瑟夫環，手動輸入順序表長（即參加約瑟夫循環的人數）和循環的次數和表元素。用已經輸出總人數和順序表長作比較，作為外層循環條件。並對每一個輸出後的元素重新賦值以為標記。對於每次循環，首先檢查順序表此次是不是我們設立的標記，如果不是則循環次數加1，當達到要求的循環次數時就將循環次數設置為0，輸出該元素到屏幕並將總輸出元素加1。每次外循環我們都會移到表的下一個位置，作為新的判斷條件，每次報到表尾的時候，我們都將重新設置到表尾，作為下次循環的表元素。
首先採用鏈式循環鏈表建立整個約瑟夫環，手動輸入第一次的循環次數和每個人所持下一個循環次數。設立判斷指針指向表頭，並將該指針是否為空作為外層循環條件。做一個內層循環，將判斷指針移動到循環要輸出的數，並設立一個前指針指向該指針的前一個位置，輸出該元素後，將循環次數重新賦值成該元素。接著判斷前指針和判斷指針比較，如果相等說明整個表已經輸出完畢，否則將刪除該位置的元素。
用鏈式隊列建立循環約瑟夫環，手動輸入人數，第一次的循環次數和每個人所持下一個循環次數。並將每一個元素依次加入隊列，根據第一次循環次數，建立一個for循環，每一次循環都能出隊列，如果達到要求的循環次數就輸出，否則進隊列，這樣這個數字就出現在隊尾。第一個數輸出後，以隊列的非空作為循環條件，判斷方式如上。
用循環隊列建立約瑟夫環，將1-7個元素依次進入隊列，以隊列的長度作為與已輸出的元素作為判斷條件，對每一個輸出後的元素重新賦值以為標記。對於每次循環，首先檢查該位置元素是不是我們設立的標記-1，如果不是則循環次數加1，將隊首指針移到隊列的下一個元素，結束此次循環，當達到要求的循環次數時就將重新循環次數設置為0，輸出該元素到屏幕並將總輸出元素加1.

問題分析與算法設計

約瑟夫問題並不難，但求解的方法很多;題目的變化形式也很多。這裡給出一種實現方法。

題目中30個人圍成一圈，因而啟發我們用一個循環的鏈來表示，可以使用結構數組來構成一個循環鏈。結構中有兩個成員，其一為指向下一個人的指針，以構成環形的鏈;其二為該人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數，每數到9時，將結構中的標記改為0，表示該人已被扔下海了。這樣循環計數直到有15個人被扔下海為止。