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

约瑟夫环问题求解算法C语言源代码2010-11-19约瑟夫算法：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（"
Please input the number of every people.
"）;
   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（"
Data error.Re-input:"）;
   }
   total=i;
   printf（"
You have input:
"）;
   for（i=0;i<total;i++）
   {
     if（i%10==0）
            printf（"
"）;
     printf（"%4d",data[i]）;
   }
   printf（"
Please input a number to count:"）;
   scanf（"%d",&k）;
   printf（"
The last one"s number is %d",yuesefu1 （data,total,k））;
}