C++的編寫約瑟夫(josephus)環(huán)函數(shù)

2019-11-17 05:42:34

字體：大中小

供稿：網(wǎng)友

    約瑟夫(josephus)環(huán)是這樣的：假設(shè)有n個小孩坐成一個環(huán)，假如從第一個小孩開始數(shù)，假如數(shù)到m個小孩，則該小該離開，問最后留下的小孩是第幾個小孩？例如：總共有6個小孩，圍成一圈，從第一個小孩開始，每次數(shù)2個小孩，則游戲情況如下：
    小孩序號：1，2，3，4，5，6
    離開小孩序號：2，4，6，3，1
最后獲勝小孩序號：5

    這樣的問題，我可以先考慮輸入的內(nèi)容有哪些？輸出內(nèi)容有哪些？
        要求用戶輸入的內(nèi)容有：
         1、是小孩的個數(shù)，也就是n的值；
         2、是離開小孩的間隔是多少？也就是m的值。
         3、所有小孩的序號要求存在數(shù)組或者鏈表中，所以需要定義一個指針，這里我們用數(shù)組來存放小孩的序號。
        而要求輸出的內(nèi)容是：
         1、離開小孩的序號；
         2、最后留下小孩的序號；
所以，根據(jù)上面分析輸入輸出參數(shù)，我們考慮離開小孩的序號可以直接輸出，這樣可以使函數(shù)的復(fù)雜性。那么函數(shù)定義如下：
//輸入?yún)?shù)：
//Childs為指向一個整形指針，指向保存小孩數(shù)組的首地址；
//n為小孩的個數(shù)；
//m為數(shù)小孩的個數(shù)；
int Josephus(int *Child,int n,int m)
{
int i=-1,j=0,k=1;
//開始數(shù)小孩，只到留下一個小孩
while(1)
{
//數(shù)m個小孩
  for(j=0;j<m;)
  {
   i=(i+1)%n;    //取下標(biāo)加1的模，當(dāng)i的值在0到n-1之間循環(huán)
   if(Child[i]!=-1) //小孩在環(huán)中則數(shù)數(shù)有效；
    j++;

  }

   if(k==n)                        //假如k==n則表示，此時數(shù)組中只留下一個小孩，
    break;                          //序號為Child[i]中的值，跳出循環(huán);
   cout<<Child[i]<<",";  //輸出離開小孩的序號;

   Child[i]=-1;               //離開的小孩用-1作標(biāo)記
   k=k+1;

}
cout<<endl;
return(Child[i]);    //返回最獲勝小孩的序號
}

完整的程序，在VC6中調(diào)試通過。
//-----------------------------------------------------------
#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]);
}

上一篇：C/C++中的日期和時間

下一篇：C++基礎(chǔ)：怎樣判斷某一文件是否存在