Posted on 2006-03-05 15:17
Tauruser 阅读(498)
评论(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);
}
}