Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
/////////////////////////////////////////////////////////////////////////////
///          算法与数据结构 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);//递归调用
    }

}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理