文档介绍：该【ACM新生培训讲座】是由【niuww】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【ACM新生培训讲座】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。ACM新生培训讲座
第1页/共18页
FlaviusJosephus
《犹太战记》(WaroftheJews)
《约瑟夫自传》(TheLifeofFlaviusJosephus)
第2页/共18页
约瑟夫环问题
在犹太人和罗马的战争期间,约瑟夫和其他40个犹太反叛者被罗马军队困在一个山洞中,这些犹太反叛者宁愿***也不想被罗马军队抓住,于是他们就站成一个环,从其中某个人开始数,每数到的第三个人就要被杀掉,直到所有人都死光了。但是约瑟夫和他的一个朋友觉得***是没有意义的,他们并不想死,于是他很快就算出了他和他的朋友应该站在什么位置,使他们两个成为最后被杀的那两个人,并最终活了下来。
第3页/共18页
约瑟夫环问题一
问题描述:编号从1到n的n个人站成一个环,从第一个人开始,每数到2的时候,去除该位置上的人,直到只剩下一个人,求剩下的这个人的编号。
我们用J(n)表示人数为n的时候的解。
第4页/共18页
约瑟夫环问题一
去掉的人的编号依次为2,4,6,8,10,3,7,1,9,最后只剩下5,所以J(10)=5。
第5页/共18页
约瑟夫环问题一
第6页/共18页
约瑟夫环问题一
当有偶数个人的时候,我们假设为2n个人,经过第一圈之后还剩下n个人。
第7页/共18页
约瑟夫环问题一
剩下的n个人又是一个新的约瑟夫环问题。
1234…n-1n
1357…2n-32n-1
J(2n)=2*J(n)-1.
第8页/共18页
约瑟夫环问题一
当有奇数个人的时候,我们假设为2n+1个人,经过第一圈之后还剩下n+1个人。去掉2n之后,下一个要去掉的就是1,最后还是剩下n个人。
第9页/共18页
约瑟夫环问题一
剩下的n个人还是一个新的约瑟夫环问题。
1234…n-1n
3579…2n-12n+1
J(2n+1)=2*J(n)-1
第10页/共18页