约瑟夫问题模拟

整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

• 习题集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;
}