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

问题描述

约瑟夫环（Josephus Problem）源于一个历史故事：n个人围成一圈，从第一个人开始报数，报到m的人出局，接着从下一个人重新开始报数，直到所有人出局。求幸存者的初始编号，或输出淘汰顺序。

该问题是递归与循环的经典训练素材，在操作系统调度、分布式选举等场景中有广泛应用。

解法一：循环链表模拟

最直观的方法是构建循环链表，按规则依次移除节点。

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

public class JosephusLinkedList {

    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    // 循环链表模拟，返回淘汰顺序
    public static List<Integer> josephus(int n, int m) {
        if (n <= 0 || m <= 0) return new ArrayList<>();

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

        List<Integer> order = new ArrayList<>();
        Node prev = cur; // prev指向当前节点的前一个，便于删除
        cur = head;
        int count = n;

        while (count > 0) {
            // 向前移动 m-1 步
            for (int i = 1; i < m; i++) {
                prev = cur;
                cur = cur.next;
            }
            // 淘汰当前节点
            order.add(cur.val);
            prev.next = cur.next;
            cur = cur.next;
            count--;
        }
        return order;
    }

    public static void main(String[] args) {
        int n = 7, m = 3;
        System.out.println("淘汰顺序: " + josephus(n, m));
        // 输出: [3, 6, 2, 7, 5, 1, 4]
    }
}

时间复杂度 O(n×m)，空间复杂度 O(n)。当 m 较大时效率较低。

解法二：递归分治

设 f(n, m) 表示 n 个人报数 m 时幸存者的编号（0 起始）。递推关系：

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

public class JosephusRecursion {

    // 递归求解幸存者编号（0起始），结果+1转为1起始
    public static int josephusRec(int n, int m) {
        if (n == 1) return 0;
        return (josephusRec(n - 1, m) + m) % n;
    }

    // 迭代版本避免栈溢出
    public static int josephusIter(int n, int m) {
        int res = 0; // f(1, m) = 0
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 7, m = 3;
        System.out.println("幸存者(递归): " + (josephusRec(n, m) + 1));
        System.out.println("幸存者(迭代): " + (josephusIter(n, m) + 1));
    }
}

时间复杂度 O(n)，空间复杂度 O(1)（迭代版）。

复杂度对比

总结

约瑟夫环展现了从暴力模拟到数学优化的经典过程。当问题规模增大时，寻找递推规律往往比直接模拟更高效。读者可尝试扩展：若每次报数上限 m 动态变化，应如何调整策略？