Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Josephus问题非递归方法１解决办法

Posted on 2006-03-05 15:00 Tauruser 阅读(844) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构

 

 1/////////////////////////////////////////////////////////////////////////////
 2///    　　　　  算法与数据结构　Josephus 问题解决方案　　　　　　　　　　///
 3///              　用方法一非递归进行出列运算源程序　　　　　　　　　　   ///
 4/////////////////////////////////////////////////////////////////////////////
 5
 6
 7#include <iostream>
 8using namespace std;
 9
10int n,s,m;//设置全局变量
11int *seat;//数组指针，指向各座位，注意这里以系统内部index base 0为准。
12int main()
13{
14    //参数输入
15    cout<<"please input n:";
16    cin>>n;
17    cout<<"please input s:";
18    cin>>s;
19    cout<<"plesae input m:";
20    cin>>m;
21    //分配座位表空间
22    seat=new int[n];    
23    //对各座位上people的编号
24    for(int i(0);i<n;i++)
25    {
26        seat[i]=i+1;
27    }
28
29    
30    //将变量转化为系统内部index base 0;
31    s--;
32    
33    //方便需要
34    m--;
35
36    int temp;
37
38    for(int i=0;i<n;i++)
39    {
40        s=(s+m)%(n-i);//第S位被OUT,s base 0；
41        if(s!=n-i-1)//当s=n-i-1时并不需要进行移位
42        {
43            temp=seat[n-i-1];
44            seat[n-i-1]=seat[s];
45            for(int j=s;j<n-i-2;j++)
46                seat[j]=seat[j+1];
47            seat[n-i-2]=temp;
48        }
49        
50    }
51    
52    //输出出列顺序表
53    cout<<"the out people list is:";
54    for(int i=n-1;i>=0;i--)
55        cout<<"P"<<seat[i]<<" ";
56    
57    //释放座位数组空间
58    delete []seat;
59
60    return 0;
61}

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