Josephus Circle
Intuition
用 f(n)
表示在 n 个人的约瑟夫环里,最后的胜利者的下标。
如果这是一个 1 环约瑟夫问题,即只有一个人的话,那被选中的那个人就一定是下标为 0 的人,可以得到:
f(1) = 0
如果这是 2 环约瑟夫问题,f(2)
的值为 f(1)
中下标为 0 的那个人(最后的胜利者)在两个人时候的下标,所以找到一个 n
到 n - 1
情况下标的映射关系就好了。
找到这个关系的过程是一个逆向的过程,n 环约瑟夫环问题 可以化解成 n - 1 环约瑟夫环问题。
模拟一下约瑟夫环的过程,下标从 0 开始:
0, 1, ... , m - 2,
m - 1, m, ..., n - 2, n - 1 (m - 1个被删去)0, 1, ... , m - 2, m, ..., n - 2, n - 1 (从 m 开始重新计数)
n - m, n - m + 1, ..., n - 2, 0, ..., n - 2 - m, n - 1 - m (然后把 0 重新提到最前面)
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
Last updated