约瑟夫环

约瑟夫环。感觉刚上大学的时候见过这个题目,昨天做笔试题的时候遇到了。。第一反应就是链表。。复杂度 $O(nm)$。不过数据也是水,也是过了。。

然后事后才知道这是约瑟夫环。用数学递推公式可以降到 $O(n)$。

推导

推导的过程是一个逆向的过程,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。

然后可以发现 在 n = 1 时,被删去的元素一定是下标为 0 的点

然后推出两个结论,f(n) 表示 n 环约瑟夫环问题 中被删掉元素下标:

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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 ;
}