C趣味程序百例(22)约瑟夫问题
71.约瑟夫问题
这是17世纪法国数学家加斯帕尔在数字游戏中讲的一个故事:15个基督徒和15个非基督徒在深海中遇险,其中一半人要被扔进海里,剩下的人才能活下来。于是他们想了一个办法:30个人围成一个圈,从第一个人开始依次数数,每隔9个人就扔进海里。请教如何安排,让每一个投海自尽的人都是非信徒。
*问题分析与算法设计
约瑟夫斯问题并不难,但求解方法很多;话题转换的形式也有很多种。下面是一个实现方法。
题目中30个人组成一个圈,从而启发我们用循环链来表达。您可以使用结构数组来形成循环链。结构中有两个成员,一个是指向下一个人的指针,形成一个循环链;第二个是这个人是否被扔到海里的标记,1表示他还在船上。从第一个人开始数没扔进海里的人,每数到9就把结构里的标记换成0,表示这个人已经扔进海里了。如此循环,直到15个人被扔进海里。
*程序和程序注释
# include
结构节点
{
int nextp;/*指向下一人的指针(下一人的数组下标)*/
int no _ out;/*是否被扔进海里的标记。1:不是扔到海里。0:已经被扔到海里*/
}链接[31];/*30人,元素0没有使用*/
void main()
{
int I,j,k;
printf("原圈是(+:pagendom,@:Christian):\ n ");
for(I = 1;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 {
for(k = 0;;)/*k:决定哪个人被扔进海里的计数器*/
if (k {
j = link [j]。nextp/*修改指针,取下一个人*/
k+=link[j]。no _ out/*计数。投海人数标记为0 */
}
else break;/*数到15就停止计数*/
link[j]。no _ out = 0;/*将标志设置为0,表示此人已经被扔到海里*/
}
for(I = 1;我打印f("%c ",链接[i]。no_out?'@':'+');/*+:扔到海里,@:在船上*/
printf(" \ n ");
}
*运行结果
原圈是(+:Pagandom,@:Christian):
+++@ @ ++ @ @
0条评论