企业官网建设流程全解析

前言

约瑟夫问题（Josephus problem）的描述是：n 个人围成一圈，从某个人开始报数，报到 k 的人出列，下一个人重新从 1 开始报数，如此重复，问最后剩下的那个人原来的编号是多少。它常被当作链表或数组下标的练习题，但它真正的价值在于：同一个过程既可以老老实实模拟，也可以推导出一个只依赖前一项的递推式，两种解法的复杂度相差一个数量级。

围绕这个问题的误解主要有三类。第一类是以为必须真的把每个人从环里删掉才能得到答案，于是写出的代码在 n 稍大时就会明显变慢。第二类是把「报到 k 出列」理解成「每隔 k 个人出列」，导致下标偏移量写成 k 而不是 k-1。第三类是编号基准混乱：递推公式通常在 0 基编号下推导，而题目输出往往要求 1 基编号，中间少加一个 1，答案就整体错位。

本文先用数组模拟把过程写清楚，再从模拟过程推出 O(n) 的递推解法，最后讨论 k 很大、n 很大时的边界处理。文中代码以 C++17 为基准，只使用标准库。

一、问题建模与模拟解法

把 n 个人编号为 0 到 n-1，放在一个数组里。用一个下标idx表示「本轮从谁开始报数」。从idx开始数 k 个人，第 k 个人在数组中的位置是(idx + k - 1) % size，因为idx本身算第 1 个。删除这个位置之后，它后面的元素整体前移，新的idx恰好指向原来被删元素的下一个位置，也就是下一轮的报数起点，不需要再额外调整。

这里有一个容易被忽略的细节：取模的除数是当前剩余人数，而不是最初的 n。每删一个人，环就少一个位置，如果还用 n 取模，下标会落到已经缩短的数组之外。

按这个思路写出的模拟代码直观、易验证，但代价是每次erase都要移动后面的元素。std::vector::erase是线性复杂度，n 次删除合计 O(n²)；如果换成std::list，删除本身是 O(1)，但走到第 k 个人需要 k 步，总计 O(nk)。两者都不适合大规模输入。

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <vector>

// 模拟法：返回 1 基编号，n 必须为正
int josephus_simulate(int n, int k) {
std::vector<int> ring(static_cast<std::size_t>(n));
for (int i = 0; i < n; ++i) {
ring[static_cast<std::size_t>(i)] = i + 1;
}

std::size_t idx = 0;
while (ring.size() > 1) {
// idx 指向本轮报 1 的人，数到 k 要前进 k-1 步
idx = (idx + static_cast<std::size_t>(k) - 1) % ring.size();
ring.erase(ring.begin() + static_cast<std::ptrdiff_t>(idx));
// 删除后 idx 正好指向下一个报数的人；若删的是末尾，取模后回到 0
if (idx == ring.size()) {
idx = 0;
}
}
return ring.front();
}

int main() {
const int n = 41;
const int k = 3;
std::cout << josephus_simulate(n, k) << '\n';
return 0;
}

上面代码里idx == ring.size()的判断是必要的：当被删除的是最后一个元素时，idx等于新的size()，下一次取模虽然也能把它变回 0，但中间那次ring.begin() + idx并不会被使用，所以两种写法都对；显式归零只是让「idx 始终是合法下标」这个不变式更清楚。真正不能省的是取模本身。

二、O(n) 递推：从结果反推编号

模拟法的瓶颈在于「每次都要知道当前环里有哪些人」。但约瑟夫问题只问最后一个人，不关心中间的出列顺序，这就允许我们换一个角度：只跟踪胜者在每一层环中的相对位置。

设f(i)表示 i 个人围成环、每轮报 k 出列时，最终胜者在 0 基编号下的下标。当i = 1时只剩一个人，他当然在位置 0，所以f(1) = 0。

现在考虑从 i-1 人恢复到 i 人。i 个人时第一个出列的是下标(k-1) % i的人。把他删掉后，剩下 i-1 个人，下一轮从被删位置的下一个人开始报数。如果把这个人重新编号为 0，就得到一个规模为 i-1 的同类问题，其胜者位置是f(i-1)。把这个相对位置映射回原来的 i 人环：原下标等于(f(i-1) + k) % i。原因是新编号 0 对应原下标 k（被删的人占了下标 k-1），此后每前进一个相对位置，原下标也前进一个。

于是得到递推式：

f(1) = 0
f(i) = (f(i-1) + k) % i (i >= 2)

最终答案是f(n) + 1（转成 1 基编号）。

这个式子只需要一个变量滚动，时间 O(n)，额外空间 O(1)，也不需要真的维护一个环。它的含义是「每一轮把环旋转一次再缩小」，而不是「模拟删除」。

// 适用于 C++17
#include <iostream>

// 递推法：返回 1 基编号；n >= 1，k >= 1
int josephus_recursive(int n, int k) {
long long f = 0; // f(1) = 0，用 64 位防止 f + k 溢出
for (int i = 2; i <= n; ++i) {
f = (f + static_cast<long long>(k)) % i;
}
return static_cast<int>(f) + 1;
}

int main() {
std::cout << josephus_recursive(41, 3) << '\n';
return 0;
}

用 41 个人、报 3 出列这个经典设置，按上述语义推演，最后剩下的人应当是原来的第 31 号（1 基）。这里说「应当」是因为本文没有运行环境，结论来自公式本身；读者可以用模拟法交叉核对，两个函数对同一组输入必须给出相同结果，这也是写这类题时最实用的自检手段。

三、变体、规模与边界

约瑟夫问题在题面上有几个常见变体，写代码前必须确认是哪一种，否则公式会整体偏移：

最后一种变体值得单独说明：如果规则是「出列后下一个人接着报 k+1，而不是重新从 1 报」，那么每轮的步长会累积变化，第二节的固定步长递推式不能直接套用，需要重新推导或者退回模拟。很多题解错在没看清这一句。

规模方面，O(n) 递推在 n 达到千万级时仍然要循环千万次，通常可以接受；如果 n 大到 10⁹ 而 k 很小，可以利用「一轮可能连续淘汰多人」做分段跳跃，把复杂度降到与 k 相关的量级；如果 n 极大且 k 任意，则需要用线段树或树状数组维护「第 m 个存活者」，单次 O(log n)。这些做法都建立在同一个前提上：只需要最终胜者或第 m 个出列者，不需要完整出列序列。

还要注意整数类型。递推中的f + k在 k 接近INT_MAX、n 也很大时可能超出int范围，而有符号溢出是未定义行为（undefined behavior, UB），不是「回绕成负数」这么温和。用long long承接中间值，或者先对 k 取模再相加，都是稳妥做法。本文示例把f声明为long long，正是为此。

常见坑点

坑点一：删除元素后继续用旧下标，且没有对新的 size 取模。

❌idx = (idx + k - 1) % n; ring.erase(ring.begin() + idx);其中 n 是初始人数且始终不变。

✅ 取模用ring.size()，并在删除后检查下标是否越界。

坑点二：把「报到 k」写成偏移 k。

❌idx = (idx + k) % ring.size();这样实际淘汰的是第 k+1 个人。

✅ 当前人算第 1 个，偏移量是k - 1。

坑点三：0 基推导、1 基输出，忘了加一。

❌ 递推得到f(n)后直接输出，结果比正确答案小 1。

✅ 明确统一基准：内部用 0 基，输出时f(n) + 1；或者全程 1 基并在取模后特判 0。

坑点四：用递归实现递推式。

❌return (josephus(n - 1, k) + k) % n;当 n 很大时递归深度等于 n，有栈溢出风险。

✅ 递推式本来就是自底向上的，用循环从 2 推到 n，空间 O(1)。

坑点五：忽略 k 为 1 或 n 为 1 的边界。

❌ 进入循环前不检查 n，ring.front()在空数组上是 UB。

✅ 函数入口校验n >= 1 && k >= 1，n 为 1 时直接返回 1。

坑点六：以为模拟法和递推法可以随便混用编号。

❌ 模拟法内部用 1 基编号，却套用 0 基的(idx + k - 1) % size，每轮都多淘汰一个人。

✅ 选定一种基准贯穿始终；模拟法推荐 0 基存储、输出时加 1。

坑点七：中间结果用 int 承接 f + k。

❌int f = 0; f = (f + k) % i;当 k 接近INT_MAX时加法溢出，属于 UB。

✅ 用long long保存中间值，或者写成(f + k % i) % i。

总结

约瑟夫问题的核心不是「怎么删人」，而是「能不能只跟踪胜者的相对位置」。想清楚每一轮删除后环如何重新编号，递推式就是自然的结果；想不清楚时，先写模拟法把下标变化打印出来，再对照递推式，比死记公式可靠得多。