明辉站/网站教程/内容

C++的编写约瑟夫(josephus)环函数

网站教程2024-02-12 阅读
[摘要]约瑟夫(josephus)环是这样的:假设有n个小孩坐成一个环,假如从第一个小孩开始数,如果数到m个小孩,则该小该离开,问最后留下的小孩是第几个小孩?例如:总共有6个小孩,围成一圈,从第一个小孩开始,每次数2个小孩,则游戏情况如下: 小孩序号:1,2,3,4,5,6 离开小孩序号:2,...
    约瑟夫(josephus)环是这样的:假设有n个小孩坐成一个环,假如从第一个小孩开始数,如果数到m个小孩,则该小该离开,问最后留下的小孩是第几个小孩?例如:总共有6个小孩,围成一圈,从第一个小孩开始,每次数2个小孩,则游戏情况如下:
    小孩序号:1,2,3,4,5,6
    离开小孩序号:2,4,6,3,1
最后获胜小孩序号:5

    这样的问题,我可以先考虑输入的内容有哪些?输出内容有哪些?
        要求用户输入的内容有:
         1、是小孩的个数,也就是n的值;
         2、是离开小孩的间隔是多少?也就是m的值。
         3、所有小孩的序号要求存在数组或者链表中,所以需要定义一个指针,这里我们用数组来存放小孩的序号。
        而要求输出的内容是:
         1、离开小孩的序号;
         2、最后留下小孩的序号;
所以,根据上面分析输入输出参数,我们考虑离开小孩的序号可以直接输出,这样可以使函数的复杂性。那么函数定义如下:
//输入参数:
//Childs为指向一个整形指针,指向保存小孩数组的首地址;
//n为小孩的个数;
//m为数小孩的个数;
int Josephus(int *Child,int n,int m)
{
int i=-1,j=0,k=1;
//开始数小孩,只到留下一个小孩
while(1)
{
//数m个小孩
  for(j=0;j<m;)
  {
   i=(i+1)%n;    //取下标加1的模,当i的值在0到n-1之间循环
   if(Child[i]!=-1) //小孩在环中则数数有效;
    j++;
   
  }

   if(k==n)                        //如果k==n则表示,此时数组中只留下一个小孩,
    break;                          //序号为Child[i]中的值,跳出循环;
   cout<<Child[i]<<",";  //输出离开小孩的序号;

   Child[i]=-1;               //离开的小孩用-1作标记
   k=k+1;

}
cout<<endl;
return(Child[i]);    //返回最获胜小孩的序号
}

完整的程序,在VC6中调试通过。
//-----------------------------------------------------------
#include<iostream.h>
int Josephus(int *Child,int n,int m);
void main()
{
int *allChild,j,k,l;
cin>>j>>k;

  if((allChild= new int[j])!=NULL)
  {
    for(l=0;l<j;l++)
    {  
     cout<<l+1<<",";
     allChild[l]=l+1;
    }
    cout<<endl;
    cout<<Josephus(allChild,j,k);
  }
}

int Josephus(int *Child,int n,int m)
{
int i=-1,j=0,k=1;
while(1)
{
  for(j=0;j<m;)
  {
   i=(i+1)%n;    
   if(Child[i]!=-1)
    j++;
   
  }

   if(k==n)                        
    break;                        
   cout<<Child[i]<<",";  

   Child[i]=-1;         
   k=k+1;

}
cout<<endl;
return(Child[i]);    
}

……

相关阅读