Posted on 2006-03-05 15:17
Tauruser 閱讀(517)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結(jié)構(gòu)
/**//////////////////////////////////////////////////////////////////////////////
/// 算法與數(shù)據(jù)結(jié)構(gòu) Josephus 問題解決方案 ///
/// 用方法二遞歸進(jìn)行出列運(yùn)算源程序 ///
/////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
int n,s,m,count;//全局變量；count用來控制當(dāng)前出列表的位置
int *seat,*outlist;//座位表與出列表
void out(int n,int s,int m,int *seat,int *outlist);//遞歸函數(shù)
int main()
{
//參數(shù)輸入
count=0;
cout<<"please input n:";
cin>>n;
cout<<"please input s:";
cin>>s;
cout<<"plesae input m:";
cin>>m;
//分配座位表與出列表空間
seat=new int[n];
outlist=new int[n];
//將變量轉(zhuǎn)化為系統(tǒng)內(nèi)部index base 0;
s--;
//對各座位上people的編號(hào),出列表全清為零
for(int i(0);i<n;i++)
{
seat[i]=i+1;
outlist[i]=0;
}
//遞歸進(jìn)行出列運(yùn)算
out(n,s,m,seat,outlist);
//輸出出列運(yùn)算結(jié)果
cout<<"the out people list is:";
for(int i=0;i<n;i++)
cout<<"P"<<outlist[i]<<" ";
//釋放座位表與出列表空間
delete []seat;
delete []outlist;
return 0;
}
void out(int n,int s,int m,int *seat,int *outlist)
{
if(count==n) return;
else
{
s--;
for(int i(0);i<m;i++)
{
s++;
if(s==n) s=0;
if(seat[s]==0) i--;
}
outlist[count]=seat[s];//送入出列表
count++;
seat[s]=0;//已經(jīng)出列設(shè)置標(biāo)志零
out(n,s+1,m,seat,outlist);
}
}