java使用递归实现约瑟夫环问题代码

以下是Java实现约瑟夫环问题的递归代码：

public static int josephus(int n, int k) {
    if (n == 1) {
        return 0;
    } else {
        return (josephus(n - 1, k) + k) % n;
    }
}

其中n代表总人数，k代表每隔k个人进行一次淘汰。函数返回的是最后留下的人的编号（从0开始计数）。

相关问题

JAVA约瑟夫环问题链表代码

约瑟夫环问题是一个经典的计算机科学问题，涉及将一组人围成一圈，从某个人开始按顺序报数，每次跳过一个人，直到只剩下最后一个人为止。在Java中解决这个问题，我们可以使用链表来模拟环形结构，并通过迭代或递归的方式来找到最后剩下的那个人。

这里是一个简单的迭代解约瑟夫环问题的链表代码示例：

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class JosephusRing {
    private Node head;
    private int step;

    public JosephusRing(int k) {
        this.step = k;
    }

    // 添加节点到环中
    public void insertNode(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    // 解决约瑟夫环问题
    public Node findLastMan Standing() {
        if (head == null || step <= 0) {
            return null;
        }
        Node slow = head;
        Node fast = head;
        for (int i = 1; fast != null && fast.next != null; i++) {
            fast = fast.next.next;
            if (i % step == 0) {
                slow = slow.next;
            }
        }
        return slow;
    }
}

// 使用示例
public static void main(String[] args) {
    JosephusRing josephus = new JosephusRing(3); // 设置步长为3
    // 插入节点...
    Node lastStanding = josephus.findLastManStanding();
    System.out.println("当步长为3时，最后站着的是节点值为 " + lastStanding.data);
}

在这个代码中，我们首先创建了一个`JosephusRing`类，它有一个头结点和步长变量。然后有`insertNode`方法用于添加节点，以及`findLastManStanding`方法用于计算在给定步长下谁会是最后一个站在圈子里的人。

java约瑟夫环问题实现

### Java 实现约瑟夫环算法

#### 方法一：List 模拟删除

在该方法中，`ArrayList` 被用来存储参与者编号。每次迭代时，程序会按照指定步长移除列表中的元素直到只剩下一个元素为止。

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

public class JosephusProblem {
    public static int findLastSurvivor(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            list.add(i);
        }
        
        int index = 0;
        while (list.size() > 1) {
            index = (index + m - 1) % list.size();
            list.remove(index);
        }

        return list.get(0);
    }

    public static void main(String[] args) {
        System.out.println(findLastSurvivor(5, 3)); // 输出最后一个幸存者的索引位置
    }
}

此方式直观易懂，但效率较低，在处理大规模数据集时性能不佳[^1]。

#### 方法二：动态规划加递归

这种方法利用了数学归纳法的思想来解决问题。对于给定的人数 `n` 和计数值 `m` ，可以通过求解更小规模子问题的结果得到最终答案：

\[ f(n,m)=(f(n−1,m)+m)\%n \]

其中 \( f(n,m) \) 表示当有 `n` 个人参与游戏并每隔 `m` 报数一次的情况下最后存活者的位置；初始条件为 \( f(1,k)=0 \)，即只有一个人的时候其总是胜利者[^2]。

public class JosephusProblemDP {

    private static int josephus(int n, int k){
        if (n == 1)
            return 0;
        else
           return(josephus(n - 1, k) + k) % n;
    }

    public static void main(String[] args) {
        System.out.println(josephus(5, 3));
    }
}

这种方案不仅逻辑清晰而且计算复杂度低得多，适合用于较大范围内的输入参数[^4]。

#### 方法三：基于位运算优化的线性时间复杂度算法

考虑到上述两种方法都存在一定的局限性——前者空间占用高而后者虽然节省内存却难以理解。因此这里介绍一种更为高效的解决方案，它能够在线性时间内完成计算而不依赖额外的数据结构支持:

设总人数为N，则第k轮报到M号被处决后的剩余序列长度L=N-k*M；
此时新起点位于原起点之后K*(M-1)%L处；
重复以上过程直至剩下最后一人即可获得结果。

public class OptimizedJosephusSolution {

    public static int solveOptimized(int N, int M) {
        int pos = 0; // 初始化第一个安全位置
        
        for (int i = 2; i <= N; ++i) {
            pos = (pos + M) % i;
        }

        return pos;
    }

    public static void main(String[] args) {
        System.out.println(solveOptimized(5, 3));
    }
}

这段代码实现了O(N)的时间复杂度，并且只需要常量级别的辅助空间就能得出正确结论[^3]。