约瑟夫环 实验.txt

其中一部分是自己写得,一部分是摘录的,希望站长能批准,我以后一定多多努力上传!

约瑟夫环  实验

实验内容：

编号为：1，2，3...n个人按顺时针方向围座成一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m的值，从他在顺时针方向上的下一个人开始报数，如此下去，直至所有人全部列出为止。设计一个程序求出出列的顺序。

测试数据
m的初值位20，n=7，7个人的密码是：3，1，7，2，4，8，4，首先m值为6（正确输出为6，1，4，7，2，3，5）

方法一：  数组

#include<iostream.h>

void main()
{
//建立小孩数组
const int n=7; //小孩个数
int interval=20;  //每次第interval个小孩，让该小孩离开，interval的初值为20
int a[n];   //小孩数组

//建立小孩数组，并设定密码；
cout<<"please input codes";
for(int i=0;i<7;i++)
   cin>>a[i];   //输入7个小孩的序号 1 2 3...7
   

//将全体小孩的序号和密码输出，以便比较
for( i=0;i<n;i++)
{
  cout<<i+1<<",";
  cout<<a[i]<<",";
  cout<<endl;
}

int k=1;  //标识处理第k个小孩    
    i=-1;  //数组下标（下一个值0就是第一个小孩的下标）

//处理获胜前的小孩
while(1)
{
 //在interval圈中的小孩，如果被标记为0则出列，否则留在interval的圈中
for(int j=0;j<interval;)
{ 
 i=(i+1)%n;
 if(a[i]!=0)  
     j++;
}

if(k==n)  break;  //该小孩是最后一个，则跳出循环，最后一个就是胜利者

cout<<i+1<<"," ;  //输出小孩依次出列的序号 
interval=a[i];     //将第出列小孩的密码作为下依次interval的值
a[i]=0;          //标记该小孩已经离开
k++;              //进入下一个圈中
}

cout<<"\nNo."<<i+1<<"boy's won.\n";
}


程序运行结果：

please input codes3 1 7 2 4 8 4
1,3,
2,1,
3,7,
4,2,
5,4,
6,8,
7,4,
6,1,4,7,2,3,
No.4boy's won.
Press any key to continue


实验分析：
  
1.程序中小孩的个数用常量n来定义，这样数组定义的大小就可以用次常量来表示。用一个循环给小孩编号，依次为1，2...。不管小孩有几个，小孩的编号只与小孩的个数有关

2.在处理离开小孩的循环前，初始化正在处理第一个小孩的给k，初始化数组下标为-1，因为下一个值0下标表示数组的第一个元素，即起始第一个小孩

3.在while循环中的for循环完成数interval个小孩的工作。数组中含有离开小孩和未离开小孩，标记为0的是离开的小孩，否则，数组元素的值是小孩的编号。因此，往前数一下，须确认该小孩含有非0值。

4.下标的移动很重要，值加1是下一个下标，但是有可能越过数组的边界，所以用“加1取模”发保证下标在数组范围内循环


实验小结
程序每次处理小孩离开的时候，都要遍利整个数组，所以效率比较低。