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