目录

zrlong 的个人博客

希望大家都能保护好自己身上的特质,无论是五年还是十年,永远善良,不服输,热爱你所热爱。在漫长岁月的变迁里,是这些让你永远迷人,富有生命力。

X

约瑟夫环

约瑟夫问题

约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。

解决方法

模拟法

刚学数据结构的时候,我们可能用链表的方法去模拟这个过程,N个人看作是N个链表节点,节点1指向节点2,节点2指向节点3,……,节点N-1指向节点N,节点N指向节点1,这样就形成了一个环。然后从节点1开始1、2、3……往下报数,每报到M,就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

缺点

可以想象如果数据量特别大时,算法的时间复杂度非常高,高达O(nm)。

公式法

既然没办法暴力解决,那我们就来找找其中的规律。

// 我们规定数到三的人出圈
// 当有1个人时,最终留下来的下标为0
f(1,3) = 0;
// 当有2个人时,最终留下来的下标为1
f(2,3) = 1;
// 当有3个人时,最终留下来的下标为1
f(3,3) = 1;
// 当有4个人时,最终留下来的下标为0
f(4,3) = 0;
// 当有5个人时,最终留下来的下标为3
f(5,3) = 3;
...
// 当有10个人时,最终留下来的下标为3
f(10,3) = 3;
// 当有11个人时,最终留下来的下标为6
f(11,3) = 6;

发现:

每杀掉一个人,下一个人成为头,相当于把数组向前移动M位。若已知N-1个人时,胜利者的下标位置位f(N−1,M),则N个人的时候,就是往后移动M为,(因为有可能数组越界,超过的部分会被接到头上,所以还要模,既f(N,M)=(f(N−1,M)+M) % N

理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人,其实就是把这个数组向前移动了M位。然后逆过来,就可以得到这个递推式。

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

标题:约瑟夫环
作者:zrlong
地址:http://blog.zrlong.top/articles/2022/04/28/1651108906471.html