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)。