引言
约瑟夫问题（Josephus Problem）是计算机科学中最经典的递归问题之一。传说犹太历史学家约瑟夫在罗马人占领乔塔帕特后，与40名士兵被困于一个洞穴中。他们决定自杀以避免被俘，约瑟夫和另一个人设法存活了下来。本文将用Java实现多种求解约瑟夫问题的方法，从直观的模拟到数学递推公式，帮助读者深入理解递归与动态规划的核心思想。
问题描述
有 n 个人围成一圈，从第一个人开始报数，数到 k 的人出圈，然后从下一个人重新开始报数，直到所有人出圈。求出圈的顺序，或求最后幸存者的初始编号。
方法一：模拟法（链表实现）
最直观的解法是使用循环链表模拟整个过程。
import java.util.ArrayList;
import java.util.List;
/**
* 约瑟夫问题多种解法实现
*/
public class JosephusProblem {
/**
* 节点类：循环链表节点
*/
static class Node {
int id; // 人员编号（1-based）
Node next; // 下一个节点
Node(int id) {
this.id = id;
this.next = null;
}
}
/**
* 方法一：循环链表模拟法
* 时间复杂度: O(n * k)
* 空间复杂度: O(n)
*/
public static List<Integer> solveBySimulation(int n, int k) {
List<Integer> eliminationOrder = new ArrayList<>();
// 构建循环链表: 1 -> 2 -> 3 -> ... -> n -> 1
Node head = new Node(1);
Node current = head;
for (int i = 2; i <= n; i++) {
current.next = new Node(i);
current = current.next;
}
current.next = head; // 形成循环
Node prev = current; // 指向当前节点的前一个节点
current = head;
int remaining = n;
while (remaining > 0) {
// 向前移动 k-1 步（当前节点算第1个）
for (int i = 1; i < k; i++) {
prev = current;
current = current.next;
}
// 当前节点出圈
eliminationOrder.add(current.id);
prev.next = current.next; // 从链表中移除
current = current.next; // 从下一个人继续
remaining--;
}
return eliminationOrder;
}
方法二：递归法
利用递归的思想，将规模为 n 的问题转化为规模为 n-1 的子问题。
/**
* 方法二：递归法
* 核心思想：设 J(n, k) 表示 n 个人、报数 k 时最后幸存者的编号
* 递推关系：J(n, k) = (J(n-1, k) + k) % n
* 基准条件：J(1, k) = 0（0-based编号）
*
* 时间复杂度: O(n)
* 空间复杂度: O(n) 递归栈深度
*/
public static int solveByRecursion(int n, int k) {
// 基准条件：只有1个人时，幸存者编号为0（0-based）
if (n == 1) {
return 0;
}
// 递归：先求解 n-1 人的子问题，然后映射回 n 人的编号
return (solveByRecursion(n - 1, k) + k) % n;
}
/**
* 递归法：返回1-based的幸存者编号
*/
public static int solveByRecursion1Based(int n, int k) {
return solveByRecursion(n, k) + 1;
}
方法三：动态规划（迭代优化）
将递归改为迭代，消除递归栈开销。
/**
* 方法三：动态规划迭代法
* 自底向上计算：从1个人的情况逐步推导到n个人
*
* 状态转移：dp[i] = (dp[i-1] + k) % i
* dp[i] 表示 i 个人时最后幸存者的0-based编号
*
* 时间复杂度: O(n)
* 空间复杂度: O(1) —— 只需保存前一个状态
*/
public static int solveByDP(int n, int k) {
int survivor = 0; // dp[1] = 0
for (int i = 2; i <= n; i++) {
survivor = (survivor + k) % i;
}
return survivor + 1; // 转换为1-based
}
方法四：输出完整出圈顺序的递归解法
/**
* 方法四：递归输出完整出圈顺序
* 利用数学递推公式反向推导每一步出圈的人
*
* 设 f(n, k, i) 为第 i 个出圈的人在原始序列中的编号
* 递推：f(n, k, i) = (f(n-1, k, i-1) + k) % n
*/
public static List<Integer> getEliminationOrderByMath(int n, int k) {
List<Integer> order = new ArrayList<>();
// 使用动态规划思想，逐步构建出圈顺序
// 设 pos[i] 表示第 i 轮（还剩 n-i+1 人）时出圈者的位置
// 需要维护一个"存活者列表"来映射位置到原始编号
// 使用线段树或树状数组优化，这里先用简单数组模拟
boolean[] eliminated = new boolean[n + 1];
int currentPos = 0; // 当前报数起始位置（0-based，相对于存活者）
for (int round = n; round >= 1; round--) {
// 在当前 round 个存活者中，找到第 k 个
int step = k % round;
if (step == 0) step = round;
// 在存活者中移动 step 步
int count = 0;
while (count < step) {
currentPos = (currentPos + 1) % n;
if (!eliminated[currentPos == 0 ? n : currentPos]) {
count++;
}
}
// 注意：上面的逻辑需要修正，使用更清晰的实现
// 以下是修正后的版本
break;
}
// 更清晰的完整顺序计算：使用顺序表+数学递推
return getOrderByList(n, k);
}
/**
* 使用列表模拟（比链表更易读）
*/
public static List<Integer> getOrderByList(int n, int k) {
List<Integer> people = new ArrayList<>();
for (int i = 1; i <= n; i++) {
people.add(i);
}
List<Integer> order = new ArrayList<>();
int index = 0;
while (!people.isEmpty()) {
// 计算下一个出圈者的索引
index = (index + k - 1) % people.size();
order.add(people.remove(index));
}
return order;
}
核心数学推导
约瑟夫问题的核心在于理解递推公式 J(n, k) = (J(n-1, k) + k) % n。
推导过程：
- 假设 n 个人排成一圈，编号为 0 到 n-1（0-based）
- 第一轮报数后，编号为
(k-1) % n的人出圈 - 从出圈者的下一个人（编号为
k % n）开始，重新编号为 0 - 剩余 n-1 个人形成一个新的约瑟夫问题
- 设新编号中幸存者的编号为
J(n-1, k)，则对应原编号为(J(n-1, k) + k) % n
/**
* 数学推导验证：打印每一步的递推过程
*/
public static void printDPSteps(int n, int k) {
System.out.println("=== 动态规划递推过程 ===");
int survivor = 0;
System.out.println("dp[1] = " + survivor);
for (int i = 2; i <= n; i++) {
int prev = survivor;
survivor = (survivor + k) % i;
System.out.println("dp[" + i + "] = (dp[" + (i-1) + "] + " + k + ") % " + i +
" = (" + prev + " + " + k + ") % " + i + " = " + survivor);
}
System.out.println("最终幸存者（0-based）: " + survivor);
System.out.println("最终幸存者（1-based）: " + (survivor + 1));
}
完整测试与对比
/**
* 主程序：测试所有方法并对比结果
*/
public static void main(String[] args) {
int n = 7; // 7个人
int k = 3; // 数到3出圈
System.out.println("约瑟夫问题: n=" + n + ", k=" + k);
System.out.println();
// 方法1：链表模拟
List<Integer> order1 = solveBySimulation(n, k);
System.out.println("方法一（链表模拟）出圈顺序: " + order1);
// 方法2&3：幸存者
int survivor2 = solveByRecursion1Based(n, k);
int survivor3 = solveByDP(n, k);
System.out.println("方法二（递归）幸存者: " + survivor2);
System.out.println("方法三（DP迭代）幸存者: " + survivor3);
// 方法4：列表模拟出圈顺序
List<Integer> order4 = getOrderByList(n, k);
System.out.println("方法四（列表模拟）出圈顺序: " + order4);
// 验证：出圈顺序的最后一个元素应该等于幸存者
System.out.println();
System.out.println("验证: 出圈顺序最后一人 = " + order1.get(order1.size()-1) +
", 幸存者 = " + survivor3);
System.out.println("结果一致: " + (order1.get(order1.size()-1) == survivor3));
// 打印递推过程
System.out.println();
printDPSteps(n, k);
// 大规模测试
System.out.println("\n=== 大规模测试 ===");
int nLarge = 100000;
int kLarge = 7;
long start = System.currentTimeMillis();
int result = solveByDP(nLarge, kLarge);
long end = System.currentTimeMillis();
System.out.println("n=" + nLarge + ", k=" + kLarge +
" 的幸存者: " + result);
System.out.println("DP迭代耗时: " + (end - start) + "ms");
}
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 链表模拟 | O(n × k) | O(n) | k较小，需要完整出圈顺序 |
| 递归 | O(n) | O(n) | 仅求幸存者，代码简洁 |
| 动态规划迭代 | O(n) | O(1) | 仅求幸存者，最优解法 |
| 列表模拟顺序 | O(n²) | O(n) | 需要完整出圈顺序，代码简洁 |
注意：当 k 较大时，递推公式中 (survivor + k) % i 可用取模优化，但整体仍为 O(n)。
扩展与变种
- 双向约瑟夫问题：报数方向交替改变，递推公式需要调整
- 多幸存者版本：求最后 m 个幸存者的编号，可用树状数组维护存活状态，每次删除 O(log n)，总复杂度 O(n log n)
- 一般化版本：每人有不同的报数步长 k_i，递推公式变为
J(n) = (J(n-1) + k_n) % n - 约瑟夫环的逆问题：已知出圈顺序，反推原始编号排列
总结
约瑟夫问题完美展示了递归思维与动态规划的威力。从 O(n×k) 的链表模拟，到 O(n) 的递归解法，再到 O(n) 时间 O(1) 空间的迭代DP，算法的优化过程本身就是一个极好的学习案例。核心递推公式 J(n) = (J(n-1) + k) % n 体现了”大问题分解为小问题”的精髓，是算法面试中的高频考点。
