计算机二级:约瑟夫环问题求解算法C语言源代码计算机二级考试
文章作者 100test 发表时间 2009:05:08 19:43:14
来源 100Test.Com百考试题网
2009年下半年全国计算机等级考试你准备好了没?考计算机等级考试的朋友,2009年下半年全国计算机等级考试时间是2009年9月19日至23日。更多优质资料尽在百考试题论坛 百考试题在线题库
约瑟夫算法:n个人围成一圈,每人有一个各不相同的编号,选择一个人作为起点,然后顺时针从1到k数数,每数到k的人退出圈子,圈子缩小,然后从下一个人继续从1到k数数,重复上面过程。求最后推出圈子的那个人原来的编号。
思路:按照上面的算法让人退出圈子,直到有n-1个人推出圈子,然后得到最后一个退出圈子的人的编号。
程序:坐成一圈的人的编号不需要按序排列
#define N 100
int yuesefu1(int data[],int sum,int k)
{
int i=0,j=0,count=0.
while(count<.sum-1)
{
if(data[i]!=0)/*当前人在圈子里*/
j .
if(j==k)/*若该人应该退出圈子*/
{
data[i]=0./*0表示不在圈子里*/
count ./*退出的人数加1*/
j=0./*重新数数*/
}
i ./*判断下一个人*/
if(i==sum)/*围成一圈*/
i=0.
}
for(i=0.i<.sum.i )
if(data[i]!=0)
return data[i]./*返回最后一个人的编号*/
}
void main()
{
int data[N].
int i,j,total,k.
printf("\nPlease input the number of every people.\n").
for(i=0.i<.N.)/*为圈子里的人安排编号*/
{
int input.
scanf("%d",&.input).
if(input==0)
break./*0表示输入结束*/
for(j=0.j<.i.j )/*检查编号是否有重复*/
if(data[j]==input)
break.
if(j>.=i&.&.input>.0)/*无重复,记录编号,继续输入*/
{
data[i]=input.
i .
}
else
printf("\nData error.Re-input:").
}
total=i.
printf("\nYou have input:\n").
for(i=0.i<.total.i )
{
if(i==0)
printf("\n").
printf("M",data[i]).
}
printf("\nPlease input a number to count:").
scanf("%d",&.k).
printf("\nThe last one s number is %d",yuesefu1(data,total,k)).
}
特别推荐:
2009年9月全国计算机等级考试时间及科目预告