约瑟夫问题（Josephus Problem）是一个著名的数学和算法问题。以下为您提供该问题的数学递推公式推导、严谨的数学证明，以及基于 C++11 的高效算法实现。

一、 数学模型与递推公式

为了简化数学运算（尤其是模运算），通常推荐使用 0-indexed（从 0 开始编号） 的方式来建立数学模型。

1. 问题重述

有 $n$ 个人，编号为 $0, 1, 2, \dots, n-1$，排成一个圈。从编号为 $0$ 的人开始报数，每次报到 $k$ 的人被淘汰，然后从下一个人开始重新报数，重复此过程，直到最后只剩一个人。求最后幸存者的编号。

设 $J(n, k)$ 为 $n$ 个人、报数间隔为 $k$ 时的幸存者编号（0-indexed）。

2. 递推公式

• 基础情况（Base Case）：当只有 1 个人时，幸存者必然是这个人。 $$J(1, k) = 0$$
• 递推步骤（Recurrence Relation）：当有 $n$ 个人时，其幸存者编号可由 $n-1$ 个人的问题转化而来。 $$J(n, k) = (J(n-1, k) + k) \pmod n$$

注：如果需要 1-indexed（从 1 开始编号）的结果，只需将 0-indexed 的最终结果加 1 即可。即 $J_{1}(n, k) = J(n, k) + 1$。

二、 数学证明

我们通过新旧编号映射（Index Mapping）的方法来证明上述递推公式。

假设当前有 $n$ 个人，编号为 $0, 1, \dots, n-1$。 第一次报数时，报到 $k$ 的人被淘汰，该人的编号为 $(k - 1) \pmod n$。为了方便叙述，记此被淘汰者的编号为 $g$： $$g = (k - 1) \pmod n$$

当 $g$ 被淘汰后，剩下的 $n-1$ 个人组成的环如下（从被淘汰者的下一个人开始排列）： $$g+1, \ g+2, \ \dots, \ n-1, \ 0, \ 1, \ \dots, \ g-1$$

现在我们将这剩下的 $n-1$ 个人重新编号，使其成为一个规模为 $n-1$ 的新约瑟夫问题。新编号从 $0$ 到 $n-2$： * 原编号 $g+1$ 对应新编号 $0$ * 原编号 $g+2$ 对应新编号 $1$ * $\dots$ * 一般地，设某人在原环中的编号为 $x$（旧编号），在消去一人后的新环中的编号为 $y$（新编号）。

我们可以推导出新编号 $y$ 到旧编号 $x$ 的映射关系： $$x = (y + g + 1) \pmod n$$

将 $g = (k - 1) \pmod n$ 代入上式中： $$x = (y + k - 1 + 1) \pmod n$$ $$x = (y + k) \pmod n$$

根据定义，$n-1$ 个人进行约瑟夫游戏时的幸存者编号为 $J(n-1, k)$。这个值代表的是新编号。 为了找到这个幸存者在 含有 $n$ 个人的原始环（旧编号） 中的位置，我们直接应用上面的映射公式，将新编号 $y = J(n-1, k)$ 带入： $$J(n, k) = (J(n-1, k) + k) \pmod n$$

得证。

三、 特殊情况：$k = 2$ 的闭式解（Closed-form Solution）

当 $k=2$ 时，存在一个极其优美的二进制闭式解。 设 $n$ 可以表示为 $n = 2^m + l$，其中 $2^m$ 是小于或等于 $n$ 的最大 2 的幂次，且 $0 \le l < 2^m$。 在 1-indexed 的情况下，幸存者的编号为： $$J_{1}(n, 2) = 2l + 1$$

这也可以用二进制位移来解释：将 $n$ 的二进制表示循环左移一位，即可得到幸存者的 1-indexed 编号。

四、 C++11 代码实现

在实际编程中，如果 $n$ 非常大（例如 $10^7$ 以上），使用递归会导致栈溢出。因此，我们通常采用自底向上的迭代法，以 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度来解决该问题。

1. 通用情况（任意 $k$）的 $O(n)$ 迭代实现

#include <iostream>
#include <stdexcept>

/**
 * @brief 计算约瑟夫问题的幸存者编号（0-indexed）
 * @param n 总人数
 * @param k 报数间隔
 * @return int 幸存者的编号（从 0 开始）
 */
int josephus_0_indexed(int n, int k) {
    if (n <= 0 || k <= 0) {
        throw std::invalid_argument("n and k must be positive integers.");
    }

    int survivor = 0; // J(1, k) = 0
    for (int i = 2; i <= n; ++i) {
        survivor = (survivor + k) % i;
    }
    return survivor;
}

/**
 * @brief 计算约瑟夫问题的幸存者编号（1-indexed）
 * @param n 总人数
 * @param k 报数间隔
 * @return int 幸存者的编号（从 1 开始）
 */
int josephus_1_indexed(int n, int k) {
    return josephus_0_indexed(n, k) + 1;
}

int main() {
    int n = 5;
    int k = 3;

    try {
        int ans_0 = josephus_0_indexed(n, k);
        int ans_1 = josephus_1_indexed(n, k);

        std::cout << "人数 n = " << n << ", 报数间隔 k = " << k << "\n";
        std::cout << "幸存者编号 (0-indexed): " << ans_0 << "\n";
        std::cout << "幸存者编号 (1-indexed): " << ans_1 << "\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }

    return 0;
}

2. $k = 2$ 时的位运算高效实现（$O(1)$ 空间，$O(\log n)$ 或 $O(1)$ 时间）

利用 $J_1(n, 2) = 2l + 1$ 的性质，我们可以使用 C++ 的位运算以极高效率计算出结果：

#include <iostream>

/**
 * @brief 当 k = 2 时，使用位运算快速求解（1-indexed）
 * @param n 总人数
 * @return int 幸存者编号
 */
int josephus_k2(unsigned int n) {
    if (n == 0) return 0;

    // 找到最高位的 1（在 C++20 中可以使用 std::bit_width，C++11 手动计算）
    unsigned int temp = n;
    unsigned int shift = 0;
    while (temp > 1) {
        temp >>= 1;
        shift++;
    }

    // 2^m 就是 1 << shift
    unsigned int max_power_of_2 = 1 << shift;
    unsigned int l = n - max_power_of_2;

    return 2 * l + 1;
}

int main() {
    unsigned int n = 41; // 经典历史背景中的 41 个人
    std::cout << "当 k=2, n=" << n << " 时，幸存者编号为: " << josephus_k2(n) << "\n";
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com