約瑟夫環

問題來由

據說著名猶太曆史學家Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定甯願死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。

然而Josephus和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接着，再越過k-1個人，并殺掉第k個人。這個過程沿着圓圈一直進行，直到最終隻剩下一個人留下，這個人就可以繼續活着。

問題是，給定了和，一開始要站在什麼地方才能避免被處決。Josephus要他的朋友先假裝遵從，他将朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡遊戲。

17世紀的法國數學家加斯帕在《數目的遊戲問題》中講了這樣一個故事：15個教徒和15個非教徒在深海上遇險，必須将一半的人投入海中，其餘的人才能幸免于難，于是想了一個辦法：

30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就将他扔入大海，如此循環進行直到僅餘15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。

問題分析與算法設計

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

題目中30個人圍成一圈，因而啟發我們用一個循環的鍊來表示，可以使用結構數組來構成一個循環鍊。結構中有兩個成員，其一為指向下一個人的指針，以構成環形的鍊；

其二為該人是否被扔下海的标記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數，每數到9時，将結構中的标記改為0，表示該人已被扔下海了。這樣循環計數直到有15個人被扔下海為止。

一般形式

約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數，第M個将被殺掉，最後剩下一個，其餘人都将被殺掉。例如N=6，M=5，被殺掉的順序是：5，4，6，2，3。

分析：

（1）由于對于每個人隻有死和活兩種狀态，因此可以用布爾型數組标記每個人的狀态，可用true表示死，false表示活。

（2）開始時每個人都是活的，所以數組初值全部賦為false。

（3）模拟殺人過程，直到所有人都被殺死為止。

概述

是一個數學的應用問題：

已知n個人（以編号1，2，3...n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。

這個就是約瑟夫環問題的實際場景，有一種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題采用的是典型的循環鍊表的數據結構，就是将一個鍊表的尾元素指針指向隊首元素。p->link=head

解決

解決問題的核心步驟：

1.建立一個具有n個鍊結點，無頭結點的循環鍊表

2.确定第1個報數人的位置

3.不斷地從鍊表中删除鍊結點，直到鍊表為空

void JOSEPHUS(int n,int k,int m)//n為總人數，k為第一個開始報數的人，m為出列者喊到的數

{/*p為當前結點r為輔助結點，指向p的前驅結點list為頭節點*/

LinkList p,r,list;

/*建立循環鍊表*/

for(int i=0,i

{p=(LinkList)malloc(sizeof(LNode));

p->data=i;

if(list==NULL)

list=p;

else

r->link=p;

r=p;}

p>link=list;/*使鍊表循環起來*/

p=list;/*使p指向頭節點*/

/*把當前指針移動到第一個報數的人*/

for(i=0;i

{r=p；

p=p->link;}

/*循環地删除隊列結點*/

while(p->link!=p)

{for(i=0;i

{r=p;

p=p->link;}

r->link=p->link;

printf("被删除的元素：%4d",p->data);

free(p);

p=r->link;}

printf("n最後被删除的元素是：％4d",P->data);}