Josephus Circle

Intuition

f(n) 表示在 n 个人的约瑟夫环里,最后的胜利者的下标。

如果这是一个 1 环约瑟夫问题,即只有一个人的话,那被选中的那个人就一定是下标为 0 的人,可以得到:

  • f(1) = 0

如果这是 2 环约瑟夫问题,f(2) 的值为 f(1) 中下标为 0 的那个人(最后的胜利者)在两个人时候的下标,所以找到一个 nn - 1 情况下标的映射关系就好了。

找到这个关系的过程是一个逆向的过程,n 环约瑟夫环问题 可以化解成 n - 1 环约瑟夫环问题

模拟一下约瑟夫环的过程,下标从 0 开始:

  1. 0, 1, ... , m - 2, m - 1, m, ..., n - 2, n - 1 (m - 1个被删去)

  2. 0, 1, ... , m - 2, m, ..., n - 2, n - 1 (从 m 开始重新计数)

  3. n - m, n - m + 1, ..., n - 2, 0, ..., n - 2 - m, n - 1 - m (然后把 0 重新提到最前面)

  4. 0, 1, ..., n - 2

这就是 n 环约瑟夫环问题 变成了 n - 1 环约瑟夫环问题 的过程了。

可以发现在 n - 1 环约瑟夫环问题 中下标为 k 的元素,在 n 环约瑟夫环问题 中对应的下标是 k + m。当然还要取一下余,所以对应关系为 (k + m) % n

结合两个结论,得到两个关系式:

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

  • f(1) = 0

Solution

#include <stdio.h>

int main()
{
    int n, m, i, s = 0;

    scanf("%d%d", &n, &m);

    for (i = 2; i <= n; i++)
        s = (s + m) % i;

    printf ("%d\n", s);
    return 0 ;
}

Last updated