用C++写代码使用类带注释。 用线性列表来解重新排序问题。输入nm。n个人围坐在一张圆桌旁。随机令某个人标记为1开始按照顺时针增序计数第二个人会数到2数到m的人成为第一个新阶数而后被移除；原本的第m+1人被重新计数为第1人重新开始顺时针增序计数第二次数到m的人是成为第二个新阶数并被移除。持续循环直到所有n个人被重新排序为新阶数。 可验证当n=8m=4时得到的新阶数为48521376。如果出现其他答

#include using namespace std;

class Node { // 定义链表节点类 public: int data; // 数据域 Node* next; // 指针域 Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} // 构造函数 };

class CircularList { // 定义循环链表类 private: Node* tail; // 尾指针 int size; // 链表长度 public: CircularList() : tail(nullptr), size(0) {} // 构造函数 ~CircularList(); // 析构函数 void insert(int pos, int val); // 插入节点 int remove(int pos); // 删除节点 int getSize() const { return size; } // 获取链表长度 void print() const; // 打印链表 int josephus(int m); // 约瑟夫问题求解 };

CircularList::~CircularList() { // 析构函数 while (tail != nullptr) { // 循环删除节点，直到链表为空 Node* temp = tail->next; // 记录链表头节点 tail->next = temp->next; // 尾节点指向第二个节点，即原头节点的下一个节点 delete temp; // 删除头节点 } }

void CircularList::insert(int pos, int val) { // 在指定位置插入节点 if (pos < 0 || pos > size) { // 插入位置非法 cout << "插入位置非法！" << endl; return; } if (tail == nullptr) { // 链表为空，新建节点作为头节点 tail = new Node(val); tail->next = tail; // 头节点的下一个节点指向自身 } else if (pos == 0) { // 插入位置为头节点之前，需移动尾指针 tail->next = new Node(val, tail->next); } else { // 插入位置为中间或末尾，需移动指针 Node* p = tail->next; for (int i = 0; i < pos - 1; i++) { // 移动指针到插入位置的前一个节点 p = p->next; } p->next = new Node(val, p->next); if (pos == size) { // 插入位置为末尾，需移动尾指针 tail = tail->next->next; } } size++; // 链表长度加1 }

int CircularList::remove(int pos) { // 删除指定位置的节点 if (pos < 0 || pos >= size) { // 删除位置非法 cout << "删除位置非法！" << endl; return -1; } int res; if (tail->next == tail) { // 链表只有一个节点，删除后置为空链表 res = tail->data; delete tail; tail = nullptr; } else if (pos == 0) { // 删除头节点，需移动尾指针 Node* temp = tail->next; tail->next = temp->next; res = temp->data; delete temp; } else { // 删除中间或末尾节点 Node* p = tail->next; for (int i = 0; i < pos - 1; i++) { // 移动指针到删除位置的前一个节点 p = p->next; } Node* temp = p->next; p->next = temp->next; res = temp->data; delete temp; if (pos == size - 1) { // 删除末尾节点，需移动尾指针 tail = p; } } size--; // 链表长度减1 return res; }

void CircularList::print() const { // 打印链表 if (tail == nullptr) { cout << "链表为空！" << endl; return; } Node* p = tail->next; while (p != tail) { // 循环打印链表节点 cout << p->data << " "; p = p->next; } cout << p->data << endl; // 打印尾节点 }

int CircularList::josephus(int m) { // 约瑟夫问题求解 Node* p = tail; // 初始指向尾节点 while (size > 1) { // 链表长度大于1时循环 for (int i = 0; i < m - 1; i++) { // 循环m-1次，找到第m个节点的前一个节点 p = p->next; } int res = remove((p == tail) ? 0 : 1); // 删除第m个节点，记下节点数据 if (p == tail) { // 如果删除的是尾节点，需移动尾指针 tail = p->next; } p = p->next; // 指针指向下一个节点，从下一个节点开始重新计数 cout << res; // 打印删除的节点数据 } cout << endl; return tail->data; // 返回最后剩余的节点数据 }

int main() { int n, m; cin >> n >> m; CircularList list; for (int i = 1; i <= n; i++) { // 初始化链表 list.insert(i - 1, i); } int res = list.josephus(m); // 求解约瑟夫问题 cout << "新阶数为：" << res << endl; return 0; }