传金币是一个经典的环形传递游戏，参与者围成一圈，从某一人开始按固定方向依次传递金币，当音乐停止时持有金币的人被淘汰。本文用Java实现这一游戏，重点讲解约瑟夫环变体的数学建模、环形链表的优雅实现，以及贪心策略在传递路径优化中的应用。
问题建模
将n名参与者编号为0到n-1，围成一个环形。从第s号参与者开始，每次将金币沿顺时针方向传递k步，持有金币的人被淘汰。重复此过程直到只剩一人，求最后的幸存者编号。
这是经典的约瑟夫问题（Josephus Problem）变体。原始约瑟夫问题是每次淘汰第k个人，而传金币增加了”起始位置”和”传递方向”的可变性。
核心算法：递推求解
设J(n, k)表示n个人、步长为k时的幸存者编号（从0开始编号）。约瑟夫问题存在优雅的递推公式：
J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n
对于传金币问题，若起始位置为s，则最终结果为(J(n, k) + s) % n。
完整Java实现
import java.util.ArrayList;
import java.util.List;
/**
* 传金币游戏 — 约瑟夫环变体实现
* 包含递推法、模拟法、环形链表法三种解法
*/
public class CoinPassingGame {
/**
* 方法一：数学递推法（最优，O(n)时间，O(1)空间）
* 利用约瑟夫问题的递推公式直接计算幸存者
*/
public static int findSurvivorMath(int n, int k, int start) {
if (n <= 0 || k <= 0) {
throw new IllegalArgumentException("参与人数和步长必须为正整数");
}
// J(1, k) = 0
int survivor = 0;
// 递推计算 J(i, k) for i = 2 to n
for (int i = 2; i <= n; i++) {
survivor = (survivor + k) % i;
}
// 调整起始位置偏移
return (survivor + start) % n;
}
/**
* 方法二：环形链表模拟法（直观，O(n*k)时间，O(n)空间）
* 使用循环链表模拟实际传递过程
*/
public static int findSurvivorSimulation(int n, int k, int start) {
if (n <= 0 || k <= 0) {
throw new IllegalArgumentException("参与人数和步长必须为正整数");
}
// 构建循环链表
ListNode head = buildCircularList(n);
// 移动到起始位置
ListNode current = head;
for (int i = 0; i < start; i++) {
current = current.next;
}
ListNode prev = null;
int remaining = n;
while (remaining > 1) {
// 传递k-1步（当前已持金币，再传k-1次到达目标）
for (int i = 0; i < k - 1; i++) {
prev = current;
current = current.next;
}
// 淘汰current节点
prev.next = current.next;
current = current.next;
remaining--;
}
return current.value;
}
/**
* 方法三：数组模拟法（空间友好，O(n*k)时间，O(n)空间）
* 使用布尔数组标记存活状态
*/
public static int findSurvivorArray(int n, int k, int start) {
boolean[] alive = new boolean[n];
// 所有人初始存活
for (int i = 0; i < n; i++) {
alive[i] = true;
}
int remaining = n;
int current = start;
int prev = -1;
while (remaining > 1) {
// 向前数k个存活的人
int count = 0;
while (count < k) {
if (alive[current]) {
count++;
if (count == k) {
break;
}
}
current = (current + 1) % n;
}
// 淘汰current
alive[current] = false;
remaining--;
// 找到下一个存活者作为新的current
do {
current = (current + 1) % n;
} while (!alive[current]);
}
// 找到唯一幸存者
for (int i = 0; i < n; i++) {
if (alive[i]) return i;
}
return -1; // 不会发生
}
/**
* 贪心策略：最优起始位置选择
* 对于给定的n和k，找到让特定玩家（如自己）获胜的最佳起始位置
*/
public static int findBestStartForPlayer(int n, int k, int targetPlayer) {
// 计算每个起始位置对应的幸存者
for (int s = 0; s < n; s++) {
if (findSurvivorMath(n, k, s) == targetPlayer) {
return s;
}
}
return -1; // 不可能发生
}
/**
* 批量查询：预计算所有子问题的解（动态规划）
* 用于需要频繁查询不同(n,k)组合的场景
*/
public static int[][] precomputeJosephus(int maxN, int maxK) {
int[][] dp = new int[maxN + 1][maxK + 1];
for (int k = 1; k <= maxK; k++) {
dp[1][k] = 0;
for (int n = 2; n <= maxN; n++) {
dp[n][k] = (dp[n - 1][k] + k) % n;
}
}
return dp;
}
// 链表节点定义
private static class ListNode {
int value;
ListNode next;
ListNode(int value) {
this.value = value;
}
}
// 构建循环链表
private static ListNode buildCircularList(int n) {
ListNode head = new ListNode(0);
ListNode current = head;
for (int i = 1; i < n; i++) {
current.next = new ListNode(i);
current = current.next;
}
current.next = head; // 首尾相连形成环
return head;
}
// 打印淘汰顺序（用于演示）
public static List<Integer> getEliminationOrder(int n, int k, int start) {
List<Integer> order = new ArrayList<>();
boolean[] alive = new boolean[n];
for (int i = 0; i < n; i++) alive[i] = true;
int remaining = n;
int current = start;
while (remaining > 0) {
int count = 0;
while (count < k) {
if (alive[current]) {
count++;
if (count == k) break;
}
current = (current + 1) % n;
}
order.add(current);
alive[current] = false;
remaining--;
if (remaining > 0) {
do {
current = (current + 1) % n;
} while (!alive[current]);
}
}
return order;
}
public static void main(String[] args) {
int n = 7; // 7名参与者
int k = 3; // 每次传3步
int start = 0; // 从0号开始
System.out.println("===== 传金币游戏演示 =====");
System.out.println("参与人数: " + n + ", 步长: " + k + ", 起始: " + start);
// 三种方法结果对比
int mathResult = findSurvivorMath(n, k, start);
int simResult = findSurvivorSimulation(n, k, start);
int arrResult = findSurvivorArray(n, k, start);
System.out.println("\n幸存者编号（数学递推）: " + mathResult);
System.out.println("幸存者编号（链表模拟）: " + simResult);
System.out.println("幸存者编号（数组模拟）: " + arrResult);
// 淘汰顺序
List<Integer> order = getEliminationOrder(n, k, start);
System.out.println("\n淘汰顺序: " + order);
System.out.println("最后幸存者是第 " + order.get(order.size() - 1) + " 号");
// 贪心策略演示
int target = 2;
int bestStart = findBestStartForPlayer(n, k, target);
System.out.println("\n贪心策略: 若想让 " + target + " 号获胜，最佳起始位置是 " + bestStart);
// 大规模测试
System.out.println("\n===== 大规模测试 =====");
int bigN = 100000;
int bigK = 7;
long t1 = System.currentTimeMillis();
int bigResult = findSurvivorMath(bigN, bigK, 0);
long t2 = System.currentTimeMillis();
System.out.println("n=" + bigN + ", k=" + bigK + " 的幸存者: " + bigResult);
System.out.println("计算耗时: " + (t2 - t1) + "ms");
}
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 数学递推法 | O(n) | O(1) | 仅需最终结果，大规模数据首选 |
| 环形链表模拟 | O(n×k) | O(n) | 需要模拟过程、获取淘汰顺序 |
| 数组模拟 | O(n×k) | O(n) | 需要追踪每轮状态 |
| 动态规划预计算 | O(maxN×maxK) | O(maxN×maxK) | 频繁查询不同参数组合 |
贪心策略扩展
在多人博弈场景下，若允许玩家选择起始位置和步长规则，贪心策略的核心是：
- 固定步长时：通过调整起始位置控制幸存者
- 可变步长时：选择使对手处于劣势位置的步长值
- 多轮博弈时：利用对称性打破僵局
总结
传金币问题展示了如何将一个简单游戏抽象为数学模型。约瑟夫问题的递推解法是算法优化的典范——将看似需要O(n²)模拟的问题压缩到O(n)的线性时间。掌握这种从模拟到数学的转化思维，是解决复杂算法问题的关键能力。
