约瑟夫环问题的递推方法

对于给出的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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>