项目三 解决约瑟夫环问题PPT课件

约瑟夫环问题python解法约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。

思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。

代码如下：class Node():def __init__(self,value,next=None):self.value=valueself.next=nextdef createLink(n):return Falseif n==1:return Node(1)root=Node(1)tmp=rootfor i in range(2,n+1):tmp.next=Node(i)tmp=tmp.nexttmp.next=rootreturn rootdef showLink(root):tmp=rootwhile True:print(tmp.value)tmp=tmp.nextif tmp==None or tmp==root: def josephus(n,k):if k==1:print('survive:',n)root=createLink(n)tmp=rootwhile True:for i in range(k-2):tmp=tmp.nextprint('kill:',tmp.next.value) tmp.next=tmp.next.nexttmp=tmp.nextif tmp.next==tmp:print('survive:',tmp.value)if __name__=='__main__':print('-----------------')josephus(10,2)print('-----------------')josephus(10,1)print('-----------------')输出结果如下：-------------------------------------分界线-----------------------------------------感谢大家建议，第一种方法是直观暴力裸搞，确实不太简洁，下面写出我的第二种方法，求模来搞起，代码少了一些，如下：def josephus(n,k):if k==1:print('survive:',n)people=list(range(1,n+1))while True:if len(people)==1:p=(p+(k-1))%len(people)print('kill:',people[p])del people[p]print('survive:',people[0])if __name__=='__main__':josephus(10,2)josephus(10,1)运行结果和上面一样。

1．需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；输入的值为数字(2) 输出的形式；输出的形式为一串数字如：6，1，4，7，2，3，5(3) 程序所能达到的功能；编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

输入错误时一般不会显示结果。

总体归纳为：1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。

3.程序执行的命令包括：1）输入初始密码和人数 2）输入所有人的密码 3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号 5）结束4.测试数据(1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4(2)m=7,n=20,20个人的密码依次为3，1，7，2，4，8，4(2)组数据为错误数据测程序的健壮性。

2．概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

ADT LinearList{数据元素：D={ai| ai∈D0, i=1,2,…，n n≥0 ，D0为某一数据对象}关系：Ｓ＝｛<ai,ai+1> | ai, ai+1∈D0，i=1,2, …,n-1｝该程序只有主程序。

ACM新生培训讲座
约瑟夫环问题
主讲人：nuanran
Flavius Josephus
弗拉维奥·约瑟夫(37-100)是第一世纪时的 著名的犹太历史学家，也是军官及辩论家。 《犹太古史》(The Antiquities of the Jews)：记录了由圣经创世记至公元66年的 犹太人历史，以旧约圣经为蓝图以及古人的 传说，编写而成的犹太巨著。由于当时的犹 太人散居各地，此书成为各地土生犹太人重 要学习典籍，亦为当代神学学者及历史学者 所采用。
约瑟夫环问题三
不要妄想再找到公式了，模拟是唯一的选择， 但是直接模拟的话，该算法的复杂度将达到 O(n^2). 事实上，我们可以用线段数对此做一个优化， 用线段数来统计每个区间上还剩下人的个数， 从而使算法的复杂度降低到O(n*logn)。 线段数？？一棵平衡二叉树，它的每个节点 都是一个线段，这里就不做详细介绍了。
约瑟夫环问题三
问题描述：编号从1到n的n个人，站成一个环，每个 人手里拿着一个卡片，卡片上写着一个非零的数，首 先去掉编号为k的人，然后看他手里的卡片上的数字 m[k]，如果m[k]>0，则去掉他左手边的第m[k]个人， 如果m[k]<0，则去掉他右手边的第m[k]个人。重复上 述步骤，直至只剩下一个人，问这个人的编号是多少。
约瑟夫环问题二
为了方便，在这里我们把这n个人的编号改为从0到n-1， 第一个去掉的人总是m%n-1，剩下n-1个人，这n-1个人 又组成了一个从第m%n个人开始的新的约瑟夫环问题。 m%n 0 m%n+1 1 … … n-1 n-m%n-1 0 n-m%n … … m%n-2 n-2
J(1,m)=0; J(n,m)=(m%n+J(n-1,m))%n, n>=2. 最后的结果加1就OK了。 这个问题可以用O(n)的算法去解决。

• • • • • • • • • • •
s:=0; while s<n do begin if j<m then inc(j) else j:=1; s:=s+a[j]; end; write(j); a[j]:=0; end; end.

约瑟夫问题多 种解决方法
约瑟夫问题的来历
• 据说著名犹太历史学家 Josephus有过以下的故事：在罗 马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋 友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓 到，于是决定了一个自杀方式，41个人排成一个圆圈，由 第1个人开始报数，每报数到第3人该人就必须自杀，然后 再由下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从，Josephus要他的朋友 先假装遵从，他将朋友与自己安排在第16个与第31个位置， 于是逃过了这场死亡游戏。17世纪的法国数学家加斯帕在 《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余 的人才能幸免于难，于是想了一个办法：30个人围成一圆 圈，从第一个人开始依次报数，每数到第九个人就将他扔 入大海，如此循环进行直到仅余15个人为止。问怎样排法， 才能使每次投入大海的都是非教徒。
著名约瑟夫问题一
• 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了 这样一个故事：15个教徒和15 个非教徒在深海上遇险， 必须将一半的人投入海中，其余的人才能幸免于难，于是 想了一个办法：30个人围成一圆圈，从第一个人开始依次 报数，每数到第九个人就将他扔入大海，如此循环进行直 到仅余15个人为止。问怎样排法，才能使每次投入大海的 都是非教徒。题目中30个人围成一圈，因而启发我们用一 个循环的链来表示。可以使用结构数组来构成一个循环链。 结构中有两个成员，其一为指向下一个人的指针，以构成 环形的链；其二为该人是否被扔下海的标记，为1表示还 在船上。从第一个人开始对还未扔下海的人进行计数，每 数到9时，将结构中的标记改为0，表示该人已被扔下海了。 这样循环计数直到有15个人被扔下海为止