josephus问题java

Josephus问题是一个经典的算法问题，描述如下：有n个人围成一圈，从第一个人开始报数，数到m的人出圈，然后从下一个人开始重新报数，数到m的人再次出圈，直到所有人都出圈为止。问最后剩下的人在原序列中的位置是多少？

下面是Java的解法：

public static int josephus(int n, int m) {
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + m) % i;
    }
    return ans + 1;
}

解释如下：

假设f(n,m)表示n个人中，每数到第m个人出圈最后剩下的人的编号，那么对于n个人来说，第一个出圈的人是(m-1)%n，剩下的人继续围成一圈，从第(m-1)%n+1个人开始重新报数。

因此，可以得到递推公式：

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

其中，f(1,m) = 0，因为只有一个人时，无需报数，直接出圈。

最后剩下的人的编号就是f(n,m)+1。

时间复杂度为O(n)。

相关问题

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递归

约瑟夫环（Josephus Problem）是一个经典的算法问题，源于一个古老的罗马游戏，参与者按顺序站立成一圈，然后从某个人开始按照给定的步长（通常称为“跳过”数）逐个报数，达到特定数的人会被淘汰并离开圈子，直到剩下最后一个人为止。在 Java 中使用递归解决这个问题可以分为以下几个步骤：

1. 定义基本情况：如果圈里只剩一个人（即步长大于当前人数），那么这个人就是胜利者，返回0作为他的位置。

2. 递归处理：对于其他情况，计算下一个人的位置，即当前人的索引加上步长，并对总数取模，以保持在范围内。然后递归地在剩余的人中继续这个过程，直到满足基本情况。

这是一个典型的动态规划问题，递归函数的伪代码可以这样描述：

public int josephus(int n, int k) {
    if (n == 1) { // 基本情况
        return 0;
    } else {
        return (josephus(n - 1, k) + k) % n; // 递归调用，更新索引
    }
}

在这个函数中，`n` 表示初始人数，`k` 表示跳过的人数。调用 `josephus(n, k)` 就能得到第一个被淘汰者的起始位置。