約瑟夫問題由來

據說著名猶太歷史學家 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個人被扔下海為止。

問題示例

設編號分別為:1,2,...,n的n個人圍坐一圈。約定序號為k(1 <= k < = n)的人從1開始計數，數到m的那個人出列，他的下一位又從1開始計數，數到m的那個人又出列，依次類推，直到所有人出列為止；

設n=8,k=3,m=4時：

出列為:6,2,7,4,3,5,1,8

算法思路:用一個不帶頭結點的循環鏈表來處理Josephu問題：先構成一個有n個結點的單循環鏈表，然后從第k結點起從1計數，計到m時，對應結點從鏈表中刪除；然后再從被刪除結點的下一個結點起又從1開始計數....,直到所有結點都列出時算法結束。

代碼實現：

總結

以上是生活随笔為你收集整理的围成一圈的排列组合问题_约瑟夫问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。