写在前面
很久没学习了。
被前队友拉去看了一个简单的入门级算法题吧。
应该是很久之前就看过的东西
凭我这个记性,很明显是忘了
重新看一下 记录一下
问题描述
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号
不妨 设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;
}
—— 暂无评论 ——