约瑟夫问题

约瑟夫问题（Josephus Problem）

约瑟夫问题是一个经典的数学和计算机科学问题，属于递归与循环算法的典型案例。其核心是模拟一群人围成圈，按固定规则依次淘汰成员，最终寻找最后剩下的人的位置。

问题背景

传说源于古罗马历史学家约瑟夫斯（Flavius Josephus）的真实经历：在公元 1 世纪的犹太战争中，约瑟夫斯和 40 名士兵被罗马军队围困，他们约定围成一圈，从第 1 个人开始报数，每数到第 3 个人就将其杀死，直到最后一人。约瑟夫斯通过数学计算找到了最后存活的位置，从而保住了自己的性命。

问题描述

标准问题：

有 n 个人围成一圈，从第 1 个人开始依次报数，当报到 k 时，该人被淘汰；然后从下一个人开始重新报数，重复此过程，直到最后只剩下 1 个人。求最后存活者的初始位置（通常从 1 开始计数）。

数学解法（递归公式）

当 (k = 2) 时（最常见的简化版本），存在简洁的递归公式：

设 (f(n)) 表示 n 个人时最后存活者的位置，则：(f(n) = (f(n-1) + 2) % n)

边界条件：(f(1) = 0)（若从 0 开始计数）或 (f(1) = 1)（若从 1 开始计数）。

• 若从 1 开始计数，公式可调整为：(f(n) = (f(n-1) + k) % n) 若结果为 0，则存活位置为 n，否则为计算结果。

public class JosephusGeneral {
    public static int josephus(int n, int k) {
        int position = 0; // 从0开始计数
        for (int i = 2; i <= n; i++) {
            position = (position + k) % i;
        }
        return position + 1; // 转换为从1开始的编号
    }

    public static void main(String[] args) {
        int n = 7;
        int k = 3;
        System.out.println("最后存活者的位置是：" + josephus(n, k)); // 输出4
    }
}

通用解法（算法模拟）

对于任意 k 值，可通过循环或递归模拟淘汰过程：

1. 初始化：用列表或数组表示围成圈的人（编号 1 到 n）。
2. 循环淘汰：
   • 从当前位置开始，数到第 k 个人（需处理越界问题，用取模运算实现循环）。
   • 移除被淘汰的人，更新当前位置为下一个人的索引。
3. 终止条件：当列表中只剩 1 人时，返回其编号。

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

public class JosephusProblem {
    public static int josephus(int n, int k) {
        List<Integer> people = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            people.add(i);
        }
        
        int index = 0;
        while (people.size() > 1) {
            // 计算要移除的人的索引
            index = (index + k - 1) % people.size();
            people.remove(index);
        }
        return people.get(0); // 返回最后剩下的人的编号
    }

    public static void main(String[] args) {
        int n = 7;  // 总人数
        int k = 3;  // 每数到第k个人淘汰
        System.out.println("最后存活者的位置是：" + josephus(n, k)); // 输出4
    }
}

示例

• 案例 1：(n = 7)，(k = 3) 淘汰顺序：3 → 6 → 2 → 7 → 5 → 1，最后存活者为 4。
• 案例 2：(n = 10)，(k = 2) 按公式计算，存活位置为 5（从 1 开始计数）。

应用场景

• 计算机科学：算法设计（递归、循环、链表操作）的经典例题。
• 数学：数论中的递归关系研究。
• 实际问题：如轮盘游戏、资源分配策略、密码学中的随机选择等。

通过数学公式可高效求解 (k = 2) 的情况，而通用模拟法则适用于任意 k，但时间复杂度为 (O(nk))，对于大 n 需优化（如使用线段树或二叉树降低复杂度至 (O(n \log n))）。