约瑟夫环问题求解算法C语言源代码

约瑟夫算法：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%10==0)
　　　　　　　　　　　 printf("\n");
　　　　 printf("%4d",data[i]);
　　 }
　　 printf("\nPlease input a number to count:");
　　 scanf("%d",&k);
　　 printf("\nThe last one's number is %d",yuesefu1 (data,total,k));
}