Posted on 2006-03-05 15:17
Tauruser 閱讀(524)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構
/**//////////////////////////////////////////////////////////////////////////////
/// 算法與數據結構 Josephus 問題解決方案 ///
/// 用方法二遞歸進行出列運算源程序 ///
/////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
int n,s,m,count;//全局變量；count用來控制當前出列表的位置
int *seat,*outlist;//座位表與出列表
void out(int n,int s,int m,int *seat,int *outlist);//遞歸函數
int main()
{
//參數輸入
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];
//將變量轉化為系統內部index base 0;
s--;
//對各座位上people的編號,出列表全清為零
for(int i(0);i<n;i++)
{
seat[i]=i+1;
outlist[i]=0;
}
//遞歸進行出列運算
out(n,s,m,seat,outlist);
//輸出出列運算結果
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;//已經出列設置標志零
out(n,s+1,m,seat,outlist);
}
}