（1）我的實(shí)驗(yàn)報(bào)告
約瑟夫環(huán)  實(shí)驗(yàn)

實(shí)驗(yàn)內(nèi)容：

編號為：1，2，3...n個(gè)人按順時(shí)針方向圍座成一圈，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m的值，從他在順時(shí)針方向上的下一個(gè)人開始報(bào)數(shù)，如此下去，直至所有人全部列出為止。設(shè)計(jì)一個(gè)程序求出出列的順序。

測試數(shù)據(jù)
m的初值位20，n=7，7個(gè)人的密碼是：3，1，7，2，4，8，4，首先m值為6（正確輸出為6，1，4，7，2，3，5）

方法一：  數(shù)組

#include<iostream.h>

void main()
{
//建立小孩數(shù)組
const int n=7; //小孩個(gè)數(shù)
int interval=20;  //每次第interval個(gè)小孩，讓該小孩離開，interval的初值為20
int a[n];   //小孩數(shù)組

//建立小孩數(shù)組，并設(shè)定密碼；
cout<<"please input codes";
for(int i=0;i<7;i++)
   cin>>a[i];   //輸入7個(gè)小孩的序號 1 2 3...7
   

//將全體小孩的序號和密碼輸出，以便比較
for( i=0;i<n;i++)
{
  cout<<i+1<<",";
  cout<<a[i]<<",";
  cout<<endl;
}

int k=1;  //標(biāo)識處理第k個(gè)小孩    
    i=-1;  //數(shù)組下標(biāo)（下一個(gè)值0就是第一個(gè)小孩的下標(biāo)）

//處理獲勝前的小孩
while(1)
{
 //在interval圈中的小孩，如果被標(biāo)記為0則出列，否則留在interval的圈中
for(int j=0;j<interval;)
{ 
 i=(i+1)%n;
 if(a[i]!=0)  
     j++;
}

if(k==n)  break;  //該小孩是最后一個(gè)，則跳出循環(huán)，最后一個(gè)就是勝利者

cout<<i+1<<"," ;  //輸出小孩依次出列的序號 
interval=a[i];     //將第出列小孩的密碼作為下依次interval的值
a[i]=0;          //標(biāo)記該小孩已經(jīng)離開
k++;              //進(jìn)入下一個(gè)圈中
}

cout<<"\nNo."<<i+1<<"boy's won.\n";
}


程序運(yùn)行結(jié)果：

please input codes3 1 7 2 4 8 4
1,3,
2,1,
3,7,
4,2,
5,4,
6,8,
7,4,
6,1,4,7,2,3,
No.4boy's won.
Press any key to continue


實(shí)驗(yàn)分析：
  
1.程序中小孩的個(gè)數(shù)用常量n來定義，這樣數(shù)組定義的大小就可以用次常量來表示。用一個(gè)循環(huán)給小孩編號，依次為1，2...。不管小孩有幾個(gè)，小孩的編號只與小孩的個(gè)數(shù)有關(guān)

2.在處理離開小孩的循環(huán)前，初始化正在處理第一個(gè)小孩的給k，初始化數(shù)組下標(biāo)為-1，因?yàn)橄乱粋€(gè)值0下標(biāo)表示數(shù)組的第一個(gè)元素，即起始第一個(gè)小孩

3.在while循環(huán)中的for循環(huán)完成數(shù)interval個(gè)小孩的工作。數(shù)組中含有離開小孩和未離開小孩，標(biāo)記為0的是離開的小孩，否則，數(shù)組元素的值是小孩的編號。因此，往前數(shù)一下，須確認(rèn)該小孩含有非0值。

4.下標(biāo)的移動(dòng)很重要，值加1是下一個(gè)下標(biāo)，但是有可能越過數(shù)組的邊界，所以用“加1取模”發(fā)保證下標(biāo)在數(shù)組范圍內(nèi)循環(huán)


實(shí)驗(yàn)小結(jié)
程序每次處理小孩離開的時(shí)候，都要遍利整個(gè)數(shù)組，所以效率比較低。


（2）鏈表解法 

//******************************************************
//                  Josephus問題解法二       ***********
//                  Jose2.cpp                ***********
//******************************************************

#include <iostream.h>
#include <iomanip.h>

struct jose    //小孩結(jié)點(diǎn)
{
int data;   //小孩序號
int code;   //小孩密碼
jose* next;  
};

void main()
{
//賦初值
int num,interval=20;   //初始interval為20
cout<<"please input the number of boys,\n";   //小孩數(shù)
   cin>>num;
cout<<"please input the codes" ;
for(int i=0;i<num;i++)
   cin>>jose.code ;

//建立小孩結(jié)構(gòu)數(shù)組
jose* pJose=new jose[num];  // 從堆內(nèi)分配空間  pJose指數(shù)組向頭結(jié)點(diǎn)
jose* pCurrent=pJose ;  //當(dāng)前結(jié)點(diǎn)指針，pCurrent為當(dāng)前指針，初始值也指向頭結(jié)點(diǎn)

//初始化結(jié)構(gòu)數(shù)組：構(gòu)成環(huán)鏈，小孩編號、密碼。輸出編號
int itemsInLine=0;  //輸出項(xiàng)數(shù)

for( i=1;i<=num;i++)
{   
 pCurrent->next=pJose+i%num  ;  //鏈到下一個(gè)元素，構(gòu)成鏈表。
 pCurrent->data=i;               //當(dāng)前數(shù)據(jù)域data為小孩的序號 1，2，3...
 pCurrent=pCurrent->next;     // 當(dāng)前指針向下一個(gè)結(jié)點(diǎn)移動(dòng)
 if(itemsInLine++ %10==0)       //輸出格式控制
      cout<<endl;
cout<<setw(4)<<i;
}    //pCurrent此時(shí)等于pJose 
itemsInLine=0;

jose* pivot;   //鏈表哨兵 用于
pCurrent=&pJose[num-1];    //下一個(gè)就是數(shù)組第一個(gè)元素pJose[0]，此時(shí)當(dāng)前指針指向最后一個(gè)結(jié)點(diǎn)

while(pCurrent->next!=pCurrent)  //當(dāng)下一個(gè)結(jié)點(diǎn)不是當(dāng)前結(jié)點(diǎn)循環(huán)，（如果是，表明是最后一個(gè)結(jié)點(diǎn) ）
{ //處理未獲勝前（interval的范圍內(nèi)）的所有小孩
 for(int j=0;j<interval;j++)   
{
 pivot=pCurrent;   //讓哨兵指針為當(dāng)前指針
 pCurrent=pivot->next;  //當(dāng)前指針為當(dāng)前哨兵指針的后繼
}

if(itemsInLine++ %10==0)    //輸出小孩
  cout<<endl;
cout<<setw(4)<<pCurrent->data;
pivot->next=pCurrent->next; //小孩脫鏈 當(dāng)前指針的后繼給哨兵指針，既跳過當(dāng)前指針（指向的是要?jiǎng)h除的結(jié)點(diǎn)）
interval=pCurrent->code;    //當(dāng)前指針的數(shù)據(jù)域的code為小孩的密碼，將作為下一個(gè)interval的值
pCurrent=pivot;       //開始下一個(gè)循環(huán)
}

cout<<"\n\nthe winner is"
    <<pCurrent->data<<endl;   //獲勝者

delete[]pJose;   //返回堆空間

}// end of main()