最浅显易懂的约瑟夫环讲解 太过爱你忘了你带给我的痛 2024-04-17 05:49 16阅读 0赞 ### 约瑟夫问题 ### 约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。 例如只有三个人,把他们叫做A、B、C,他们围成一圈,从A开始报数,假设报2的人被杀掉。 * 首先A开始报数,他报1。侥幸逃过一劫。 * 然后轮到B报数,他报2。非常惨,他被杀了 * C接着从1开始报数 * 接着轮到A报数,他报2。也被杀死了。 * 最终胜利者是C ### 解决方案 ### #### 普通解法 #### 刚学数据结构的时候,我们可能用链表的方法去模拟这个过程,N个人看作是N个链表节点,节点1指向节点2,节点2指向节点3,……,节点N-1指向节点N,节点N指向节点1,这样就形成了一个环。然后从节点1开始1、2、3……往下报数,每报到M,就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70] ##### 缺点: ##### 要模拟整个游戏过程,时间复杂度高达O(nm),当n,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。 #### 公式法 #### 约瑟夫环是一个经典的数学问题,我们不难发现这样的依次报数,似乎有规律可循。为了方便导出递推式,我们重新定义一下题目。 **问题**: N个人编号为1,2,……,N,依次报数,每报到M时,杀掉那个人,求最后胜利者的编号。 这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。 **递推公式**: **f(N,M)=(f(N−1,M)+M)%N** * f(N,M) 表示,N个人报数,每报到M时杀掉那个人,最终胜利者的编号 * f(N−1,M)表示,N-1个人报数,每报到M时杀掉那个人,最终胜利者的编号 下面我们不用字母表示每一个人,而用数字。 1、2、3、4、5、6、7、8、9、10、11 表示11个人,他们先排成一排,假设每报到3的人被杀掉。 * 刚开始时,头一个人编号是1,从他开始报数,第一轮被杀掉的是编号3的人。 * 编号4的人从1开始重新报数,这时候我们可以认为编号4这个人是队伍的头。第二轮被杀掉的是编号6的人。 * 编号7的人开始重新报数,这时候我们可以认为编号7这个人是队伍的头。第三轮被杀掉的是编号9的人。 * …… * 第九轮时,编号2的人开始重新报数,这时候我们可以认为编号2这个人是队伍的头。这轮被杀掉的是编号8的人。 * 下一个人还是编号为2的人,他从1开始报数,不幸的是他在这轮被杀掉了。 * 最后的胜利者是编号为7的人。 下图表示这一过程(先忽视绿色的一行) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70 1] 现在再来看我们递推公式是怎么得到的! **将上面表格的每一行看成数组,这个公式描述的是:幸存者在这一轮的下标位置** * f(1,3)f(1,3):只有1个人了,那个人就是获胜者,他的下标位置是0 * f(2,3)=(f(1,3)+3)%2=3%2=1:在有2个人的时候,胜利者的下标位置为1 * f(3,3)=(f(2,3)+3)%3=4%3=1:在有3个人的时候,胜利者的下标位置为1 * f(4,3)=(f(3,3)+3)%4=4%4=0:在有4个人的时候,胜利者的下标位置为0 * …… * f(11,3)=6 很神奇吧!现在你还怀疑这个公式的正确性吗?上面这个例子验证了这个递推公式的确可以计算出胜利者的下标,下面将讲解怎么推导这个公式。 **问题1**:假设我们已经知道11个人时,胜利者的下标位置为6。那下一轮10个人时,胜利者的下标位置为多少? **答**:其实吧,第一轮删掉编号为3的人后,之后的人都往前面移动了3位,胜利这也往前移动了3位,所以他的下标位置由6变成3。 **问题2**:假设我们已经知道10个人时,胜利者的下标位置为3。那下一轮11个人时,胜利者的下标位置为多少? **答**:这可以看错是上一个问题的逆过程,大家都往后移动3位,所以f(11,3)=f(10,3)+3。不过有可能数组会越界,所以最后模上当前人数的个数,f(11,3)=(f(10,3)+3)%11 **问题3**:现在改为人数改为N,报到M时,把那个人杀掉,那么数组是怎么移动的? **答**:每杀掉一个人,下一个人成为头,相当于把数组向前移动M位。若已知N-1个人时,胜利者的下标位置位f(N−1,M),则N个人的时候,就是往后移动M为,(因为有可能数组越界,超过的部分会被接到头上,所以还要模N),既f(N,M)=(f(N−1,M)+M)%n 注:理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人,其实就是把这个数组向前移动了M位。然后逆过来,就可以得到这个递推式。 因为求出的结果是数组中的下标,最终的编号还要加1 下面给出代码实现: int cir(int n,int m) { // 一个人报数,报到m的被杀,最后的胜利者是0 int p = 0; // i个人报数,报到m的被杀,求最后的胜利者 for (int i = 2; i <= n; i++) { p = (p + m) % i; } return p + 1; } #### 关注公众号【秃头哥编程】,获取编程大礼包 #### [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/a17bebf348fa486db19c78b17ec83c67.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9fd47a2a1a754218ad13fcebe16ac1c2.png
相关 最浅显易懂的约瑟夫环讲解 约瑟夫问题 约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。 例如只... 太过爱你忘了你带给我的痛/ 2024年04月17日 05:49/ 0 赞/ 17 阅读
相关 约瑟夫环 约瑟夫环 1、参考资料 https://blog.csdn.net/shuaicihai/article/details/54847433 2、使用数组 痛定思痛。/ 2022年11月27日 06:54/ 0 赞/ 151 阅读
相关 约瑟夫环 package com.someusefuldesign.demo; import java.util.ArrayList; /约瑟 桃扇骨/ 2022年08月13日 15:54/ 0 赞/ 144 阅读
相关 约瑟夫环 \include<stdio.h> \include<stdlib.h> /\ 约瑟夫环是一个数学的应用问题: 已知n个人(以编号1,2,3...n分别表示)围 ╰半夏微凉°/ 2022年08月07日 01:53/ 0 赞/ 166 阅读
相关 约瑟夫环 约瑟夫环 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个 怼烎@/ 2022年07月15日 13:39/ 0 赞/ 163 阅读
相关 约瑟夫环 N个人坐成一个圆环(编号为1 - N),从第1个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。 例如:N = 3,K = 2。2号先出列,然后是 桃扇骨/ 2022年06月11日 06:26/ 0 赞/ 162 阅读
相关 约瑟夫环 【问题描述】 编号为 1,2,...,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。现在给定一个随 机数 m>0,从编号为 1 的人开始,按顺时针方向 1 今天药忘吃喽~/ 2022年04月22日 06:06/ 0 赞/ 204 阅读
相关 约瑟夫环 > 约瑟夫环运作如下: > 1、一群人围在一起坐成 \[2\] 环状(如:N) > 2、从某个编号开始报数(如:K) > 3、数到某个数(如:M)的时候,此人出列, 阳光穿透心脏的1/2处/ 2022年03月22日 16:38/ 0 赞/ 259 阅读
相关 约瑟夫环 编号为1,2,…,n的n个人按顺时针方向围坐在一张圆桌周围,每人持有一个密码(正整数)。一 开始任选一个正整数m作为报数上限值,从第一个人开始按顺时针方向自1开始报数,报到m时 r囧r小猫/ 2021年12月20日 04:29/ 0 赞/ 283 阅读
相关 约瑟夫环 int cir(int n,int m) { int p=0; for(int i=2;i<=n;i++) { 我会带着你远行/ 2021年12月16日 15:13/ 0 赞/ 290 阅读
还没有评论,来说两句吧...