Josephus Problem的详细算法及其Python,Java语言的实现

  笔者昨天看电视,偶尔看到一集讲述古罗马人与犹太人的战争——马萨达战争,深为震撼,有兴趣的同学可以移步:http://finance.ifeng.com/a/20170627/15491157_0.shtml .

  这不仅让笔者想起以前在学数据结构时碰到的Josephus问题:

  据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人找到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

  以前我们都是用链表的方法编程来解决这个问题的,这次笔者将会讲述两个不同的方法,一个是笔者自己的朴素想法,一个是数学方法。

朴素方法

数学方法

  首先我们先将Josephus问题描述出来,即: 共有N个人围成一圈,编号分别为1,2,…,N,从第一个人开始从1到m报数,报到m的人退出,如此循环下去,直至最后一个人。问最后一个人的最开始的编号是几?

  先是笔者的朴素想法。

  将N个人储存在列表(list)中,每次报到m的元素剔除,并记录下最后一个人报的数i,然后将缩短后的数组从i+1报数,如此循环下去,直至列表的长度为1,这样剩下来的元素就是我们要求的答案。

  这种想法虽然素朴,比较容易实现,但是时间复杂度为O(Nm).

  接着是数学方法。

  假设一开始的Josephus环编号为0,1,2,…,N-1.我们知道第一个人(编号一定是m%N-1) 出列之后,剩下的N-1个人组成了一个新的Josephus环(以编号为k=m%n的人开始):

并且从k开始报0.

  现在我们把他们的编号做一下转换:

k,k+1,k+2,……,n−2,n−1,,1,2,…k−2

k−>,

k+1−>1,

k+2−>2,

…,

k−2−>n−2,

k−1−>n−1

变换后就成为了(N-1)个人报数的子问题,这启示我们可以用归纳法来解决这个问题。假如我们知道这个子问题的解为

x

,原来问题的答案为

x

,则

x=(x+k)%n.

因此,递推公式就有了!令

f(i)

表示

i

个人玩游戏报

m

退出最后胜利者的编号,我们要求的结果是

f(N)

,其递推公式如下:

  数学方法简单明了,计算效率高,但是推导比较困难。

  最后,我们给出以下两种方法的Python代码和朴素方法的Java代码,希望能给大家一点思考。

  完整的Python代码如下:

f(1)=,f(i)=(f(i−1)+m)%i(i>1).

  完整的Java代码如下:

  本次分享到此结束,欢迎大家交流~~

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180605G0DKDT00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券