约瑟夫环的思考

发表于 | 更新于: | 分类于 |
字数统计: 637 字 | 阅读时长 ≈ 2 分钟

写在前面

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

问题描述

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

解法

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

解法二 公式法
主要思考如何解释推到该公式
看到一篇博客特别好，解释的十分清楚
先抛出一个样例
如果9个人喊道3的人被处死 那么生存着是第几个

给每个人编号从1开始

​ 有1 2 3 4 5 6 7 8 9

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

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

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

……

0 1 2* 3 4 5 6 7 8
1 2 3* 4 5 6 7 8 9
4 5 6* 7 8 9 1 2 ..
7 8 9* 1 2 4 5 .. ..
1 2 4* 5 7 8 .. .. ..
5 7 8* 1 2 .. .. .. .
1 2 5* 7
7 1 2*
7* 1
1 W

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

1
2
3
4
5
6
7
8
9
10
11
不妨 设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)结果

代码实现

1
2
3
4
5
6
7
8
9
int cir(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}
0%