实验报告.txt

约瑟夫环实验报告

（1）我的实验报告
约瑟夫环  实验

实验内容：

编号为：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取模”发保证下标在数组范围内循环


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


（2）链表解法 

//******************************************************
//                  Josephus问题解法二       ***********
//                  Jose2.cpp                ***********
//******************************************************

#include <iostream.h>
#include <iomanip.h>

struct jose    //小孩结点
{
int data;   //小孩序号
int code;   //小孩密码
jose* next;  
};

void main()
{
//赋初值
int num,interval=20;   //初始interval为20
cout<<"please input the number of boys,\n";   //小孩数
   cin>>num;
cout<<"please input the codes" ;
for(int i=0;i<num;i++)
   cin>>jose.code ;

//建立小孩结构数组
jose* pJose=new jose[num];  // 从堆内分配空间  pJose指数组向头结点
jose* pCurrent=pJose ;  //当前结点指针，pCurrent为当前指针，初始值也指向头结点

//初始化结构数组：构成环链，小孩编号、密码。输出编号
int itemsInLine=0;  //输出项数

for( i=1;i<=num;i++)
{   
 pCurrent->next=pJose+i%num  ;  //链到下一个元素，构成链表。
 pCurrent->data=i;               //当前数据域data为小孩的序号 1，2，3...
 pCurrent=pCurrent->next;     // 当前指针向下一个结点移动
 if(itemsInLine++ %10==0)       //输出格式控制
      cout<<endl;
cout<<setw(4)<<i;
}    //pCurrent此时等于pJose 
itemsInLine=0;

jose* pivot;   //链表哨兵 用于
pCurrent=&pJose[num-1];    //下一个就是数组第一个元素pJose[0]，此时当前指针指向最后一个结点

while(pCurrent->next!=pCurrent)  //当下一个结点不是当前结点循环，（如果是，表明是最后一个结点 ）
{ //处理未获胜前（interval的范围内）的所有小孩
 for(int j=0;j<interval;j++)   
{
 pivot=pCurrent;   //让哨兵指针为当前指针
 pCurrent=pivot->next;  //当前指针为当前哨兵指针的后继
}

if(itemsInLine++ %10==0)    //输出小孩
  cout<<endl;
cout<<setw(4)<<pCurrent->data;
pivot->next=pCurrent->next; //小孩脱链 当前指针的后继给哨兵指针，既跳过当前指针（指向的是要删除的结点）
interval=pCurrent->code;    //当前指针的数据域的code为小孩的密码，将作为下一个interval的值
pCurrent=pivot;       //开始下一个循环
}

cout<<"\n\nthe winner is"
    <<pCurrent->data<<endl;   //获胜者

delete[]pJose;   //返回堆空间

}// end of main()