ID #5701

约瑟夫环问题求解算法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));
}


2011-07-01 18:28
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

汉诺塔问题的最终解决

“大整数阶乘”问题的递推算法

A/B向上取整的方法

[算法问题]交换两个子数组的元素值

[算法问题]合并两个已经排序的数组为另一个数组