C++约瑟夫环问题：循环链表实现及多次游戏

本文将介绍如何使用C++的循环链表来解决经典的约瑟夫环问题，并实现多次游戏，每次游戏可以设置不同的报数密码。

约瑟夫环问题简介

约瑟夫环问题是一个古老的数学问题：n个人围成一圈，从第一个人开始报数，报到m的人出列，然后从出列的下一个人开始重新报数，如此循环，直到所有人出列。求解的目标是确定出列顺序。

循环链表实现c++#include using namespace std;

// 定义循环链表节点typedef struct LNode { int data; struct LNode* next;} LNode, * LinkList;

// 创建循环链表void createList(LinkList& head, int n) { head = new LNode; head->next = NULL; LNode* r = head; for (int i = 1; i <= n; i++) { LNode* p = new LNode; p->data = i; cout << p->data << ' '; p->next = NULL; r->next = p; r = p; } r->next = head->next; // 形成循环}

// 在末尾插入新节点void insertNode(LinkList& head, int num) { LNode* newNode = new LNode; newNode->data = num; newNode->next = head->next; head->next = newNode;}

// 约瑟夫环游戏void josephus(LinkList& head, int n, int m, LinkList& newList) { LNode* p = head->next; LNode* q; int num = 0; while (num < n) { for (int i = 1; i < m; i++) { q = p; p = p->next; } cout << p->data << ' '; // 输出出列的人 q->next = p->next; insertNode(newList, p->data); // 将出列的人插入到新队列 delete p; p = q->next; num++; }}

// 游戏完成后队列次序void josephus_game(LinkList& head, int n, int* passwords, int numPasswords) { LinkList newList = new LNode; newList->next = NULL; for (int i = 0; i < numPasswords; i++) { int m = passwords[i]; josephus(head, n, m, newList); cout << endl; head->next = newList->next; // 更新初始队列为新队列 newList->next = NULL; // 清空新队列 } delete newList;}

int main() { int n; cout << '请输入n：' << endl; cin >> n;

LinkList head = NULL;    createList(head, n);

int numPasswords;    cout << '请输入游戏遍数：' << endl;    cin >> numPasswords;

int* passwords = new int[numPasswords];    cout << '请输入每遍游戏的报数密码：' << endl;    for (int i = 0; i < numPasswords; i++) {        cin >> passwords[i];    }

josephus_game(head, n, passwords, numPasswords);

delete[] passwords;    return 0;}

代码解释

createList函数创建一个包含n个节点的循环链表。2. insertNode函数将一个新节点插入到链表的末尾。3. josephus函数模拟约瑟夫环游戏，将出列的人的节点插入到一个新的链表中。4. josephus_game函数实现多次游戏，每次游戏使用不同的报数密码，并将每次游戏后的队列次序输出。

总结

本文介绍了如何使用C++的循环链表来解决约瑟夫环问题，并实现了多次游戏，每次游戏可以设置不同的报数密码。该代码清晰易懂，方便读者理解和学习。