先說明一點，如果有什么不對的地方，歡迎大家批評指正。

先來看這個類型的某個題目描述：

約瑟夫生者死者游戲

約瑟夫游戲的大意：30個游客同乘一條船，因為嚴重超載， 加上風浪大作，危險萬分。因此船長告訴乘客，只有將全船 一半的旅客投入海中，其余人才能幸免于難。無奈，大家只 得同意這種辦法，并議定30 個人圍成一圈，由第一個人數起，依次報數，數到第9人，便把他投入大海中，然后再從 他的下一個人數起，數到第9人，再將他投入大海中，如此 循環地進行，直到剩下 15 個游客為止。問：哪些位置是將 被扔下大海的位置？

不失一般性，將 30 改為一個任意輸入的正整數 n，而報數 上限（原為9）也為一個任選的正整數k

第一次看到這個題目，我首先想到的是用 鏈表 或者是 數組 來模擬，但是當我寫完之后，與大神對答案，發現他的c語言代碼是這么寫的：

int ysfdg ( int sum, intvalue, intn)
{
if ( n == 1 )
return ( sum + value - 1 ) %sum;
else
return ( ysfdg ( sum-1, value,n-1 ) +value ) %sum;
}

7行。。。。。。再見（已經不能做朋友了嗎。。。）

sum指的是總人數，value指的是每次最大報到的數值，n是第n次，該函數每次可以求出第n次扔海里的人的編號，( ysfdg指的是約瑟夫遞歸 ) 。

大神飄然而去，而我懵逼了一天，才明白了這段代碼的意思。

舉個栗子：

總人數sum為10人，從0開始，每報到4就把一人扔下去（value=4）。

初始情況為:

0 1 2 3 4 5 6 7 8 9

扔下去一個之后:

0 1 2 4 5 6 7 8 9

此時，這些編號已經不能組成一個環，但是可以看出4至2之間還是連著的（4 5 6 7 8 9 0 1 2），且下一次報數將從4開始。但是，之后的報數將總要考慮原編號3處的空位問題。

如何才能避免已經產生的空位對報數所造成的影響呢？

可以將剩下的9個連續的數組成一個新的環（將2、4連接），這樣報數的時候就不用在意3的空位了。但是新產生的環的數字并非連續的，報數時不像之前那樣好處理了（之前沒人被扔海里時下一個報數的人的編號可以遞推，即(當前編號+1)%sum ），無法不借助存儲結構得知下一個應該報數的現存人員編號。

如何使新環上的編號能夠遞推來簡化我們之后的處理呢？

可以建立一種有確定規則的映射，要求映射之后的數字可以遞推，且可以將在新環中繼續按原規則報數得到的結果逆推出在舊環中的對應數字。

方法：將它與 sum-1 個人組成的（0 ~ sum-1）環一 一映射。

比如之前的栗子，將剩余的 9 人與 9 人環（0~8）一 一映射。既然 3 被扔到海里之后，報數要從4開始 （4 其實在數值上等于最大報數值），那么就將4映射到0~8的新環中0的位置，也就是說在新環中從0開始報數即可，且新環中沒有與3對應的數字，因此不必擔心有空位的問題。從舊環的 4 開始報數等效于從新環中的 0 開始報數。

原始 0 1 2 3 4 5 6 7 8 9

舊環 0 1 2 4 5 6 7 8 9

新環 6 7 8 0 1 2 3 4 5

新環有這么一個優勢: 相比于舊環中2與4之間在數學運算上的不連續性，新環8和0之間在對9取余的運算中是連續的，也就是說根本不需要單獨費心設計用以記錄并避開已產生的空位（如 編號3）的機制 ，新環的運算不受之前遺留結果的掣肘。同時只要能將新環與舊環的映射關系逆推出來，就能利用在新環中報數的結果退出之前舊環中的報數結果。

以下是新環與舊環中下一個要人扔海里的人位置:

舊環 0 1 2 4 5 6 7 8 9

^

新環 6 7 8 0 1 2 3 4 5

^

如何由新環中的 3 得到舊環中的 7 呢。其實可以簡單地逆推回去 : 新環是由 (舊環中編號-最大報數值)%舊總人數 得到的，所以逆推時可以由 ( 新環中的數字 + 最大報數值 )% 舊總人數 取得。即 old_number = ( new_number + value ) % old_sum.

如 : ( 3 + 4 ) % 10 =7 .

也就是說在，原序列( sum ) 中第二次被扔入海中編號可以由新序列( sum - 1) 第一次扔海里的編號通過特定的逆推運算得出。

而新序列 (sum -1)也是（從0開始）連續的，它的第二次被扔入海中的編號由可以由（sum - 2）的第一次扔入海里的編號通過特定的逆推運算得出，并且它的第二次被扔入海中的編號又與原序列中的第三次被扔入海里的編號是有對應關系的。

也求是說有以下推出關系:

(sum-2)環的第1次出環編號 >>>(sum-1)環的第2次出環編號 >>>(sum)環的第3次出環編號

即 在以 k 為出環報數值的約瑟夫環中， m人環中的第n次出環編號可以由 (m-1) 人環中的第 (n-1) 次出環編號通過特定運算推出。

幸運的是，第一次出環的編號是可以直接求出的，也就是說，對于任意次出環的編號，我們可以將之一直降到第一次出環的編號問題，再一 一 遞推而出。

注意 以下圖示中的環數字排列都是順序的，且從編號0開始。

由圖知，10人環中最后入海的是4號，現由其在1人環中的對應編號0來求解。

通過以上運算，其實我們已經求出分別位于9個環中九個特定次數的結果，只不過我們需要的是10人環的結果罷了。

這種方法既可以寫成遞歸也可以寫成循環，它對于求特定次數的出環編號效率較高。

遞歸就比較好寫了，出口即是當次數為1時。

實際編號是從1開始，而不是0，輸出時要注意轉換。

借此就可以看懂那個大神的代碼了。

以下是三種約瑟夫環解法（數組，鏈表，遞歸）的c語言代碼，作者水平不高，將就看看吧 ╮(╯_╰)╭：

#include<stdio.h> #include<stdlib.h> #define FAIL 0 #define SUCCESS 1typedef struct gamenode {int number;struct gamenode* next;} node;//讀入初值 int getvalue(int* sum,int* count,int* alive) {printf("請輸入要參與約瑟夫生存游戲的人數:(人數>0)\n");while(1){scanf("%d",sum);if(*sum>0)break;printf("輸入無效，請重新輸入。\n");};printf("請輸入能報到的最大數字:(1<=數字)\n");while(1){scanf("%d",count);if(*count>=1)break;printf("輸入無效，請重新輸入。\n");};printf("請輸入要求最后存活的人數:(0<=人數<=%d)\n",*sum);while(1){scanf("%d",alive);if(*alive>=0&&*alive<=*sum)break;printf("輸入無效，請重新輸入。\n");};return SUCCESS; }//數組解法 int ysfsz(int n,int k,int s) {int i=0,*p=NULL,sum=n-k,j=1,o=0,pr=0;if ((p=(int*)malloc(sizeof(int)*n))==NULL){printf("FAIL!\n");return FAIL;}for(i=0;i<n;i++){p[i]=1;}i=0;while(1){if (sum==0)break;if (j==s&&p[i]==1){ p[i]=0;j=1;--sum;}else if(p[i]==1){ j++;}i++;i=i%n; }printf("\n生存下來的人的位置是:");for(i=0;i<n;i++){if(p[i]==1)printf("%d ",i+1);}printf("\n");printf("\n扔海里的位置是:");for(i=0;i<n;i++){if(p[i]==0)printf("%d ",i+1);}printf("\n");free(p);return SUCCESS; }//鏈表解法 int ysflb(int n,int k,int s) {node *h=NULL,*p=NULL,*q=NULL;int i=0;if ((h=(node*)malloc(sizeof(node)*n))==NULL){printf("FAIL!\n");return FAIL;}h->number=1;h->next=h;q=h;for(i=1;i<n;i++){if ((p=(node*)malloc(sizeof(node)*n))==NULL){printf("FAIL!\n");exit (-1);}else{ p->next=NULL;p->number=i+1;q->next=p;q=q->next;}}q->next=h;p=h;i=1;k=n-k;while(k>0){if(i==s){if(p!=p->next){q->next=p->next;printf("%d號已被扔進海里。\n",p->number);free(p);p=q->next;}else{printf("%d號已被扔進海里。\n",p->number);p=q=h=NULL;}--k;}else{p=p->next;q=q->next;}++i;if(i>=s+1)i=1;}if(p!=NULL){printf("幸存下來的人有:");h=p;p=p->next;while(p!=h){q=p->next;printf("%d ",p->number);free(p);p=q;}printf("%d ",h->number);free(h);}elseprintf("全部扔海里去了。\n");return SUCCESS; }//遞歸解法 int ysfdg(int sum,int value,int n) {if(n==1)return (sum+value-1)%sum;elsereturn (ysfdg(sum-1,value,n-1)+value)%sum; }//主函數 int main(void) {int sum=0,count=0,alive=0,i=0;//讀入總人數，報數值，存活人數getvalue(&sum,&count,&alive);/*------------------------------------------------------------*/ //1.約瑟夫環的數組解法//ysfsz(sum,alive,count);//2.約瑟夫環的鏈表解法//ysflb(sum,alive,count);//3. 約瑟夫環遞歸解法for(i=1;i<=sum-alive;i++)printf("第%2d個被扔海里人的編號:%2d\n",i,ysfdg(sum,count,i)+1);return 0; }

總結

以上是生活随笔為你收集整理的映射递归循环-约瑟夫环问题递归解法的一点理解的全部內容，希望文章能夠幫你解決所遇到的問題。

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