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

Radinka ·
更新时间:2024-09-20
· 979 次阅读

前言

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

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

目录 简介 基础题意 思路简介 算法讲解 首先搞清 10 个猴去掉 1 个怎么变成 9 只猴 其次搞清每一轮的结果之间的关系 代码展示 变 k 讲解 推荐题目 鸣谢文章 简介 基础题意 猴子选大王:有 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 using namespace std; int JO(int n, int k) { int r = 0; for (int i = 2; i > 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 using namespace std; int JO(int n, int k) { int r = 0; for (int i = 2; i > 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; } 推荐题目

国王游戏

鸣谢文章

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

请多多支持猹的个人博客 H_On 个人小站
因为猹的小站真的还挺可的,所以那边更新的也比较勤奋,感谢关注~我会努力的(ง •_•)ง


作者:H_On



约瑟夫环问题 约瑟夫环 ON

需要 登录 后方可回复, 如果你还没有账号请 注册新账号