josephus环问题 java

Josephus环问题是源于罗马帝国时期的数学问题，也称为“约瑟夫斯问题”或“隔数删除问题”。它描述了一个由n个人组成的圆圈，从第一个人开始按顺序报数，每次跳过k个人，直到只剩下一个幸存者。在Java中解决这个问题通常涉及到循环和条件判断。

以下是基本的算法步骤：
1. 定义一个数组模拟人员环，每个人表示数组的一个元素。
2. 初始化计数器为1，表示第一个报数的人。
3. 使用while循环，每次迭代将计数器加k并移动到数组的下一个位置，直到计数器等于数组长度减去1（因为最后一个幸存者不需要移动）。
4. 当只剩下一个人时，跳出循环，这个人就是最后的幸存者。

以下是一个简单的Java函数实现：

public int josephus(int n, int k) {
    int[] circle = new int[n];
    for (int i = 0; i < n; i++) {
        circle[i] = i + 1;
    }
    int step = 1;
    while (circle.length > 1) {
        step = (step + k - 1) % circle.length;
        circle = Arrays.copyOf(circle, circle.length - 1);
    }
    return circle[0];
}

相关问题

用顺序表解决约瑟夫环问题Java代码

约瑟夫环问题是这样的：给定一个正整数n和一个初始值k，从0到n-1这n个人排成一圈，编号为0、1、2...n-1。从第k个人开始报数，每个人报完数后跳过下一个数，如果轮到的人数为0，则下一个人开始报数。直到有人再次报到0。

下面是使用顺序列表（数组）解决约瑟夫环问题的一个简单Java代码示例：

public class JosephusRing {
    public static int josephus(int n, int k) {
        if (n <= 0 || k <= 0) {
            throw new IllegalArgumentException("Invalid input: n and k must be positive integers.");
        }

        // 创建循环数组并初始化计数器
        int[] ring = new int[n];
        for (int i = 0; i < n; i++) {
            ring[i] = i;
        }
        int index = k - 1;

        while (ring.length > 1) {
            // 报数并删除当前元素
            index = (index + 1) % ring.length;
            ring[index] = 0; // 使用0表示已删除
        }

        // 最后一个存活的人即为结果
        return ring[0];
    }

    public static void main(String[] args) {
        int n = 7, k = 3;
        System.out.println("The last person standing is: " + josephus(n, k));
    }
}

在这个代码中，我们首先检查输入是否有效，然后创建一个大小为n的数组作为环形结构，并从第k个人开始报数。每次循环中，我们都将当前索引加一，然后取模保持在合法范围内，同时删除该位置的人（将其置零）。当只剩下一个人时，就找到了最后的幸存者。

JAVA环形单链表约瑟夫环问题

Java环形单链表版本的约瑟夫环问题（Josephus Problem）是一个经典的计算机科学问题，源于一种古老的数学游戏。在一个循环排列的人群中，按照一定的步长（通常从某个特定位置开始计数），每隔一步就处死一个人，直到剩下最后一个人为止。在链表版本中，你需要设计算法找出最后一个存活下来的人的索引。

例如，如果链表有n个节点，步长为k，那么第一个节点就是起始点。为了解决这个问题，可以采用模运算的方式。从头节点开始，每次移动k个节点，然后删除这个节点，更新头节点。当链表只剩下一个节点时，那个节点就是解决方案。

以下是解决该问题的一个基本步骤伪代码示例：

ListNode josephus(ListNode head, int k) {
    ListNode slow = head;
    ListNode fast = head;

    // 找到环形链表的长度
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }

    // 如果不是环形链表，返回null
    if (fast == null || fast.next == null) {
        return null;
    }

    // 计算步长k在环形链表中的实际位置
    slow = slow.next;
    for (int i = 0; i < k - 1; i++) {
        slow = slow.next;
    }

    // 从慢指针开始遍历，找到生存者
    while (slow.next != head) {
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}