`
214740484
  • 浏览: 23175 次
  • 来自: 广州
社区版块
存档分类
最新评论

约瑟夫环问题:n个人围成一圈,第一个人从1开始报数,每次报到M的人出列,然后从1开始重新报数,求最后一个出列的人。

 
阅读更多
#include<stdio.h>
#include<stdlib.h>

//n个人坐一圈,从头开始数,每次数到M的出列,求最后出列的人 
void loop(int n,int M)
{
    int a[n],m=0,number=0;
    int i,j; 
    for(j=0;j<n;j++)
    {
         a[j]=(j+1);//初始化数组,第一个人是a[0]=1,以此类推 
    } 
   for(i=0;i<n;i++)
    {
            if(a[i]>0)//大于0说明还没出列
            {         
                      //printf("judge a[%d] is %d\n",i,a[i]);
                      m++; 
                      if(m==M)//数到第M个人
                      {
                               printf("---->person %d is out\n",a[i]);
                               a[i]=0;       //设置改变量的值为0,为0则说明人已经出列了
                               m=0;          //重新报数
                               number++;     //统计一共出列了多少人
                               if(number==n)
                               {
                                    printf("end\n");
                                    break;//判断所有人出列之后跳出for循环 
                                }
                               
                      }        
            }
            if(i==(n-1))
            {
                   i=-1;//回到队列开始的处
                        //注意此处不能直接置零,因为for里面还会执行一次i++
            }
    }
}
int main()
{
    loop(10,3);//test, you can test other number
    
   // printf("the result is %d\n",a);
    system("pause");
    }

 主要思路如下:设置一个长度为n的数组,然后赋予其值,其值代表其位置,然后再该队列里面报数,每次报到M值即出列并重新报数,一轮数完之后重新再队列开头。

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics