计算机二级:约瑟夫环问题求解算法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 ones number is %d",yuesefu1(data,total,k)).
　　}

　　特别推荐：

　　2009年9月全国计算机等级考试时间及科目预告

　　2009年上半年全国计算机等级考试参考答案请进入计算机考试论坛

　　2009年全国计算机等级考试报名信息汇总

　　2009年NCRE考试有新变化

　　2009年全国计算机等级考试-大纲

　　2009年上半年全国计算机二级考试试题及答案

　　2009年上半年全国计算机等级考试试题答案汇总