C趣味程序百例(22)约瑟夫问题

文章作者 100test 发表时间 2007:03:10 17:30:09
来源 100Test.Com百考试题网

71.约瑟夫问题
这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该 人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
*程序与程序注释
#include
struct node
{
int nextp. /*指向下一个人的指针(下一个人的数组下标)*/
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 ) /*初始化结构数组*/
{
link[i].nextp=i 1. /*指针指向下一个人(数组元素下标)*/
link[i].no_out=1. /*标志置为1，表示人都在船上*/
}
link[30].nextp=1. /*第30个人的指针指向第一个人以构成环*/
j=30. /*j:指向已经处理完毕的数组元素，从link[i]指向的人开始计数*/
for(i=0.i<15.i ) /*i:已扔下海的人数计数器*/
{
for(k=0..) /*k:决定哪个人被扔下海的计数器*/
if(k<15)
{
j=link[j].nextp. /*修改指针，取下一个人*/
k =link[j].no_out. /*进行计数。因已扔下海的人计标记为0*/
}
else break. /*计数到15则停止计数*/
link[j].no_out=0. /*将标记置 0，表示该人已被扔下海*/
}
for(i=1.i<=30.i ) /*输出结果*/
printf("%c",link[i].no_out? ’@’:’ ’). /* :被扔下海， @：在船上*/
printf("\n").
}
*运行结果
The original circle is( :pagandom, @:christian):
@@ @ @@@ @ @@ @@@ @ @@