Posted on 2006-03-05 15:06
Tauruser 閱讀(762)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構
/**//////////////////////////////////////////////////////////////////////////////
/// 算法與數據結構 Josephus 問題解決方案 ///
/// 用方法一遞歸進行出列運算源程序 ///
/////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
int n,s,m;//設置全局變量
int *seat;//全局變量用于存儲當前各位置上的人;seat no. base 0;
void out(int n,int s,int m,int *seat);//用于進行出列的遞歸函數
int main()
{
//參數輸入
cout<<"please input n:";
cin>>n;
cout<<"please input s:";
cin>>s;
cout<<"plesae input m:";
cin>>m;
//分配座位表空間
seat=new int[n];
//對各座位上people的編號
for(int i(0);i<n;i++)
{
seat[i]=i+1;
}
//將變量轉化為系統內部index base 0;
s--;
//方便需要
m--;
//進行出列運算
out(n,s,m,seat);
//輸出出列運算結果
cout<<"the out people list is:";
for(int i=n-1;i>=0;i--)
cout<<"P"<<seat[i]<<" ";
//釋放座位數組空間
delete []seat;
return 0;
}
void out(int n,int s,int m,int *seat)//用于進行出列的遞歸函數
{
int temp;
if(n==1)//遞歸退出條件
return;
else{
s=(s+m)%(n);//第S位被OUT,s base 0；
if(s!=n-1)//當s=n-i-1時并不需要進行移位
{
temp=seat[n-1];
seat[n-1]=seat[s];
for(int j=s;j<n-2;j++)
seat[j]=seat[j+1];
seat[n-2]=temp;
}
out(n-1,s,m,seat);//遞歸調用
}
}