每日算法 — 使用java实现抢椅子：约瑟夫环与循环链表

游戏背景与问题建模

抢椅子（Musical Chairs）是一款经典的淘汰游戏：N 位参与者围绕 M 把椅子（M < N）走动，音乐停止时所有人抢坐椅子，没有抢到椅子的人被淘汰；随后撤掉一把椅子，重复进行，直到最后一人获胜。

本文将抢椅子游戏抽象为约瑟夫问题（Josephus Problem）的变体：N 个人围成一圈，从某个指定位置开始报数，数到 K 的人被淘汰，从下一个人重新报数，求最后的幸存者编号。抢椅子的规则可视为 K=1 的特殊情况（每轮淘汰 1 人）。

算法思路

循环链表模拟

最直观的方法是使用循环链表模拟整个过程：
– 每个节点代表一位参与者
– 节点首尾相连形成环
– 每轮移除一个节点，直到只剩一个节点

数学递推公式

约瑟夫问题存在高效的数学解法。设 f(n, k) 表示 n 个人、步长为 k 时幸存者的编号（从 0 开始），则有递推关系：

f(1, k) = 0
f(n, k) = (f(n-1, k) + k) % n

该公式可在 O(n) 时间内直接计算出结果，无需模拟淘汰过程。

Java 完整实现

import java.util.ArrayList;
import java.util.List;

/**
 * 抢椅子游戏：约瑟夫环与循环链表实现
 * 模拟多轮淘汰过程，支持链表模拟与数学递推两种解法
 */
public class MusicalChairs {

    /**
     * 循环链表节点
     */
    static class Node {
        int id;           // 参与者编号
        String name;      // 参与者名称
        Node next;        // 下一个节点

        Node(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

    /**
     * 使用循环链表模拟抢椅子淘汰过程
     * @param players  参与者列表
     * @param chairs   初始椅子数量（每轮减少1）
     * @return 每轮淘汰顺序及最终胜者
     */
    public GameResult simulateByLinkedList(List<String> players, int chairs) {
        int n = players.size();
        if (n == 0) return new GameResult(new ArrayList<>(), null);
        if (chairs >= n) {
            // 椅子足够，无人淘汰
            return new GameResult(new ArrayList<>(), players.get(0));
        }

        // 构建循环链表
        Node head = new Node(0, players.get(0));
        Node current = head;
        for (int i = 1; i < n; i++) {
            current.next = new Node(i, players.get(i));
            current = current.next;
        }
        current.next = head; // 首尾相连

        List<String> eliminationOrder = new ArrayList<>();
        Node prev = current; // 指向尾节点，便于删除
        current = head;
        int remaining = n;
        int currentChairs = chairs;

        // 每轮淘汰 (remaining - currentChairs) 人
        while (remaining > 1) {
            int eliminateCount = remaining - currentChairs;
            if (eliminateCount <= 0) break;

            for (int i = 0; i < eliminateCount; i++) {
                // 随机步长模拟音乐停止的随机性（简化用固定步长）
                int step = (int) (Math.random() * remaining) + 1;

                // 移动 step 步
                for (int j = 0; j < step - 1; j++) {
                    prev = current;
                    current = current.next;
                }

                // 淘汰 current 节点
                eliminationOrder.add(current.name);
                prev.next = current.next;
                current = current.next;
                remaining--;
            }

            currentChairs--; // 撤掉一把椅子
            if (currentChairs < 1) currentChairs = 1;
        }

        return new GameResult(eliminationOrder, current.name);
    }

    /**
     * 经典约瑟夫问题：数学递推解法 O(n)
     * @param n 总人数
     * @param k 步长（每数到k的人淘汰）
     * @return 幸存者编号（0-based）
     */
    public int josephusMath(int n, int k) {
        int survivor = 0; // f(1, k) = 0
        for (int i = 2; i <= n; i++) {
            survivor = (survivor + k) % i;
        }
        return survivor;
    }

    /**
     * 约瑟夫问题：循环链表模拟解法
     * @param n 总人数
     * @param k 步长
     * @return 幸存者编号
     */
    public int josephusLinkedList(int n, int k) {
        if (n <= 0) return -1;

        // 构建循环链表 0 -> 1 -> 2 -> ... -> n-1 -> 0
        Node head = new Node(0, "P0");
        Node current = head;
        for (int i = 1; i < n; i++) {
            current.next = new Node(i, "P" + i);
            current = current.next;
        }
        current.next = head;

        Node prev = current;
        current = head;
        int remaining = n;

        while (remaining > 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.id;
    }

    /**
     * 记录每轮淘汰顺序的详细模拟
     * @param n 总人数
     * @param k 步长
     * @return 淘汰顺序列表
     */
    public List<Integer> getEliminationOrder(int n, int k) {
        List<Integer> order = new ArrayList<>();
        if (n <= 0) return order;

        Node head = new Node(0, "P0");
        Node current = head;
        for (int i = 1; i < n; i++) {
            current.next = new Node(i, "P" + i);
            current = current.next;
        }
        current.next = head;

        Node prev = current;
        current = head;
        int remaining = n;

        while (remaining > 1) {
            for (int i = 0; i < k - 1; i++) {
                prev = current;
                current = current.next;
            }
            order.add(current.id);
            prev.next = current.next;
            current = current.next;
            remaining--;
        }
        order.add(current.id); // 最后幸存者也加入

        return order;
    }

    // 结果封装
    public static class GameResult {
        public final List<String> eliminationOrder;
        public final String winner;

        public GameResult(List<String> eliminationOrder, String winner) {
            this.eliminationOrder = eliminationOrder;
            this.winner = winner;
        }
    }

    public static void main(String[] args) {
        MusicalChairs game = new MusicalChairs();

        // 测试1：经典约瑟夫问题
        int n = 10, k = 3;
        System.out.println("=== 经典约瑟夫问题 ===");
        System.out.println("n=" + n + ", k=" + k);
        System.out.println("数学递推结果: 幸存者编号 = " + game.josephusMath(n, k));
        System.out.println("链表模拟结果: 幸存者编号 = " + game.josephusLinkedList(n, k));
        System.out.println("淘汰顺序: " + game.getEliminationOrder(n, k));

        // 测试2：抢椅子模拟
        System.out.println("\n=== 抢椅子游戏模拟 ===");
        List<String> players = new ArrayList<>();
        for (int i = 1; i <= 8; i++) {
            players.add("玩家" + i);
        }
        GameResult result = game.simulateByLinkedList(players, 5);
        System.out.println("淘汰顺序: " + result.eliminationOrder);
        System.out.println("最终胜者: " + result.winner);
    }
}

复杂度分析

数学递推法利用问题的最优子结构特性，通过动态规划思想将指数级复杂度降至线性，是算法优化的典范。

扩展思考

• 变步长约瑟夫问题：若每轮步长 k 动态变化，数学公式不再适用，只能使用链表模拟。
• 多幸存者场景：要求最后留下 m 个人，只需修改终止条件为 remaining > m。
• 双向约瑟夫问题：参与者围成双向链表，可顺时针或逆时针报数，增加策略维度。
• 概率模型：真实抢椅子中音乐停止时机是随机的，可引入泊松过程建模音乐持续时间。