约瑟夫问题：古代将军的生存策略 - Java循环链表实现

约瑟夫问题：古代将军的生存策略 - Java循环链表实现

约瑟夫问题是一个经典的数学问题，讲述了古代犹太将军约瑟夫在罗马叛乱中利用巧妙的策略保全自己和朋友的故事。

故事背景：约瑟夫，曾经在一次罗马叛乱中担任将军，后来战败，他和朋友及另外39个人躲在一口井里，但还是被发现了。罗马人表示只要投降就不死，约瑟夫想投降，可是其他人坚决不同意。怎么办呢，他想到一个主意: 让41个人围成一个圆圈，从第一个人开始报数，数到3的那个人被旁边的人杀死。这样就可以避免自杀了，因为犹太人的信仰是禁止自杀的。结果一群人杀来杀去最后只剩下两个了，就是约瑟夫和他朋友，于是两人愉快地去投降了。

问题: 约瑟夫和朋友站在什么位置才保住了性命？

解决方案: 使用顺序表和循环链表实现过程（报数，移除圈)，并输出结果（幸存者的位置)。

使用 Java 代码实现

使用循环链表来解决该问题是比较方便的，因为每次移除一个元素后，下一个元素仍然可以通过下一个节点来访问。下面是使用 Java 代码实现的例子：

import java.util.LinkedList;

public class JosephusProblem {
    public static int findSurvivor(int n, int k) {
        // 创建循环链表
        LinkedList<Integer> circle = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            circle.add(i);
        }

        int index = 0;
        while (circle.size() > 1) {
            // 计算要移除的元素位置
            index = (index + k - 1) % circle.size();
            // 移除元素
            circle.remove(index);
        }

        // 返回最后剩下的元素
        return circle.get(0);
    }

    public static void main(String[] args) {
        int n = 41; // 总人数
        int k = 3; // 报数到k的人被杀死
        int survivor = findSurvivor(n, k);
        System.out.println('幸存者的位置是：' + survivor);
    }
}

输出结果：

幸存者的位置是：31

所以，约瑟夫和他的朋友站在位置31才保住了性命。