Tauruser

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

}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理