Josephus问题：
一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩就离开，小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢？
#include
using namespace std;
void main()
{
    const int n=50;
    int child[n];
    int i,j,m,count=n;
    for(i=0;i         child[i]=i+1;//给小孩编号，1，2……
    cin>>m;
    for(i=0,j=0;;j++)
    {
        if(j==n)j=0;//从第一个小孩开始重新数
        if(child[j])i++;//当数到一个还没有离开圈的小孩是i增加1，
        else continue;
        if(i==m)//此时说明又一次达到m值，这时又有一个小孩要离开圈了
        {
            //从新初始化
            count--;
            i=0;
            cout<             child[j]=0;
        }
        if(count==1)break;//只剩下一个小孩是就全部结束了
    }
    for(i=0;i         if(child[i])break;
        cout<<"第"<
}

Josephus问题的扩展：
题目：17个人围成圈，编号1——17，从第一号开始报数，报到3的倍数的人离开，一直数下去，直到最后只剩下一个。求此人的编号？

#include
using namespace std;
void main()
{
    const int n=17;
    int child[n];
    int i,j,count=n;
    for(i=0;i         child[i]=i+1;//给小孩编号，1，2……
    for(i=0,j=0;;j++)
    {
        if(j==n)j=0;//从第一个小孩开始从新数
        if(child[j])
            i++;//当数到一个还没有离开圈的小孩是i增加1，
        else continue;
        if(i%3==0)//此时说明又一次达到m值，这时又有一个小孩要离开圈了
        {
            //从新初始化
            count--;
            cout<             child[j]=0;
        }
        if(count==1)break;//只剩下一个小孩是就全部结束了
    }
    for(i=0;i         if(child[i])break;
        cout<<"第"< }

继续扩展：

问题来自电脑报bbs网站,

有k个好人和k个坏人。好人的编号是1到k，坏人的编号是k+1到2k。
从等一个人开始报数，数到M个人出列，然后从出列的人的下一个人重新开始报数，数到第M个出列.......
希望求出最小的M，能使k个坏人最先出列

输入
k(0输出
M

样例：
输入
4
输出
30

我的程序：不是很好，主要是因为直接从上面的程序改编过来的，

#include
using namespace std;

void main()
{
    const int n=28;
    int child[n];
    int i,j,k,m=1,count=0;
 cin>>k;
 
 if(k<=0||k>=14)
 {
  cout<<"You are wrong!\n";
  return ;
 }

 
 while(1)
 {
  for(i=0;i<2*k;i++)
   child[i]=i+1;//给这些人编号，1，2……
  
  for(i=0,j=0;;j++)
  {
   if(j==2*k)j=0;//从第一个人开始重新数
   if(child[j])i++;//当数到一个还没有离开圈的人时i增加1，
   else continue;
   if(i==m)//此时说明又一次达到m值，这时又有一个小孩要离开圈了
   {
            //重新初始化
    if(j

    count++;
    i=0;
    child[j]=0;
   }
   if(count==k) break;//坏人全部出列以后就结束
  }

  if(count  {
   count=0;
   m++;
   continue;
  }//重新初始化并把m的值增加一
  
  //说明已经取得了最小的m
  cout<<"满足条件的最小的M="<  break;
 }

}

评论