最浅显易懂的约瑟夫环讲解,10行代码解决问题

世间上的相遇

都是久别重逢

约瑟夫问题

约瑟夫问题是个著名的问题: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开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

缺点:

要模拟整个游戏过程,时间复杂度高达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的人。

下图表示这一过程(先忽视绿色的一行)

现在再来看我们递推公式是怎么得到的!

将上面表格的每一行看成数组,这个公式描述的是:幸存者在这一轮的下标位置

  • f(1,3)f(1,3):只有1个人了,那个人就是获胜者,他的下标位置是0
  • f(2,3)=(f(1,3)+3)%2=3%2=1f(2,3)=(f(1,3)+3)%2=3%2=1:在有2个人的时候,胜利者的下标位置为1
  • f(3,3)=(f(2,3)+3)%3=4%3=1f(3,3)=(f(2,3)+3)%3=4%3=1:在有3个人的时候,胜利者的下标位置为1
  • f(4,3)=(f(3,3)+3)%4=4%4=0f(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)+3f(11,3)=f(10,3)+3。不过有可能数组会越界,所以最后模上当前人数的个数,f(11,3)=(f(10,3)+3)%11

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

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

因为求出的结果是数组中的下标,最终的编号还要加1

下面给出代码实现:

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

本文分享自微信公众号 - 秃头哥编程(xp_1311664842)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

牛逼哄哄的 Lambda 表达式,简洁优雅就是生产力!

https://www.zhihu.com/question/20125256/answer/324121308

9220
来自专栏开发杂记

oracle截取字符串去掉字段末尾指定长度的字符

lengthb(string)计算string所占的字节长度:返回字符串的长度,单位是字节

23310
来自专栏Java技术栈

难倒你了吧!ArrayList 为啥要实现 RandomAccess 接口?

在我们的开发中,List接口是最常见不过,而且我们几乎每天都在用ArrayList或者LinkedList,但是细心的同学有没有发现,ArrayList中实现了...

12710
来自专栏开发杂记

mysql常用语句备忘

3、导出数据库 mysqldump -u 用户名 -p 数据库名 > 导出的文件名

7810
来自专栏开发杂记

使用MyBatis Generator自动创建代码

最近开始接触MyBatis,都是手动创建的映射文件,后来才知道原来可以利用生成器自动生成实体类、DAO接口和Mapping映射文件,将生成的文件的拷贝到项目中,...

10720
来自专栏自然语言处理(NLP)论文速递

「自然语言处理(NLP)论文推送」第二弹(含源码)805

本次共有三篇Paper和大家分享,第一篇主要是序列对序列建模训练的问题,将复杂度由

10530
来自专栏开发杂记

Array类型

Array也是ECMAScript中常用类型之一,其特点是数组中的每一项都可以保存任何类型的数据,数组的大小可以动态调整。

11530
来自专栏暴走大数据

Spark Core源码精读计划11 | Spark广播机制的实现

在RPC的领域里摸爬滚打了很长时间,是时候抽身出来看一看其他东西了。顺着SparkEnv初始化的思路继续看,下一个主要组件是广播管理器BroadcastMana...

11820
来自专栏Java技术栈

Oh My God!e.printStackTrace() 导致系统卡崩

非堆!那么,左边是代码缓存区内存,右边红框就是字符串池,常量,基本类型数据的内存区。

18520
来自专栏SAMshare

【LeetCode20】回文数

1 )首先我们知道题目要求不可以将数字转换为 字符串 来解决,因此 [::-1] 的办法就不能用了

15920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励