资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Flavius Josephus,弗拉维奥,约瑟夫,(37-100),是第一世纪时的著名的犹太历史学家，也是军官及辩论家。,犹太古史,(The Antiquities of the Jews),：记录了由圣经创世记至公元,66,年的犹太人历史，以旧约圣经为蓝图以及古人的传说，编写而成的犹太巨著。由于当时的犹太人散居各地，此书成为各地土生犹太人重要学习典籍，亦为当代神学学者及历史学者所采用。,Flavius Josephus弗拉维奥约瑟夫(37-10,Flavius Josephus,犹太战记,(War of the Jews),约瑟夫自传,(The Life of Flavius Josephus),Flavius Josephus犹太战记(War of,约瑟夫环问题,在犹太人和罗马的战争期间，约瑟夫和其他,40,个犹太反叛者被罗马军队困在一个山洞中，这些犹太反叛者宁愿自杀也不想被罗马军队抓住，于是他们就站成一个环，从其中某个人开始数，每数到的第三个人就要被杀掉，直到所有人都死光了。但是约瑟夫和他的一个朋友觉得自杀是没有意义的，他们并不想死，于是他很快就算出了他和他的朋友应该站在什么位置，使他们两个成为最后被杀的那两个人，并最终活了下来。,约瑟夫环问题在犹太人和罗马的战争期间，约瑟,约瑟夫环问题一,问题描述：编号从,1,到,n,的,n,个人站成一个环，从第一个人开始，每数到,2,的时候，去除该位置上的人，直到只剩下一个人，求剩下的这个人的编号。,我们用,J(n),表示人数为,n,的时候的解。,约瑟夫环问题一问题描述：编号从1到n的n个人站成,约瑟夫环问题一,去掉的人的编号依次为,2,4,6,8,10,3,7,1,9,最后只剩下,5,，所以,J(10)=5,。,约瑟夫环问题一,约瑟夫环问题一,约瑟夫环问题一,约瑟夫环问题一,当有偶数个人的时候，我们假设为,2n,个人，经过第一圈之后还剩下,n,个人。,约瑟夫环问题一当有偶数个人的时候，我们假设为2n,约瑟夫环问题一,剩下的,n,个人又是一个新的约瑟夫环问题。,1 2 3 4 n-1 n,1 3 5 7 2n-3 2n-1,J(2n)=2*J(n)-1.,约瑟夫环问题一剩下的n个人又是一个新的约,约瑟夫环问题一,当有奇数个人的时候，我们假设为,2n+1,个人，经过第一圈之后还剩下,n+1,个人。去掉,2n,之后，下一个要去掉的就是,1,，最后还是剩下,n,个人。,约瑟夫环问题一当有奇数个人的时候，我,约瑟夫环问题一,剩下的,n,个人还是一个新的约瑟夫环问题。,1 2 3 4 n-1 n,3 5 7 9 2n-1 2n+1,J(2n+1)=2*J(n)-1,约瑟夫环问题一剩下的n个人还是一个新的约瑟,约瑟夫环问题一,综上，我们可以得到如下递推公式：,该问题可以在,O(n),的复杂度解决。,约瑟夫环问题一综上，我们可以得到如下递推公式：,约瑟夫环问题一,约瑟夫环问题一,约瑟夫环问题一,由上图可以看出如果,n,为,2,的幂次方的时候，,J(n)=1,，这是显然的。而在此之后,J(n),以,2,递增，因此我们可以猜测,:,而事实上,J(n),确实满足上述规律，这个可以通过归纳法得到证明，至此，约瑟夫环问题一可以用,O(lg(n),的算法很好地解决。,约瑟夫环问题一由上图可以看出如果n为2的幂次方,约瑟夫环问题二,问题描述：编号从,1,到,n,的,n,个人站成一个环，从第一个人开始，每数到,m,的时候，去除该位置上的人，直到只剩下一个人，求剩下的这个人的编号。,我们用,J(n,m),表示人数为,n,，每次都去掉第,m,个人的时候的解。,约瑟夫环问题二问题描述：编号从1到n的n个人,约瑟夫环问题二,为了方便，在这里我们把这,n,个人的编号改为从,0,到,n-1,，第一个去掉的人总是,m%n-1,，剩下,n-1,个人，这,n-1,个人又组成了一个从第,m%n,个人开始的新的约瑟夫环问题。,m%n m%n+1 n-1 0 m%n-2,0 1 n-m%n-1 n-m%n n-2,J(1,m)=0;,J(n,m)=(m%n+J(n-1,m)%n,n=2.,最后的结果加,1,就,OK,了。,这个问题可以用,O(n),的算法去解决。,约瑟夫环问题二为了方便，在这里我们把这n个人,约瑟夫环问题三,问题描述：编号从,1,到,n,的,n,个人，站成一个环，每个人手里拿着一个卡片，卡片上写着一个非零的数，首先去掉编号为,k,的人，然后看他手里的卡片上的数字,mk,，如果,mk0,，则去掉他左手边的第,mk,个人，如果,mk0,，则去掉他右手边的第,mk,个人。重复上述步骤，直至只剩下一个人，问这个人的编号是多少。,约瑟夫环问题三问题描述：编号从1到n的n个人，,约瑟夫环问题三,不要妄想再找到公式了，模拟是唯一的选择，但是直接模拟的话，该算法的复杂度将达到,O(n2).,事实上，我们可以用线段数对此做一个优化，用线段数来统计每个区间上还剩下人的个数，从而使算法的复杂度降低到,O(n*logn),。,线段数？一棵平衡二叉树，它的每个节点都是一个线段，这里就不做详细介绍了。,约瑟夫环问题三不要妄想再找到公式了，模拟是唯一,
展开阅读全文