约瑟夫环游戏：单链表实现

约瑟夫环游戏：单链表实现

题目描述

有M个人，编号分别为1到M，玩约瑟夫环游戏，最初时按编号顺序排成队列；每遍游戏开始时，有一个正整数报数密码N，队列中人依次围坐成一圈，从队首的人开始报数，报到N的人出列，然后再从出列的下一人开始重新报数，报到N的人出列；重复这一过程，直至所有人出列，完成一遍游戏，所有出列的人形成新队列；游戏可能玩很多遍，每遍有新报数密码。求若干遍游戏完成后队列次序。本题要求使用单链表实现，程序要求采用模块化设计，格式规范，有合适注解。

输入描述

每个测试用例包含若干个正整数（至少1个），第一个正整数为玩游戏人数M，后续每个正整数为每遍游戏报数密码；报数密码可能为1

输出描述

每个测试用例结果占一行，每个编号占4位。

样例输入

10 3 5 2

样例输出

4 6 5 2 9 1 3 7 8 10

#include <iostream>
#include <iomanip>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(NULL) {}
};

ListNode* createList(int M) {
    ListNode* head = new ListNode(1);
    ListNode* cur = head;
    for (int i = 2; i <= M; i++) {
        ListNode* newNode = new ListNode(i);
        cur->next = newNode;
        cur = newNode;
    }
    cur->next = head;
    return head;
}

void josephus(ListNode* head, int N) {
    ListNode* prev = head;
    while (prev->next != head) {
        for (int i = 1; i < N; i++) {
            prev = prev->next;
        }
        ListNode* cur = prev->next;
        prev->next = cur->next;
        cout << setw(4) << setfill(' ') << cur->data;
        delete cur;
    }
    cout << setw(4) << setfill(' ') << prev->data;
}

void playJosephusGame(int M, int* passwords, int numPasswords) {
    ListNode* head = createList(M);
    for (int i = 0; i < numPasswords; i++) {
        josephus(head, passwords[i]);
        cout << endl;
    }
}

int main() {
    int M;
    cin >> M;

    int numPasswords;
    cin >> numPasswords;

    int* passwords = new int[numPasswords];
    for (int i = 0; i < numPasswords; i++) {
        cin >> passwords[i];
    }

    playJosephusGame(M, passwords, numPasswords);

    delete[] passwords;
    return 0;
}

这个程序使用单链表实现了约瑟夫环游戏。首先，通过createList函数创建了一个包含M个人的循环单链表。然后，通过josephus函数模拟了游戏的过程。在每遍游戏中，根据报数密码N，从队列首开始报数，每报到N的人出列，直到所有人都出列。最后，通过playJosephusGame函数完成了多遍游戏的过程，根据输入的报数密码进行游戏，并输出每遍游戏完成后的队列次序。

以上代码是根据题目要求编写的单链表版本的约瑟夫环游戏程序。输入包含多个测试用例，每个测试用例以玩游戏的人数M开始，后续是每遍游戏的报数密码。每个测试用例的结果占一行，输出每个人的编号。你可以将以上代码复制到你的代码编辑器中，然后根据输入样例进行测试。