详解基于C++实现约瑟夫环问题的三种解法

约瑟夫问题

约瑟夫问题是一个经典的问题，是一个圆圈里面有$n$个数字，从中每次删除第$m$个数字，求出每次删除的数字。简单的说，约瑟夫问题就是$n$个人围成一圈，从第一个人开始报数，报到$m$的人出圈，直到计算到最后一个人。

解法一：使用递推（模拟游戏过程）

思路：利用递归的思想模拟即可。假如最后剩下一个数据，则保留该数据，否则位置为 $s=(f+m)\ mod\ i $，$f$表示上一轮已经被删除数字的位置，$i$表示上一轮剩余数字个数，$m$为给定的数字。

代码：

int Josephus(int n, int m) {
    if (n == 1) {
        return 1;
    }
    return (Josephus(n - 1, m) + m - 1) % n + 1;
}

递归较为简便，但是处理的数据规模过大，会引起栈溢出等问题。

解法二：循环链表

思路：使用循环链表模拟过程，进行删除操作，直到链表剩下一个节点。

代码：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

int Josephus(int n, int m) {
    Node* head = new Node{1, nullptr};
    Node* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node{i, nullptr};
        cur = cur->next;
    }
    cur->next = head;
    while (head->next != head) {
        int cnt = m % (n--);
        if (cnt == 0) {
            cnt = n;
        }
        Node* pre;
        for (pre = head; pre->next != head; pre = pre->next) {
            if (--cnt == 0) {
                break;
            }
        }
        Node* temp = pre->next;
        pre->next = temp->next;
        head = temp->next;
        delete temp;
    }
    int res = head->val;
    delete head;
    return res;
}

int main() {
    cout << Josephus(5, 3) << endl;    // 输出3
    cout << Josephus(8, 4) << endl;    // 输出6
    return 0;
}

解法三：数学归纳

思路：可以通过利用数学归纳法来证明一种对称性，然后根据对称性来推导出约瑟夫环问题的答案。设 $f(n)$ 表示当有$n$个人时最后留下的人在数列中的位置，则：

当 $n=1$ 时，$f(1)=0$。

当 $n>1$ 时，将编号改为从 $0$ 开始，第一个人编号为 $0$ ，对 $n-1$ 取模，设结果为 $x$，则：

$$ f(n,m)=\left{\begin{aligned} & 0 & n=1 \ & \left(f(n-1,m)+m\right)\ \% \ n & n>1 \end{aligned}\right. $$

代码：

int Josephus(int n, int m) {
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res = (res + m) % i;
    }
    return res + 1;
}

示例说明

例如，有 $5$ 个人 $(0, 1, 2, 3, 4)$ 依次报数，编号为 $0$ 的人从 $1$ 开始报数，假设报到 $3$ 的人出局，依次出局的顺序为 $2, 0, 4, 3$，因此最后剩下的是编号为 $1$ 的人。

可以通过调用以下代码进行验证：

cout << Josephus(5, 3) << endl;

输出为 $3$。