题目描述:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一 开始,任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报 数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
*需求分析
利用单向循环链表存储结构模拟此过程。程序输入、输出值均为正整数(其中人数限定<=30),程序的功能是按照出列的顺序印出各人的编号。
*测试数据:m=20,n=7,7个人的密码为:3,1,7,2,4,8,4;
*测试结果:出列顺序为6,1,4,7,2,3,5.
*附录(源程序):
//约瑟夫(Joseph)环
#include<iostream.h>
#include<conio.h>
//定义单链存储结构
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
void main()
{
int m,n,t[30],j(0); //定义初始报数上限值m、人数n
cout<<"输入初始报数上限值m(正整数):";
cin>>m;
cout<<"输入人数n(正整数,<=30):";
cin>>n;
cout<<"输入各人的密码(以空格符为分隔号):"<<endl;
for(int i=0;i<n;i++)
cin>>t[i];
LinkList p,head;
head=new LNode;
head->data=0;
head->next=0;
p=head;
//初始化单向循环链表
for(i=1;i<n;i++)
{
struct LNode *s=new LNode;
s->data=i;
//s->next=0;
p->next=s;
p=p->next;
}
p->next=head;
//处理出列顺序
while(p->data!=p->next->next->data&&j<m)
{
if(j==m-1){
int n=p->next->data;
m=t[n];
j=0;
cout<<n+1<<endl;
if(p->data==p->next->next->data)
break;
p->next=p->next->next;
}
if(p->data==p->next->next->data){
cout<<p->next->data+1<<endl; //倒数第二个出列者
break; }
p=p->next;
j++;
}
cout<<p->data+1<<endl; //最后一个出列者
//暂停
getch();
}