每日算法 — 使用java实现约瑟夫环：递推公式与循环链表模拟

问题描述

约瑟夫环（Josephus Problem）是一个经典的数学问题：有 n 个人围成一圈，从第一个人开始报数，数到 m 的人出列，然后从下一个人重新开始报数，直到所有人出列。求出列顺序，或求最后幸存者的编号。

这个问题历史悠久，传说由犹太历史学家约瑟夫提出。它在计算机科学中常用于讲解递归、递推和循环链表等数据结构。

算法思路

方法一：数学递推公式（O(n)）

设 f(n, m) 表示 n 个人、步长为 m 时最后幸存者的编号（0-based）。

递推关系：

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

推导过程：第一次淘汰的是 (m-1) % n，剩下的 n-1 个人构成一个子问题。子问题的解 f(n-1, m) 是在新编号体系下的答案，映射回原编号需要加上 m 并对 n 取模。

方法二：循环链表模拟（O(nm)）

使用循环链表模拟报数过程，逐个删除节点，直观但时间复杂度较高，适合理解问题本质。

Java实现

递推公式解法

public class JosephusMath {
    /**
     * 使用递推公式求解最后幸存者的编号（0-based）
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param n 总人数
     * @param m 报数步长
     * @return 最后幸存者的编号（0-based）
     */
    public static int lastSurvivor(int n, int m) {
        if (n <= 0 || m <= 0) {
            throw new IllegalArgumentException("n and m must be positive");
        }
        int result = 0; // f(1, m) = 0
        for (int i = 2; i <= n; i++) {
            result = (result + m) % i;
        }
        return result;
    }

    /**
     * 使用递推公式求出列顺序（1-based）
     *
     * @param n 总人数
     * @param m 报数步长
     * @return 依次出列的人的编号（1-based）
     */
    public static int[] eliminationOrder(int n, int m) {
        if (n <= 0 || m <= 0) {
            throw new IllegalArgumentException("n and m must be positive");
        }
        int[] order = new int[n];
        // 使用List模拟，记录当前存活的人
        java.util.ArrayList<Integer> alive = new java.util.ArrayList<>();
        for (int i = 1; i <= n; i++) {
            alive.add(i);
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            index = (index + m - 1) % alive.size();
            order[i] = alive.remove(index);
        }
        return order;
    }

    public static void main(String[] args) {
        int n = 7, m = 3;
        System.out.println("总人数：" + n + "，步长：" + m);
        System.out.println("最后幸存者（0-based）：" + lastSurvivor(n, m));
        System.out.println("最后幸存者（1-based）：" + (lastSurvivor(n, m) + 1));
        System.out.print("出列顺序：");
        for (int num : eliminationOrder(n, m)) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

循环链表解法

/**
 * 循环链表节点
 */
class CircularNode {
    int value;
    CircularNode next;

    CircularNode(int value) {
        this.value = value;
    }
}

public class JosephusLinkedList {
    /**
     * 使用循环链表模拟约瑟夫环
     * 时间复杂度：O(n × m)
     * 空间复杂度：O(n)
     *
     * @param n 总人数
     * @param m 报数步长
     * @return 依次出列的人的编号
     */
    public static int[] simulate(int n, int m) {
        if (n <= 0 || m <= 0) {
            throw new IllegalArgumentException("n and m must be positive");
        }

        // 构建循环链表：1 -> 2 -> 3 -> ... -> n -> 1
        CircularNode head = new CircularNode(1);
        CircularNode current = head;
        for (int i = 2; i <= n; i++) {
            current.next = new CircularNode(i);
            current = current.next;
        }
        current.next = head; // 形成环

        int[] result = new int[n];
        CircularNode prev = current; // prev指向最后一个节点，便于删除
        current = head;

        for (int i = 0; i < n; i++) {
            // 前进m-1步到达要删除的节点
            for (int j = 1; j < m; j++) {
                prev = current;
                current = current.next;
            }
            result[i] = current.value;
            // 删除当前节点
            prev.next = current.next;
            current = current.next;
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 7, m = 3;
        System.out.print("循环链表模拟出列顺序：");
        for (int num : simulate(n, m)) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

复杂度分析

扩展与应用

1. 变体问题：步长 m 动态变化、双向报数、多 survivors 等情况
2. 实际应用：资源轮询调度（如Nginx的ip_hash）、分布式系统中的令牌环、负载均衡策略
3. 数学延伸：与模运算、组合数学、递归思想密切相关

总结

约瑟夫环问题展示了同一问题可以有截然不同的解法。数学递推公式利用问题的递归结构，将时间复杂度从朴素的 O(n²) 或 O(n × m) 优化到 O(n)，是算法优化的经典范例。理解递推关系的建立过程，对解决其他递归问题具有重要的启发意义。