约瑟夫环的思考

• 2019 年 07 月 04 日
• 289 次阅读
• 416 字
• 暂无评论

写在前面

很久没学习了。
被前队友拉去看了一个简单的入门级算法题吧。
应该是很久之前就看过的东西
凭我这个记性，很明显是忘了
重新看一下 记录一下

问题描述

N个人围绕一圈报数， 喊道m的人被处死， 下一个人从头开始继续报数 为最后唯一生存者是第几个人。

解法

解法一 自然是用链表模拟 复杂度O(n*m) 爆炸复杂度

解法二 公式法

主要思考如何解释推到该公式

看到一篇博客特别好，解释的十分清楚
先抛出一个样例

如果9个人喊道3的人被处死 那么生存着是第几个

给每个人编号从1开始

​ 有1 2 3 4 5 6 7 8 9

​ 第一轮从1开始报数 3被处死

​ 第二轮从4开始报数 6被处死

​ 第三轮从7开始报数 9被处死

......

​ 由上表表可知最后幸存者为1号

不妨 设F(n,m) = x  //n个人 ，喊道m被处死 幸存者的下标为x
那么
    F(1,3)=0 
    F(2,3)= 1 = F( F(1,3) + 3)%2  
    F(3,3)= 1 = F( F(2,3) + 3)%3
    F(4,3)= 0 = F( F(2,3) + 3)%4
    F(5,3)= 3 = F( F(2,3) + 3)%5
    F(6,3)= 0 = F( F(2,3) + 3)%6
    F(7,3)= 3 = F( F(2,3) + 3)%7
    F(8,3)= 6 = F( F(2,3) + 3)%8
    F(9,3)= 0 = F( F(2,3) + 3)%9

感觉一脸懵逼？ 怎么推导的？

现在开始推导公式

简单点讲:

​ 每一次死的都是 下标为2(喊到3)的人死

​ 死去的人的下一个人下标向前挪三位 然后开始从1报数

​ 因为人越死越少 所以会产生循环 所以模一个当前剩余人数(死人不会报数)

以此类推 N个人 喊道m被处死 数组如何移动？

​ 每杀掉一个人，下一个人成为头，即数组整体向前挪m位

​ 如果已知F(n-1,m) = x

​ 则 F(n,m) =(x + m) % n

从F(1 , m) = 0 逆向递推至n 得到 F(n,m)结果

代码实现

int cir(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}