- 习题集P79。编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
- 问题输入
输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。
- 问题输出
用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
int a[N]; // 用于存储每个人的密码值
typedef struct Node{
int data; // 存储该节点代表的人的编号
struct Node *next; // 指向下一个节点的指针
}node;
// 约瑟夫问题模拟函数
void josephusProblem(int n, int m) {
node *head=NULL,*p=NULL,*r=NULL; // 头指针、当前指针和前驱指针
head=(node *)malloc(sizeof(node)); // 创建头节点
if(head==NULL){
cout<<"Memory error"<<endl; // 内存分配失败
return ;
}
head->data=1; // 第一个节点代表的人的编号为1
head->next=NULL;
p=head; // 当前指针指向头节点
for(int i=2;i<=n;i++){
r=(node *)malloc(sizeof(node)); // 创建新节点
r->data=i; // 节点代表的人的编号为i
r->next=NULL;
p->next=r; // 将新节点插入到链表中
p=r;
}
p->next=head; // 尾节点指向头节点，形成循环链表
p=head; // 当前指针重新指向头节点
int cnt=0;
while(p->next!=p){ // 当链表中只剩下一个节点时结束循环
for(int i=1;i<=m-1;i++){
r=p;
p=p->next; // 循环m-1次，更新前驱和当前节点
}
cout<<p->data<<endl; // 输出出列的人的编号
m=a[p->data]; // 根据当前出列的人的密码值更新报数值m
r->next=p->next; // 删除出列的节点AAAAAAAA
p=p->next; // 更新当前节点为下一个节点
cnt++;
}
cout<<p->data<<endl; // 输出最后剩下的人的编号
return ;
}
int main() {
int n;
cin>>n; // 输入人数
for(int i=1;i<=n;i++)cin>>a[i]; // 输入每个人的密码值
int st;
cin>>st; // 输入初始报数上限值
a[0]=st; // 设置初始报数上限值
josephusProblem(n,st); // 调用约瑟夫问题模拟函数
return 0;
}