**問題由來：** ?????? 在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第*k*個人。接著，再越過k-1個人，并殺掉第*k*個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。 **一般形式：** ?????? N個人圍成一個圈，編號為1到N，從1號開始報數，報數為M的人出局；其他人繼續圍成圈，從出局人的下一個開始重新報數，報到M的人又出局。直到剩下最后一個人。 可以用數組或者鏈表來模擬這個報數的過程，如下是數組實現的C++代碼： ~~~ const int maxn = 10000; void ArrayJose() { bool jose[maxn] = {0}; //設置一個數組來模擬N個人 int m_count = 0; //記錄當前報的數 int i = 0; //記錄當前遍歷的是數組的第幾個元素 int out_count = 0; //記錄當前出局的人數 int n, m; cin >> n >> m; do { ++i; if (i > n) //所有人報數完后從頭開始報數 i = 1; if (!jose[i]) //若數組元素為0，即這個人沒出局 m_count++; if (m_count == m) { //報數為m的人出局 m_count = 0; //重新開始報數 cout << i << " "; //輸出出局人編號 jose[i] = 1; //將這個人所在位置標記為出局：1 out_count++; //出局人數加1 } } while (out_count != n); } ~~~ 以下是C++的循環單鏈表方式： ~~~ struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; struct Node { int element; Position next; }; List MakeCircleList(int n) { ?List jose = NULL; ?int i = 0; ?Position node, rear; ?for (i = 1; i <= n; i++) { ??? ?node = (struct Node *)malloc(sizeof(struct Node)); ??? ?if (node == NULL) { ??? ??? ?cout << "malloc failed." << endl; ??? ??? ?return NULL; ??? ?} ??? ?node->element = i; ??? ?if (jose == NULL) { ??? ??? ?jose = node; ??? ?} ??? ?else { ??? ??? ?rear->next = node; ??? ?} ??? ?rear = node; ?} ?rear->next = jose; ?return jose; } void CircleListJose(int n, int m, List jose) { ?int m_count = 0, out_count = 0; ?int i; ?Position q, p = jose; ?q = p; ?while (p->next != p) { ??? ?for (i = 1; i < m; ++i) { ??? ??? ?q = p; ??? ??? ?p = p->next; ??? ?} ??? ?Position start = p->next; ??? ?cout << p->element << " "; ??? ?q->next = p->next; ??? ?free(p); ??? ?p = start; ?} ?cout << p->element << endl; } ~~~ ???????? 以上的兩種方式的思想都是一樣的：要模擬所有人報數并出局的整個過程。這種思想的復雜度比較大，為O(mn)。通過數學方式可以提高算法的效率。可以將問題描述改為：n個人（編號0~(n-1))，從0開始報數，報到(m-1)的退出，剩下的人繼續從0開始報數。求勝利者的編號。 ?????? 注意這里的方法沒有將每次報數人的編號計算出來，而是僅僅求出了勝利者的編號，下面算法的復雜度為O(n)。 ?????? 當第一個人出列后（這個人的編號一定是（m - 1）% n，剩下的n - 1 個人重新構成了一個新的約瑟夫環（這個環以k = m % n開始報數）： k，k+1，k+2，……，n-2，n-1，0，1，……，k-2。 ????? 將這n-1個人依次重新編號為0，1，2，……，n-1： k ? ---> ?0， k+1 ?---> ? 1， k+2 ?----> ? 2， …… k-2 ---> ? n - 2 即轉換映射為 x ? ---> ?(n + x - k - 1) % n ? == ?(x - k - 1) % n，反向的轉換關系為： ?x ?<--- ?(x + k + 1 - n) % n == ?(x + k + 1)?% n? ??????? 這些人繼續從0號開始報數，那么，如果這n-1個人子問題的最后勝利者編號為f(n)。如果設n個人時勝利者編號為f(n - 1)的話，那么可以得到遞推關系式： f(n) ?= (f(n - 1) ?+ k ?+ 1) % n; ? 將 k =?（m - 1）% n 代入， f(n) = ( f(n - 1) + (m - 1) % n + 1) % n = ( f(n - 1) + m) % n ??????? 也就是說，如果求得了n-1個人的勝利者根據遞推關系式就可以求得n個人的勝利者，那么n-1個人的勝利者就通過求n-2個人的勝利者來求，因此這是遞歸過程。 解f(1) = 0; ? f(i) = (f(i - 1) + m) % i;(i > 1) 。這里的f(i)表示的是勝利者的編號。 代碼實現如下： ~~~ int main(void) { int n, m,i, f[20]={0}; scanf("%d %d",&n,&m); for(i=2;i<=n;i++) { f[i]=(f[i-1]+m)%i; printf("%d個人報數，報到%d的出列，最后的勝者下標為%d\n", i,m,f[i]); } printf("The winner is %d\n", f[n]+1); system("pause"); } ~~~ 優化后代碼： ~~~ int main(void) { int n, m,i, s=0; scanf("%d %d",&n,&m); for(i=2;i<=n;i++) { s=(s+m)%i; } printf("The winner is %d\n", s + 1); } ~~~ -----------------------------------------------------------------------分割線----------------------------------------------------------------------------------- 注意以下使用的變量含義與上述沒必要聯系。 一道ACM的約瑟夫變形題： Description The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.? Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.? Input The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. Output The output file will consist of separate lines containing m corresponding to k in the input file. Sample Input ~~~ 3 4 0 ~~~ Sample Output ~~~ 5 30 ~~~ ??????? 一共2k個人，前k個人為好人，后k個人為壞人，要求選擇m，使得所有壞人被殺前不能誤殺好人。 ?????? 設第0輪仇殺人編號為0，即f[0] = 0，第i輪抽殺人的編號為f[i] = (f[i - 1] + m - 1) % (2k - (i - 1));(i > 0)。 設置一個大小為14的int數組，用來存仇殺遞推數組，因為抽殺的遞推公式計算時需要前一次的數據。然后讀入一個k，初始化抽殺數字為m = k + 1，因為之前的數字第一次抽殺好人，不符合規定，直接略過。用m抽殺一輪，如果f[i] < k，說明好人被殺，直接m++重新抽殺。如果k輪仇殺都沒有殺死好人，則這個m就是符合要求的，輸出m。 ~~~ #include <iostream> using namespace std; int main() { int k = 0,joseph[14] = {0}, ans[14] = {0}; while (cin >> k) { if (k == 0) break; if (ans[k]) { //如果讀入的k對應的m已經計算出來，就直接打印 cout << ans[k] << endl; continue; } int n = 2 * k, m = k + 1; for (int i=1; i<=k; i++) { joseph[i] = (joseph[i-1] + m - 1) % (n - i + 1); //遞推關系，第i輪殺死的人 if (joseph[i] < k) { //如果第i輪殺死的人是好人則m直接加1，重新開始計算 i=0; m++; } } ans[k] = m; //記錄符合要求的m并輸出 cout << m << endl; } return 0; } ~~~ 或者對于0到14之間的k，將符合要求的所有m都計算出來，存入數組，然后輸入一個k就從數組中找到對應的結果即可： ~~~ int main() { int k; int ans[20]; int Joseph[20]={0}; for(k=1;k<14;k++) { int m=1; memset(ans,0,sizeof(Joseph)); for(int i=1;i<=k;i++) { Joseph[i]=(Joseph[i-1]+m-1)%(2*k-i+1); //遞推公式 if(Joseph[i] < k) { i=0; m++; } } ans[k]=m; } while(scanf("%d",&k)&&k!=0) { printf("%d\n",ans[k]); } return 0; } ~~~ --------------------------------------------------------------分割線------------------------------------------------------------- 另一種變形題是：n個人圍成圈，每個人持有一個正數密碼，依次報數，報數為m的人出局；將m的值設置為出局人的密碼，從出局人的下一個人重新報數，報到該密碼的人出局，依次循環；直到剩下最后一人。 該問題目前沒有好的解法，只能用開始介紹的循環單鏈表進行遍歷，只是每次出局時m的值要重新設置，單路表節點使用如下的結構體： ~~~ struct Node { int element; //人員編號 int key; //密碼 struct Node *next; }; ~~~