当前位置:首页 >> 学科竞赛 >> 约瑟夫环问题

约瑟夫环问题


约瑟夫环问题
一、前言 约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Flavius Josephus)提出的。该问题的说法不 一,传说他参加并记录了公元 66—70 年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达 伯特城达 47 天之久,在城市沦陷之后,他和 40 名死硬的将士在附近的一个洞穴中避难。在那里,这些叛 乱者表决说“要投降毋宁死”。

于是,约瑟夫建议每隔两个人杀死一人,而这个顺序是由抽签决定的。约瑟 夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了另一个幸存者一起投降了罗 马。 假设现在一个房间内共有 n 个人。同上所述, “杀人狂” 只想留下一个人活命,并且他将按下面的规 则去杀人: ? 所有的人围成一圈; ? 顺时针报数,每次报到 q 的人将被杀掉; ? 被杀掉的人将从房间内移走; ? 然后从被杀掉的下一个人重新报数,直到剩余一人。 你非常不幸地参加了这场“游戏” ,当然,你是想活命的,所以你必须快速决定要站到哪一个位置, 才能使得最后留下的人是你。 这就是最初的“约瑟夫环”问题,纯粹的数学计算无法做出解答,但对于参加信息学竞赛的选手来说, 可以快速的编写一个程序来解决。下面就针对这个问题进行分析并解答。 二、特例 当 q=2 时,是约瑟夫环的一个特例,可以利用数学的方法快速求解。 分析: 如果只有 2 个人,显然剩余的为 1 号。如果有 4 个人,在第一轮移除掉 2、4 以后,只剩下 1、3,现 在环中又仅剩下 2 个人了,我们已经知道 2 个人时,结果为 1,所以当 n=4 时,最后剩余的也为 1 号。如 此可设想: 当 n ? 2 ?k ? 0? 时,最后剩余的必定为 1。
k

我们定义 J ?n ? 为由 n 个人的构建成的约瑟夫环最后的结果,则有 J 2 正确性:

? ? ? 1。让我们来证明该设想的
k

n ? 2 k ? 2 k ?1 ? 2 k ?1 (第一轮后,移除掉 2 k / 2 ? 2 k ?1 个人,剩余 2 k ?1 ,1 号仍在环中) n ? 2 k ?1 ? 2 k ?2 ? 2 k ?2 (第二轮后,1 号仍在环中)

??

n ? 2 2 ? 21 ? 21 (1 号仍在序列当中)

J ?2? ? 1
在上面的分析中,每一轮的移除操作,均移除一半出列,1 号总在剩余的环中。直至最后剩余 2 个人 时,再清除一半,就只剩下 1 号了,所以 J 2 k ? 1。 而对于 n ? 2 时,就不存在上面的设想了。我们分析一下部分数值的解构成的表格:
k

? ?
8 1

n J(n)

1 1

2 1

3 3

4 1

5 3

6 5

7 7

9 3

10 5

11 7

12 9

13 11

14 13

15 15

16 1

?? ??

可以看出 J ?n? ? J 2 k ? t ? 2t ? 1 k ? 0,0 ? t ? 2 k 。 这样,我们就可以在分解 n ? 2 ? t 后就可以得到结果了。举例来说:9(23+1)个人构建成的约瑟夫
k

?

?

?

?

环(如图一) ⑨ ⑧

① ②



⑦ ⑥ ⑤



图一:9 人构建成约瑟夫环 我们在移除一个人后,就成为剩余的 8 个人构建成的新的约瑟夫环(如图二所示) ,而我们已经知道

J ?8? ? J 23 ? 1,这里的 1 号是原约瑟夫环中的 3 号,所以 J ?9? ? 3 。
① ⑨ ⑧ ② ⑦ ③ ⑥ ⑧ ⑨

? ?



⑦ ⑥ ⑤



⑤ ④ ③



图二:9 人约瑟夫环,移除 1 人后转化为 8 人的约瑟夫环 在转变过程中,是将原约瑟夫环中的 2t 后的第一个人 2t+1 定义为新序列中的 1 号,而我们在 2t 个人 中移除掉 t 个人后, 原 n 个人的约瑟夫环就转变为了 2k 个人的环了。 从前面的分析, 我们已经知道 J 2

? ? ? 1,
k

这时,新约瑟环中的 1 是指原序列中的 2t+1,因此 J ?n? ? J 2 k ? t ? 2t ? 1 。 这里仅仅是当 q=2 时的特例,当 q ? 2 时呢? 三、延伸 当 q ? 2 时就无法应用上面的数学方法了。在进行接下来的分析之前先做以下约定: ? ? 定义 J q ?n? 为 n 个人构建成的约瑟夫环,每次移除第 q 个人的解; n 个人的编号从 0 开始编号至 n-1。

?

?

我们仍然采用与图二所示相似的分析, 探究 J q ?n ? 1? 与 J q ?n? 之间的关系。 因 J q ?n? 是在 J q ?n ? 1? 的 基础上移除一个人后得到的,如果我们能知道 J q ?n? ,就可以从 n 的解推导出 n+1 的解。

J q ?n ? 1? = ?J q ?n? ? q? | ?n ? 1?
解释: J q ?n? 是从原 n+1 个人构建的约瑟夫环的编号为 q(注:编号从 0 开始)作为起点的,因此我 们需要还原到 n+1 约瑟夫环中的编号 J q ?n? ? q ,又因编号加 q 后有可能大于等于 n+1,超出原有的编号, 所以对 n+1 做取模操作。 举例来说: n ? 9, q ? 4 0 8 7 1 2 3 4 5 6 7

6 5 4

3

2 1 0

8

图三、 n ? 9, q ? 4 构建的约瑟夫环,移除 1 人后成为 8 人的约瑟夫环 如果我们已知 J 4 ?8? ? 5 ,那么我们就可以推导出 J 4 ?9? ? ?J 4 ?8? ? 4? | 9 ? 0 。 利用此推导过程再次查看当 q=2 时的结果值: (注:n 个人的编号从 0??n-1)

J 2 ?1? ? 0 J 2 ?2? ? ?J 2 ?1? ? 2? | 2 ? 0 J 2 ?3? ? ?J 2 ?2? ? 2? | 3 ? 2 J 2 ?4? ? ?J 2 ?3? ? 2? | 4 ? 0

J 2 ?5? ? ?J 2 ?4? ? 2? | 5 ? 2 J 2 ?6? ? ?J 2 ?5? ? 2? | 6 ? 4 J 2 ?7? ? ?J 2 ?6? ? 2? | 7 ? 6 J 2 ?8? ? ?J 2 ?7? ? 2? | 8 ? 0
??

J 2 ?n? ? ?J 2 ?n ? 1? ? 2? | n
上面的推导过程中与我们进行的特例分析相比较,可以看出结果是一致的。 由此我们可以编写时间复杂度为 O?n ? 的约瑟夫环求解函数。 int solve(int n, int q){ //求解 n 个人构建成的约瑟夫环,每次移除掉第 q 个人 int jn=0; //初始化 J q ?1? ? 0 for(int i=2; i<=n; i++) jn=(jn+q)%i; // J q ?n? ? J q ?n ? 1? ? q %n return jn; } 四、优化 上面的求解过程是在求解出 n-1 个人的解的基础上推导出 n 个人的约瑟夫环解。而当 n 为一个极大值 时,有没有更优的方法来解决呢?我们来做如下分析: 对于 n 个人构建的约瑟夫环,每移除完一圈(我们称为一轮) ,将移除掉 ?n / q? (n 整除 q)个人,组 成的新约瑟夫环剩有 n ? ?n / q? 个人。如果我们已知道 J q ?n ? ?n / q??,是否也能非常容易的推导出 J q ?n? 呢?我们仍然来看当 n ? 9, q ? 4 时的例子: 0 8 7 1 2 3 0 1 2 3

?

?

6 5 4

3

6 5 4

8

图四、 n ? 9, q ? 4 构建的约瑟夫环,移除一轮后构建新约瑟夫环

我们在一轮中移除掉 ?9 / 4? ? 2 人,构建成的新约瑟夫环中剩有 9-2=7 人,并且重新编号,如图四中 的右图所示。假设我们已知 J 4 ?7 ? ? 1 , 那么我们就可以推导出 J 4 ?9? ? 0 。 这里的问题主要是如何将新约瑟夫环中编号还原到原约瑟环中的编号。新约瑟夫环中的编号是在原环 中移除掉 ?n / q? 个得到,所以原环中的编号对应于新环中的编号可利用下面的式子计算出来:

J q ?n ? ?n / q ?? ? ?n / q ? ? q ? ? ?J q ?n ? ?n / q ?? ? n | q ? J q ?n ? ? ? ? J q ?n ? ?n / q ?? ? n | q ? ??J q ?n ? ?n / q ?? ? n | q ?/ ?q ? 1??? ?J q ?n ? ?n / q ?? ? n | q ?
解释: 假定 J q ?n ? ?n / q?? ? x ,如果新编号 x ? ?q ? ?n / q??n ? 1? 即 x ? n | q ,也就是说最后剩余的人是 在最后一部分中,新环中的编号是从最后一个被移除掉的后一个 q ? ?n / q? 开始的,所以原环中的对应编 号为 x ? q ? ?n / q? ;否则,我们需要计算出在 x 之前已除去多少人,新的编号 x 是在每 q 个人里移除一个 后得到,即除去的人数为 ,因此原编号为 ??x ? n | q? /?q ? 1?? ( x ? n | q 是 指 还 原 起 始 编 号 位 置 )

x ? n | q ? ??x ? n | q? /?q ? 1?? 。
至此,我们可以编写约瑟夫环的求解函数如下: int josephus(int n, int q){ if (n<=q) solve(n, q); //如果 n ? q 我们调用 O?n ? 的算法求解 int jn=josephus(n-n/q, q); //递归求解 jn-=n%q; //还原起始编号位置 if (jn<0) return jn+n; else return jn +jn/(q-1); } 五、时间复杂度分析 约瑟夫环问题是信息学奥赛选手在学习循环链表时练习的问题之一,利用循环链表模拟移除操作来解 决的时间复杂度显而易见的是 O?nq? 。 利用已知的 J q ?n ? 1? 推导出 J q ?n? 的解决函数 solve(n, q)时间复杂度为 O?n ? 。

当 n 远大于 q 时,josephus(n, q)的时间复杂度为 O? ? q ? log

? ?

q/n ? ?。 ?q ? 1? / q ? ?

六、总结: 在本文中只有特例(q=2)是借助于数学方法,另外两种算法都是基于动态规划的思想来解决,是在 我们得知子问题的求解之后,向更大的问题进行转化、推导,从而使问题得以圆满解答。


更多相关文档:

约瑟夫环问题

约瑟夫环问题_学科竞赛_高中教育_教育专区。约瑟夫环问题一、前言 约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Flavius Josephus)提出的。该问题的说法不 一,...

约瑟夫环问题解决答案

如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 约瑟夫环问题解决答案 隐藏>> 约瑟夫环 a) 问题描述:Joseph 问题的一种...

用顺序表解决约瑟夫环问题

用顺序表解决约瑟夫环问题_工学_高等教育_教育专区。用顺序表解决约瑟夫环问题计算机科学与工程学院《算法与数据结构》试验报告[一] 算法与数据结构》试验报告[ 专业...

c语言实现约瑟夫环问题

运行、测试与分析 (二)采用顺序存储结构如何实现约瑟夫环问题代码和解释 #include <stdlib.h> #include<stdio.h> #include<malloc.h> #define MaxSize 50 ...

C语言 约瑟夫环问题

实验一: 实验一:约瑟夫环问题 一.实验目的: 实验目的:要求设计一个程序模拟约瑟夫环问题过程,求出出列编号序列。 要求设计一个程序模拟约瑟夫环问题过程,求出出列...

约瑟夫环问题

约瑟夫环问题_计算机软件及应用_IT/计算机_专业资料。计算机科学与工程学院《算法与数据结构》实验报告(一) 专业班级 学生学号 学生姓名 实验项目 实验类别 13 级计...

约瑟夫环问题实验报告

约瑟夫环问题实验报告_计算机软件及应用_IT/计算机_专业资料。利用C++编写约瑟夫环问题 天津理工大学实验报告学院(系)名称:计算机与通信工程学院 姓名 班级 黄雅娇 四...

约瑟夫环问题_实验报告

约瑟夫环问题 实验报告 年级 12 级 学号 12061633 姓名 一、实验目的 徐超杰 本实验的目的是进一步理解线性表的逻辑结构和存储结构, 进一步提高使用理 论知识指导...

题目:约瑟夫环问题

数据结构上机实验报告 02090401 12 题目:约瑟夫环问题 一.问题描述 设有 n 个人围做一圈,现从某个人开始报数,数到 m 的人出列,接着从出列的 下一个人开始...

数据结构 约瑟夫环问题

数据结构 约瑟夫环问题_数学_自然科学_专业资料。数据结构实验报告-约瑟夫环 哈工程大学heu实验名称:约瑟夫环问题 实验类型:综合性问题 班级: 学号: 姓名: 实验日期...
更多相关标签:
约瑟夫环 | 约瑟夫问题 | 约瑟夫环 c语言 | 约瑟夫 | 约瑟夫环问题 java | 约瑟夫环问题c++ | 约瑟夫环 数据结构 | 约瑟夫环 java |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com