对于给出的n个人,每隔k个人退出一个,第一次退出第m个人的约瑟夫环:
首先考虑从0开始编号,从第k个开始退出的情况。
则第k人退出后,约瑟夫环变为了:给出 n – 1 个人,每隔 k 个人退出一个 新约瑟夫环问题。给新环重新编号,与旧环建立的映射为:
k+1 => 0
k+2 => 1
…
k – 1 => n-2
假设 n-1 个人的约瑟夫环退出的人的编号为 x , 那么该人在 n 个人的环中的编号应该是 (x + k) % n
设f[n]表示,有N个人的约瑟夫环问题,最后退出的人的编号,则由上可得到递推式:
f[n] = (f[n-1] + k) % n
那么一个人的约瑟夫环的人必然是赢家,且编号为0,即: f[1] = 0
接下来可以使用递推得到最后结果。
最后对于f[n], 因为我们考虑的是从编号为 k 的开始,而题目要求从第 m 个开始退出,则需要旋转一下。
答案为 f[n] + m +1 – k。。
# include <cstdio> int n, m, k; int f[10003]; int main() { while ( scanf("%d%d%d", &n, &k, &m) == 3, n ) { f[1] = 0; for (int i = 2; i <= n; ++i ) f[i] = (f[i-1] + k) % i; int ans = ( f[n] + m - k + 1) % n; if ( ans <= 0 ) ans += n; printf("%d\n", ans); } return 0; }