Posted on 2006-03-05 15:06
Tauruser 阅读(747)
评论(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);//递归调用
}
}