抢凳子（Musical Chairs）是广为人知的派对游戏：N名参与者围绕M把凳子（M<N）转圈，音乐停止时每人需抢坐一把凳子，未抢到者淘汰，同时撤掉一把凳子，直至决出最后胜者。本文用Java实现这一经典淘汰游戏，核心算法涉及约瑟夫环变体建模与幸存者预测。
游戏规则与数学建模
每轮淘汰规则：
– N人竞争M把凳子（M = N - 1为经典规则）
– 音乐停止瞬间，每人随机选择一把凳子
– 每把凳子只能坐1人，未坐到者淘汰
– 淘汰1人后撤掉1把凳子，进入下一轮
当每轮恰好淘汰1人时，问题等价于经典的约瑟夫问题：n个人围成一圈，从某个指定位置开始报数，数到k的人出局，再从下一个人重新开始报数，求最后的幸存者。
本文建模更一般的随机淘汰版本：每轮每人等概率选择一把凳子，若多人选择同一把则随机留下一人，其余淘汰。
约瑟夫环与幸存者问题
经典约瑟夫问题有递推公式：
J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n
其中J(n, k)表示n个人、步长为k时幸存者的初始位置（0索引）。该递推可在O(n)时间内求解，也可用数学方法在O(k log n)内求解。
对于每轮仅淘汰1人的抢凳子变体，只需令k=2（音乐停止相当于报数终止），直接用约瑟夫递推即可预测胜者。
Java完整实现
import java.util.*;
/**
* 抢凳子游戏 - 约瑟夫环变体与动态淘汰策略
* 核心问题：每轮淘汰若干人，求最终幸存者
*/
public class MusicalChairs {
// ==================== 核心算法：经典约瑟夫问题 ====================
/**
* 经典约瑟夫递推：O(n)时间求幸存者位置
* @param n 总人数
* @param k 报数步长(每第k个人淘汰)
* @return 幸存者初始位置(0索引)
*/
public static int josephus(int n, int k) {
int survivor = 0; // J(1, k) = 0
for (int i = 2; i <= n; i++) {
survivor = (survivor + k) % i;
}
return survivor;
}
/**
* 当k=2时的数学优化：利用最高次幂公式
* J(n, 2) = 2L + 1, 其中 L = n - 2^floor(log2(n))
* 时间复杂度：O(log n)
*/
public static int josephusK2(int n) {
// 找到小于等于n的最大2的幂
int highestPower = Integer.highestOneBit(n);
int l = n - highestPower;
return 2 * l;
}
// ==================== 扩展：随机淘汰版本 ====================
/**
* 模拟经典抢凳子：每轮N人竞争N-1把凳子，恰好淘汰1人
* 淘汰位置随机(非约瑟夫固定步长)
* @param players 玩家列表
* @return 最终幸存者
*/
public static Player simulateClassicChairs(List<Player> players, Random rand) {
List<Player> alive = new ArrayList<>(players);
int round = 1;
while (alive.size() > 1) {
int chairs = alive.size() - 1;
System.out.println("\n第" + round + "轮: " + alive.size() + "人竞争" + chairs + "把凳子");
// 每个人随机选择一把凳子
Map<Integer, List<Player>> chairChoices = new HashMap<>();
for (Player p : alive) {
int choice = rand.nextInt(chairs);
chairChoices.computeIfAbsent(choice, x -> new ArrayList<>()).add(p);
}
// 每把凳子随机留下1人，其余淘汰
List<Player> nextRound = new ArrayList<>();
for (List<Player> competitors : chairChoices.values()) {
// 随机洗牌后取第一个
Collections.shuffle(competitors, rand);
nextRound.add(competitors.get(0));
if (competitors.size() > 1) {
System.out.println(" 淘汰: " + competitors.subList(1, competitors.size()));
}
}
alive = nextRound;
round++;
}
return alive.get(0);
}
/**
* 动态规则变体：凳子数每轮减少量不固定
* 例如M = N - 2，每轮淘汰2人
*/
public static Player simulateVariantChairs(List<Player> players, int eliminatePerRound, Random rand) {
List<Player> alive = new ArrayList<>(players);
int round = 1;
while (alive.size() > 1) {
int chairs = Math.max(1, alive.size() - eliminatePerRound);
System.out.println("\n第" + round + "轮: " + alive.size() + "人竞争" + chairs + "把凳子");
Map<Integer, List<Player>> chairChoices = new HashMap<>();
for (Player p : alive) {
int choice = rand.nextInt(chairs);
chairChoices.computeIfAbsent(choice, x -> new ArrayList<>()).add(p);
}
List<Player> nextRound = new ArrayList<>();
for (List<Player> competitors : chairChoices.values()) {
Collections.shuffle(competitors, rand);
nextRound.add(competitors.get(0));
}
alive = nextRound;
round++;
}
return alive.get(0);
}
// ==================== 概率分析：蒙特卡洛模拟 ====================
/**
* 蒙特卡洛模拟：统计每个初始位置成为胜者的概率
*/
static Map<Integer, Double> computeWinProbability(int n, int simulations) {
Map<Integer, Integer> winCount = new HashMap<>();
Random rand = new Random(42);
for (int sim = 0; sim < simulations; sim++) {
List<Player> players = new ArrayList<>();
for (int i = 0; i < n; i++) {
players.add(new Player(i, "Player-" + i));
}
Player winner = simulateSilent(players, rand);
winCount.merge(winner.id, 1, Integer::sum);
}
Map<Integer, Double> prob = new HashMap<>();
for (Map.Entry<Integer, Integer> e : winCount.entrySet()) {
prob.put(e.getKey(), (double) e.getValue() / simulations);
}
return prob;
}
/**
* 静默模拟（不打印），用于大规模统计
*/
static Player simulateSilent(List<Player> players, Random rand) {
List<Player> alive = new ArrayList<>(players);
while (alive.size() > 1) {
int chairs = alive.size() - 1;
Map<Integer, List<Player>> chairChoices = new HashMap<>();
for (Player p : alive) {
int choice = rand.nextInt(chairs);
chairChoices.computeIfAbsent(choice, x -> new ArrayList<>()).add(p);
}
List<Player> nextRound = new ArrayList<>();
for (List<Player> competitors : chairChoices.values()) {
Collections.shuffle(competitors, rand);
nextRound.add(competitors.get(0));
}
alive = nextRound;
}
return alive.get(0);
}
// ==================== 数据结构：玩家定义 ====================
static class Player {
int id;
String name;
int speed; // 抢凳速度(影响概率)
Player(int id, String name) {
this.id = id;
this.name = name;
this.speed = 50;
}
Player(int id, String name, int speed) {
this.id = id;
this.name = name;
this.speed = speed;
}
@Override
public String toString() {
return name;
}
}
// ==================== 进阶：加权概率淘汰 ====================
/**
* 考虑玩家抢凳速度差异的模拟
* 速度快的玩家在同凳竞争中存活概率更高
*/
public static Player simulateWeightedChairs(List<Player> players, Random rand) {
List<Player> alive = new ArrayList<>(players);
int round = 1;
while (alive.size() > 1) {
int chairs = alive.size() - 1;
Map<Integer, List<Player>> chairChoices = new HashMap<>();
for (Player p : alive) {
int choice = rand.nextInt(chairs);
chairChoices.computeIfAbsent(choice, x -> new ArrayList<>()).add(p);
}
List<Player> nextRound = new ArrayList<>();
for (List<Player> competitors : chairChoices.values()) {
// 按速度加权随机选择存活者
int totalSpeed = competitors.stream().mapToInt(p -> p.speed).sum();
int pick = rand.nextInt(totalSpeed);
int cumulative = 0;
Player survivor = competitors.get(0);
for (Player p : competitors) {
cumulative += p.speed;
if (pick < cumulative) {
survivor = p;
break;
}
}
nextRound.add(survivor);
}
alive = nextRound;
round++;
}
return alive.get(0);
}
// ==================== 主程序与演示 ====================
public static void main(String[] args) {
System.out.println("========== 抢凳子游戏 - 约瑟夫环变体 ==========\n");
// 1. 经典约瑟夫问题演示
System.out.println("=== 经典约瑟夫问题 (步长k=2) ===");
for (int n = 1; n <= 10; n++) {
int survivor = josephus(n, 2);
int survivorOpt = josephusK2(n);
System.out.printf("n=%d: 幸存者位置=%d (优化版=%d)%n", n, survivor, survivorOpt);
}
// 2. 经典抢凳子模拟
System.out.println("\n=== 经典抢凳子模拟 (8人) ===");
List<Player> players = new ArrayList<>();
for (int i = 0; i < 8; i++) {
players.add(new Player(i, "玩家" + (i + 1)));
}
Random rand = new Random(123);
Player winner = simulateClassicChairs(players, rand);
System.out.println("\n最终胜者: " + winner.name);
// 3. 概率统计
System.out.println("\n=== 蒙特卡洛概率统计 (8人, 10000次模拟) ===");
Map<Integer, Double> probs = computeWinProbability(8, 10000);
for (int i = 0; i < 8; i++) {
double p = probs.getOrDefault(i, 0.0);
System.out.printf("玩家%d 获胜概率: %.2f%%%n", i + 1, p * 100);
}
// 4. 加权速度模拟
System.out.println("\n=== 加权速度模拟 (速度快的人有优势) ===");
List<Player> speedPlayers = new ArrayList<>();
speedPlayers.add(new Player(0, "乌龟", 20));
speedPlayers.add(new Player(1, "兔子", 80));
speedPlayers.add(new Player(2, "猎豹", 95));
speedPlayers.add(new Player(3, "普通人", 50));
speedPlayers.add(new Player(4, "运动员", 70));
Map<String, Integer> winStats = new HashMap<>();
for (int sim = 0; sim < 10000; sim++) {
List<Player> copy = new ArrayList<>();
for (Player p : speedPlayers) copy.add(new Player(p.id, p.name, p.speed));
Player w = simulateWeightedChairs(copy, new Random(sim));
winStats.merge(w.name, 1, Integer::sum);
}
System.out.println("10000次加权模拟结果:");
for (Map.Entry<String, Integer> e : winStats.entrySet()) {
System.out.printf(" %s: %d 次 (%.2f%%)%n", e.getKey(), e.getValue(), e.getValue() / 100.0);
}
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 约瑟夫递推 | O(n) | O(1) | 经典固定步长淘汰 |
| k=2数学公式 | O(log n) | O(1) | 恰好淘汰一半的特殊情况 |
| 随机淘汰模拟 | O(rounds × n) | O(n) | 每轮随机淘汰 |
| 蒙特卡洛统计 | O(simulations × rounds × n) | O(n) | 概率分布估计 |
约瑟夫递推是动态规划的极致压缩：仅保留前一轮的幸存者位置，通过取模运算在常数空间内迭代求解，体现了状态压缩的核心思想。
扩展思考
- 多轮并行淘汰：若每轮淘汰比例固定（如每次淘汰一半），可用二分快速幂加速递推，时间复杂度降至O(log² n)。
- 不完全信息博弈：玩家不知剩余凳子数，仅根据音乐节奏猜测停止时机，可建模为带有随机 stopping time 的最优停止问题。
- 图论扩展：将凳子布局从环形扩展为任意图结构，玩家在图上移动抢位，问题转化为图上的竞争博弈，与”图着色博弈”密切相关。
抢凳子将概率论、递推动态规划与博弈论浓缩在一个简单规则中，是理解淘汰过程与幸存者偏差的绝佳模型。
