约瑟夫问题c++

约瑟夫问题是一个经典的问题，可以使用循环链表来解决。以下是使用 C++ 语言实现的代码：

#include <iostream>
using namespace std;

// 定义循环链表节点结构体
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

// 定义函数实现约瑟夫问题
int josephus(int n, 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 = NULL;
    while (cur->next != cur) {
        for (int i = 0; i < m-1; i++) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        delete cur;
        cur = prev->next;
    }
    int winner = cur->val;
    delete cur;
    return winner;
}

int main() {
    int n = 5, m = 3;
    int winner = josephus(n, m);
    cout << "The winner is: " << winner << endl;
    return 0;
}

在上述代码中，我们首先构造了一个循环链表，然后从链表头开始报数，每数到第 $m$ 个节点就将该节点删除，直到只剩下一个节点为止。最后返回剩下的节点的值即可。

注意，在链表中删除一个节点时，需要先保存该节点的前一个节点，以便在删除后将前一个节点与后一个节点相连。