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):
+++@ @ ++ @ @