首页 > 代码库 > 算法:约瑟夫环问题

算法:约瑟夫环问题

算法:约瑟夫环问题

【写在前面】

  由于本人天生驽钝,所写代码和描述可能不堪入目,高手请移步。但是我一直在努力记录一下有用的知识点,给自己给朋友用,只是希望对大家有帮助。

【问题描述】

  约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从第一个人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,求最后一个出圈的人的标号。

【代码】

void JOSEF(int n,int m) //:n个人,m出列{    int people[n+1]; //我们定义的数组大小为n+1,因为我们不想涉及到0的操作,我们只取1到n这个范围内的标号,忽略0    for(int i=1;i<=n;i++)        people[i]=i; //将数组内(除0)的每一个元素进行初始化,其实非0即可,值无所谓。    int flag=n-1;    //我们要在数组里面删除多少个元素呢?答案是n-1个。剩下的一个为最后出圈的那一个    int p=1;         //用来指示元素下标    int count=0;     //计数器        while(flag)      //没有删完的情况下继续    {        if(people[p]==0)  //如果p所指的元素为0,表示该元素已经出圈,可以跳过        {            if(p==n)      //这段代码就是让尾部连接头部                    p=1;            else                    p++;            continue;        }        count++;       //找打一个不为0的元素        if(count==m)   //如果我们找够m个,就将这个元素出圈,也就是设为0        {            people[p]=0;                 flag--;    //待出圈的元素-1            count=0;   //重新开始数        }        if(p==n)       //这段代码就是让尾部连接头部            p=1;        else            p++;    }
  

  for(int i=1;i<n;i++)  //那个值不为0元素的下标的就是最后一个出圈的人的序号
  {
    if(people[i]!=0)
    {printf("目标为%d\n",i);break;}
  }

 

算法:约瑟夫环问题