c++约瑟夫问题思路

约瑟夫问题是一个经典的数学问题，具体描述为：已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求出列顺序。

解决这个问题的一种常见方法是使用循环链表。具体思路如下：

1. 创建一个循环链表，包含 n 个节点，每个节点表示一个人。
2. 从第 k 个节点开始，依次遍历链表，数到第 m 个节点就将其删除。
3. 重复步骤 2 直到链表为空，每次删除的节点即为出列的顺序。

C++代码实现如下：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

int josephus(int n, int k, int m) {
    Node* head = new Node(1);
    Node* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = head;

    Node* prev = cur;
    cur = head;
    while (cur->next != cur) {
        for (int i = 1; i < k; i++) {
            prev = cur;
            cur = cur->next;
        }
        for (int i = 1; i < m; i++) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        cout << cur->val << " ";
        Node* tmp = cur;
        cur = prev->next;
        delete tmp;
    }
    int ans = cur->val;
    delete cur;
    return ans;
}

int main() {
    int n = 5, k = 2, m = 3;
    cout << josephus(n, k, m) << endl; // 输出：3 1 5 2
    return 0;
}