約瑟夫斯問題（Josephus Problem）

約瑟夫斯問題（有時也稱為約瑟夫斯置換），是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又稱為“約瑟夫環”，也有的地方叫做“丟手絹”。

問題是這樣的：
有編號從1 到n的 n個人圍坐成一圈。從編號為1的人開始報數，報到 m 的人出局，下一位再從 1 開始報數，報到 m 的人出局，……如此持續，直到剩下一人為止，假設此人的原始編號是x。給定 n和 m，求出x。

為了說明問題，我們舉個例子。這個例子中n=4, m=2. 最終結果x=1.
以下是示意圖（橫著看）

思路一：編程模擬

若編程解決此問題，很容易想到用數組或者循環鏈表模擬整個過程，直到剩下一個人。

用數組模擬

C語言代碼如下。

#include <stdio.h> #include <stdlib.h>void josephus(int n,int m) //一共n個人，報m的人被淘汰 {if((n<=1) || (m<=1)) //n和m最小是2return;//數組的下標作為每個人的編號。a[0]不使用int *a = (int *)malloc(sizeof(int)*(n+1)); if(a==NULL){printf("內存分配失敗\n");return;}int i;for(i=1;i<n+1;++i)a[i]=1; // 初始化，1表示人存在int count = 0; //用來模擬報數，取值從0到m int left = n; // 用來記錄剩下的人數while(1){for(i=1;i<=n;++i){if(a[i]) //如果人存在{ ++count; //模擬報數，這里取值從1到mif(count == m){a[i]=0; //此人被淘汰printf("%d ",i); //打印被淘汰的人的編號count=0; //重置為0，準備下一輪報數--left;if(left == 1) //說明只剩一個人,這時候跳出死循環goto out;} } }}out:for(i=1;i<=n;++i){if(a[i]) //找到最后的那個人，打印其編號{printf("%d ",i);break;}}printf("\n");free(a); }int main(void) //測試代碼 {josephus(41,3); return 0; }

運行結果如下：

3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

為了驗證結果的正確，除了人工計算外，我從網上找了一張圖片來對比：

用循環鏈表模擬

【錯誤的代碼】本來想刪除這部分內容，算了，留個紀念吧。

#include <stdio.h> #include <stdlib.h>void josephus(int n,int m);int main(void) {josephus(41,3);return 0; }struct node {int data;struct node *next; }; typedef struct node node_t;void josephus(int n,int m) {// 創建頭結點node_t *head = (node_t *)malloc(sizeof(node_t));if(head==NULL){printf("內存分配失敗\n");return;}node_t *pre = head;node_t *cur;for(int i=1;i<=n;++i){cur = (node_t *)malloc(sizeof(node_t));if(cur==NULL){printf("內存分配失敗\n");return;}cur->data = i; //用data字段存儲編號pre->next = cur;pre = cur;} //以上帶頭結點的單向鏈表創建完畢，此時cur指向最后一個結點cur->next = head->next; //最后一個結點的next域指向第一個結點，構成循環鏈表cur = head->next; // 讓cur指向第一個人free(head); //頭結點不再使用，釋放頭結點int skip;while(n--) //每次循環淘汰一人（包括勝利者），循環n次{skip = m-1; //從1報數到m,即跳過（m-1）個人while(skip--){pre = cur;cur = cur->next; //cur指向下一個人}pre->next = cur->next; //淘汰一人printf("%d ",cur->data); //打印被淘汰者的編號free(cur); //釋放結點 cur = pre->next; //從1開始報數，cur指向報1的人 }printf("\n"); }

測試上面的代碼，雖然結果正確，但是我發現了一個BUG，請注意64~65這兩行

free(cur); //釋放結點 cur = pre->next; //從1開始報數，cur指向報1的人

當執行最后一次循環體的時候，此時只剩一個人，cur和pre指向的是同一個地址，執行完free(cur);與此地址關聯的內存已經被釋放，cur和pre都不能被引用了（除非它們又指向了其他有效的內存區域）。但是，cur = pre->next這條語句又引用了pre。所以，這是一個BUG！

所以，我修改了while循環（見下面33~46行）。
【正確的代碼】

void josephus(int n,int m) {// 創建頭結點node_t *head = (node_t *)malloc(sizeof(node_t));if(head==NULL){printf("內存分配失敗\n");return;}node_t *pre = head;node_t *cur;for(int i=1;i<=n;++i){cur = (node_t *)malloc(sizeof(node_t));if(cur==NULL){printf("內存分配失敗\n");return;}cur->data = i; //用data字段存儲編號pre->next = cur;pre = cur;} //以上帶頭結點的單向鏈表創建完畢cur->next = head->next; //最后一個結點的next指向第一個結點，構成循環鏈表cur = head->next; // cur指向第一個人free(head); //頭結點不再使用，釋放頭結點int skip;while(cur->next != cur) //不斷淘汰，直到剩下一個人{skip = m-1; //從1報數到m,即跳過（m-1）個人while(skip--){pre = cur;cur = cur->next; //cur指向下一個人}pre->next = cur->next; //淘汰printf("%d ",cur->data); //打印被淘汰者的編號free(cur); //釋放結點cur = pre->next; //從1開始報數，cur指向報1的人 } printf("%d\n",cur->data); //打印最后一個人的編號free(cur); }

思路二：數學公式法

無論是用數組還是用循環鏈表求解，都有一個共同點——要模擬整個過程，時間復雜度高達O(n*m)，當n*m非常大（例如上百萬、上千萬）的時候，是非常耗時間的。

注意到原問題僅僅要求算出最后勝利者的編號，而不是要求模擬整個過程。因此要追求效率，就要打破常規，比如利用數學方法。

為了討論方便，先把問題稍微改變一下，并不影響原意。

有編號從0 到n-1的 n個人圍坐成一圈。從編號為0的人開始報數，報到 m-1 的人出局，下一位再從 0 開始報數，報到 m-1 的人出局，……如此持續，直到剩下一人為止，假設此人的原始編號是x。給定 n和 m，求出x。

還是以n=4, m=2為例，每淘汰一個人后（綠色表示），我們給余下的人重新編號（從0開始編），示意圖（豎著看）如下。

令 f(i) 表示i個人玩此游戲最后勝利者的編號，那么本問題就是求f(n).
不管多少人玩這個游戲，最后勝出者的新編號都是0，所以我們規定
f(1)=0;
由上圖第一行可以得出：
f(2)=0, f(3)=2, f(4)=0;
其中的規律是：
f[i]=(f[i-1]+m)%i; (i>1)

也就是說遞推公式如下：
f[i]=0; (i=1)
f[i]=(f[i-1]+m)%i; (i>1)

公式的證明可以參考維基百科，這里略去。
根據公式我們就可以寫出代碼，C語言代碼如下。

void josephus(int n,int m) {int s = 0;for(int i=2; i<=n; ++i){s = (s+m)%i;}printf("the winner = %d\n",s); }

測試代碼是

int main(void) {josephus(41,3);return 0; }

運行結果是

the winner = 30

如果編號從1開始，那么獲勝者的編號是31，這和前兩種方法得出的結果是一致的。

【參考資料】
[1] 維基百科https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
[2] http://mathworld.wolfram.com/JosephusProblem.html
[3] http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/

總結

以上是生活随笔為你收集整理的程序员面试系列——约瑟夫环的全部內容，希望文章能夠幫你解決所遇到的問題。

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