约瑟夫环问题（二）：（难度：2颗星）

r囧r小猫 2022-06-13 23:19 202阅读 0赞

问题描述：

编号为1,2,…,n的n个人按顺时针方向围坐一圈，任选一个正整数作为报数上限m,从第一个人开始按顺时针方向从自1开始顺序报数,报道m时停止报数.报m的人出列,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止,输出最后一个出列的人的编号。

输入输出描述：

m和n由用户输入，并且保证m和n的范围是【1,10000000】，输出最后出列的编号。

问题分析：

为了方便说明，我们稍微转换一下，假定标号是0到n-1，报数从0到m-1（主要是因为m%n是可能等于0的，这样的转换方便后面的运算），反正最后的结果加1就可以了。

假定当前序列的人数是n，则第一个出列的人的编号是(m-1) % n，下一次报数的人的编号为m%n，令k=m%n，我们重新对剩下的n-1个人进行组织，可以得到如下对应关系：

k->0  
k+1->1  
k+2->2  
k+3->3  
k+4->4  
……..  
k-4->n-4  
k-3->n-3  
k-2->n-2  
k-1->n-1

这个过程实际就是n个人的约瑟夫环问题降为了n-1个人的约瑟夫环问题，用同样的方法，我们可以得到n-2个人的约瑟夫环问题，一直到1个人的约瑟夫环问题，从这个不断缩小规模的过程中，我们可以发现编号的对应关系，如果在n-1个人的情况下某个人的编号是x，那么这个人在n个人的情况下的编号一定是(x+k)%n

同理，如果我们求出t个人玩的时候最后出局的人标号为f(t)，那么t+1个人玩的时候出局的编号就是（f(t) + k）%（t+1）

最后结果总结成一个递推关系是为：  
f(n)=(f(n-1)+k)%n=(f(n-1)+m%n)%n=(f(n-1)+m)%n

PS：

如果是要求出这个约瑟夫环的出队序列，可以参考我的另外一篇文章：

[http://blog.csdn.net/yi\_ming\_he/article/details/72859577][http_blog.csdn.net_yi_ming_he_article_details_72859577]

参考代码：

#include <stdio.h>
    
    int main()
    {
        int ans = 0, i, n, m;
        scanf_s("%d%d", &n, &m);
        for (i = 1; i <= n; i++)
            ans = (ans + m) % i;
    
        //因为开始是从0开始的，还原原来的问题所以加1
        printf("%d\n", ans + 1);
    
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[http_blog.csdn.net_yi_ming_he_article_details_72859577]: http://blog.csdn.net/yi_ming_he/article/details/72859577
[SouthEast]: /images/20220614/5c1f9c4d1df54eb395605ae0a6f763f9.png