H_On个人小站

个人站

这都被你发现了【惊
奖励你一朵小红花~


H_On简结 - 思路超清晰的解释约瑟夫环问题

前言

在一年半前还是个新生,第一次接触专业的编程教育的我刷题刷的很起劲,经典的猴子选大王问题就是在那时候遇到的,那时候我花了好久,用数组加判断实现了模拟选人,最终做出来了这道题。
如今已经熟练了掌握各种容器,对编程的理解也不可同日而语,但模拟已经不能满足如今的需要了。

好久以前老师曾助教新生时发现一个孩子用了 “公式推导法” 却说不出个所以然,于是让我们来解释,当时我绞尽脑汁没有想明白,最后有几个慧根灵光的同学说了说,感觉没懂,于是不再深究。
直到前几天做题又遇到了这个题,模拟时间超限,公式法又不会,于是等到比赛结束,开始用心的研究【约瑟夫环】了。

目录

简介

基础题意

  • 猴子选大王:有 n 只猴子围成一圈,每只猴子用 1-n 编号,从 1 开始数,数到 3 的猴子出列。从下一个猴子开始继续从 1 开始报数,同样报到 3 的猴子出列。直到最后出列的猴子就是大王,求大王的编号是多少。
  • 杀人:有 2n 个人,n 个好人 n 个坏人,他们围成一圈,分别在编号 1-n 的位置上。从 1 开始报数,谁喊到 k 的就会被杀,直到剩下 n 个人。问你如何安排好人的位置才能让游戏杀掉的全是坏人。
  • 大乱斗:有 n 个人围一圈,编号 1-n1 号作为开头,每一轮都从 1 开始报数。第一轮杀掉喊 1 的人,第二轮杀掉喊 2 的人 . . .第 n - 1 轮杀掉喊 n - 1 的人。直到剩 1 个人,问你最后剩下那个人编号是多少。

像以上这些都是可以用约瑟夫环来解决的例题,这里我只列了三个我想得起来的。
第一个是基础,第二个是应用,第三个是推广。

思路简介

这一类的题模拟的方法就不说了,基本上往后做 ACM 用模拟肯定 TLE 。
思路就是:【例如 10 只猴子里选大王

  • 10 只猴子里去掉 1 只,问题可以变成从 9 只猴子里选大王
  • 9 只猴子里去掉 1 只,问题可以变成从 8 只猴子里选大王
  • 8 只猴子里去掉 1 只,问题可以变成从 7 只猴子里选大王
  • . . .
  • 最后剩下 1 只猴子,就是大王

具体怎么转换,接下来我们详细讲解一下转换方式

算法讲解

首先搞清 10 个猴去掉 1 个怎么变成 9 只猴

我们先假设猴子有两个属性:编号位置 ,简单的栗子,一开始编号和位置是对应的

  • 第一轮是 0,1,2 报数,2 会报 “3” 因此 2 号出列
  • 之后从 3 号开始报数,我们可以理解为 0,1 报数完成以后跑到了队尾。那么此时 3 号猴从 3 的位置跑到了 0 的位置,其他猴都往前走
  • 新的队列生成后,依然从 0 开始报数,位置 0 和位置 1 的猴去后面,依然是 2 号位置的猴报到 “3” ,出队以后 3 号位置的猴站到 0 号位置,其他的猴往前补
  • 猴的位置可能一直在变,但是它们各自的编号是永远不变的,因此最后剩一只猴,我们就可以得到这个猴的编号,得到结果
第一轮选出 2 : 0 1 2 3 4 5 6 7 8 9
第二次选出 5 : 7 8   0 1 2 3 4 5 6
第三次选出 8 : 4 5   6 7   0 1 2 3
第四次选出 1 : 1 2   3 4   5 6   0
第五次选出 6 : 5     0 1   2 3   4
第六次选出 0 : 2     3 4     0   1
第七次选出 7 :       0 1     2   3
第八次选出 4 :       1 2         0
第九次选出 9 :       1           0
最终结果是 3 :       0

可以看到每次都选 3 选 3 的,虽然出队的猴的编号不一样,但是对于 新队列 除去的一定是站在 2 号位置的猴。
这就是我们说的:10 个猴去掉一个,题目就变成从 9 个猴里选结果【有点递归的意思

要注意一点,实际上程序里的编号并不是 1 ~ n 而是 0 ~ n-1 。因为我们在往后推移的时候有可能会超出人数,因此要对人数取余,而 n 的余数是 0 ~ n-1 因此如果用 1 ~ n 来推算会出错,结果需要 +1,之后看代码的时候还会再次说明此事

其次搞清每一轮的结果之间的关系

k 是一个数,每当报数报到 k 就把这个人踢出去,这里先声明一下 k ,现在先以 3 为例。 观察上面的栗子,最开始的序列是

序列 a: 0 1 2 3 4 5 6 7 8 9

之后 2 号踢出去之后,因为接下来假装还是从 0 开始报数,所以 3 号变 0 号

序列 b: 7 8   0 1 2 3 4 5 6

我们会发现,序列 b 中的任何一 个号 i 都满足一个式子 (bi + 3) % a的长度 = a中对应的数
几个栗子:

(7 + 3) % 10 = 0
(0 + 3) % 10 = 3
(4 + 3) % 10 = 7

同理:

第二次选出 5 : 7 8   0 1 2 3 4 5 6
第三次选出 8 : 4 5   6 7   0 1 2 3
(7 + 3) % 9 = 1
(5 + 3) & 9 = 8
第八次选出 4 :       1 2         0
第九次选出 9 :       1           0
(0 + 3) % 3 = 0
(1 + 3) % 3 = 1

我相信到此为止,大家都了然了,既然公式有了,那还说啥?循环就完事了

代码展示

这里还要再说一句,因为这个思路从上到下的标号一直在变,公式也是 从下往上 推算的,因此循环的时候也是从 求 2 个数的结果求 n 个数的结果 。你问 n = 1 的时候怎么办?结果不是已经出来了吗 = =
r 的初始值是 0 ,因为求 1 个猴的话结果直接就是第一个 - 0 。每次循环求的都是 答案对应在上一层的编号 推算到最后就得到最后的编号了。如果编号是 1 ~ n 的话返回的结果就要 +1

#include <iostream>
using namespace std;

int JO(int n, int k) {
        int r = 0;
        for (int i = 2; i <= n; i += 1) r = (r + k) % i;
        return r;
}

int main() {
        ios::sync_with_stdio(0); cin.tie(0);
        int n, k; cin >> n >> k;
        cout << JO(n, k) + 1 << endl;
        return 0;
}

其实我对递归的写法还是挺喜欢的:JO 级函数

  • 到最后一层就返回 0
  • 不到最后一层那就是用下一层的答案 JOJO(n - 1, k) 加上 k 再对这一层的人数取余,得到这一层的结果
int JOJO(int n, int k) {
        if (n == 1) return 0;
        return (JOJO(n - 1, k) + k) % n;
}

变 k 讲解

我们知道,k 是一个关键数,每当报数报到 k 的时候就处理,那么这个关键数如果改变了怎么办呢。只要我们搞清楚每一轮 对应的 关键数是多少就好。
上面说过的第三个栗子:第一轮杀 报 1 的,第二轮杀 报 2 的 . . .这时候我们只需要让 k 的值变起来就好了
注意:n 个人的时候,k 是 1 ,n 越来越少的时候 k 越来越大,所以这个每一轮对应的 k 值一定要想清楚

#include <iostream>
using namespace std;

int JO(int n, int k) {
        int r = 0;
        for (int i = 2; i <= n; i += 1, k -= 1) r = (r + k) % i;
        return r;
}


int main() {
        ios::sync_with_stdio(0); cin.tie(0);
        int n; cin >> n;
        cout << JO(n, n - 1) + 1 << endl;
        return 0;
}

同样给出递归的方式,各位可以尝试自己理解一下

int JOJO(int n, int k) {
        if (n == 1) return 0;
        return (JOJO(n - 1, k + 1) + k) % n;
}

推荐题目

国王游戏

鸣谢文章

我看了好多将约瑟夫环的文章,大都讲的不明不白,有的甚至直接给个代码。直到看了这篇文章,里面有把各阶段列出来,让我茅塞顿开。就像我学线段树那会,有时候对不好理解的代码,把每一步改变都列出来对理解和解释原理都有很大的帮助。请看 —–> 秒懂约瑟夫环