71.約瑟夫問題
這是17世紀的法國數(shù)學(xué)家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。
*問題分析與算法設(shè)計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現(xiàn)方法。
題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示?？梢允褂媒Y(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的鏈；其二為該 人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數(shù)，每數(shù)到9時，將結(jié)構(gòu)中的標記改為0，表示該人已被扔下海了。這樣循環(huán)計數(shù)直到有15個人被扔下海為止。
*程序與程序注釋
#include
struct node
{
int nextp; /*指向下一個人的指針(下一個人的數(shù)組下標)*/
int no_out; /*是否被扔下海的標記。1：沒有被扔下海。0：已被扔下海*/
}link[31]; /*30個人，0號元素沒有使用*/
void main()
{
int i,j,k;
printf("The original circle is(+:pagendom,@:christian):\n");
for(i=1;i<=30;i++) /*初始化結(jié)構(gòu)數(shù)組*/
{
link[i].nextp=i+1; /*指針指向下一個人(數(shù)組元素下標)*/
link[i].no_out=1; /*標志置為1，表示人都在船上*/
}
link[30].nextp=1; /*第30個人的指針指向第一個人以構(gòu)成環(huán)*/
j=30; /*j:指向已經(jīng)處理完畢的數(shù)組元素，從link[i]指向的人開始計數(shù)*/
for(i=0;i<15;i++) /*i:已扔下海的人數(shù)計數(shù)器*/
{
for(k=0;;) /*k:決定哪個人被扔下海的計數(shù)器*/
if(k<15)
{
j=link[j].nextp; /*修改指針，取下一個人*/
k+=link[j].no_out; /*進行計數(shù)。因已扔下海的人計標記為0*/
}
else break; /*計數(shù)到15則停止計數(shù)*/
link[j].no_out=0; /*將標記置 0，表示該人已被扔下海*/
}
for(i=1;i<=30;i++) /*輸出結(jié)果*/
printf("%c",link[i].no_out? ’@’:’+’); /*+:被扔下海， @：在船上*/
printf("\n");
}
*運行結(jié)果
The original circle is(+:pagandom, @:christian):
+++@@+@+@@@+@+++@@+@@@+++@+@@+
這是17世紀的法國數(shù)學(xué)家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。
*問題分析與算法設(shè)計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現(xiàn)方法。
題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示?？梢允褂媒Y(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的鏈；其二為該 人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數(shù)，每數(shù)到9時，將結(jié)構(gòu)中的標記改為0，表示該人已被扔下海了。這樣循環(huán)計數(shù)直到有15個人被扔下海為止。
*程序與程序注釋
#include
struct node
{
int nextp; /*指向下一個人的指針(下一個人的數(shù)組下標)*/
int no_out; /*是否被扔下海的標記。1：沒有被扔下海。0：已被扔下海*/
}link[31]; /*30個人，0號元素沒有使用*/
void main()
{
int i,j,k;
printf("The original circle is(+:pagendom,@:christian):\n");
for(i=1;i<=30;i++) /*初始化結(jié)構(gòu)數(shù)組*/
{
link[i].nextp=i+1; /*指針指向下一個人(數(shù)組元素下標)*/
link[i].no_out=1; /*標志置為1，表示人都在船上*/
}
link[30].nextp=1; /*第30個人的指針指向第一個人以構(gòu)成環(huán)*/
j=30; /*j:指向已經(jīng)處理完畢的數(shù)組元素，從link[i]指向的人開始計數(shù)*/
for(i=0;i<15;i++) /*i:已扔下海的人數(shù)計數(shù)器*/
{
for(k=0;;) /*k:決定哪個人被扔下海的計數(shù)器*/
if(k<15)
{
j=link[j].nextp; /*修改指針，取下一個人*/
k+=link[j].no_out; /*進行計數(shù)。因已扔下海的人計標記為0*/
}
else break; /*計數(shù)到15則停止計數(shù)*/
link[j].no_out=0; /*將標記置 0，表示該人已被扔下海*/
}
for(i=1;i<=30;i++) /*輸出結(jié)果*/
printf("%c",link[i].no_out? ’@’:’+’); /*+:被扔下海， @：在船上*/
printf("\n");
}
*運行結(jié)果
The original circle is(+:pagandom, @:christian):
+++@@+@+@@@+@+++@@+@@@+++@+@@+