《acm新生培训讲座》.ppt

文档介绍：ACM新生培训讲座
编辑ppt
Flavius Josephus
弗拉维奥·约瑟夫(37-100)是第一世纪时的著名的犹太历史学家，也是军官及辩论家。
《犹太古史》(The Antiquities of the Jews)：记录了由圣经创世记至公元66年的犹太人历史，以旧约圣经为蓝图以及古人的传说，编写而成的犹太巨著。由于当时的犹太人散居各地，此书成为各地土生犹太人重要学****典籍，亦为当代神学学者及历史学者所采用。
编辑ppt
Flavius Josephus
《犹太战记》(War of the Jews)
《约瑟夫自传》(The Life of Flavius Josephus)
编辑ppt
约瑟夫环问题
在犹太人和罗马的战争期间，约瑟夫和其他40个犹太反叛者被罗马军队困在一个山洞中，这些犹太反叛者宁愿***也不想被罗马军队抓住，于是他们就站成一个环，从其中某个人开始数，每数到的第三个人就要被杀掉，直到所有人都死光了。但是约瑟夫和他的一个朋友觉得***是没有意义的，他们并不想死，于是他很快就算出了他和他的朋友应该站在什么位置，使他们两个成为最后被杀的那两个人，并最终活了下来。
编辑ppt
约瑟夫环问题一
问题描述：编号从1到n的n个人站成一个环，从第一个人开始，每数到 2的时候，去除该位置上的人，直到只剩下一个人，求剩下的这个人的编号。
我们用J(n)表示人数为n的时候的解。
编辑ppt
约瑟夫环问题一
去掉的人的编号依次为2,4,6,8,10,3,7,1,9,最后只剩下5，所以J(10)=5。
编辑ppt
约瑟夫环问题一
编辑ppt
约瑟夫环问题一
当有偶数个人的时候，我们假设为2n个人，经过第一圈之后还剩下n个人。
编辑ppt
约瑟夫环问题一
剩下的n个人又是一个新的约瑟夫环问题。
1 2 3 4 … n-1 n
1 3 5 7 … 2n-3 2n-1
J(2n)=2*J(n)-1.
编辑ppt
约瑟夫环问题一
当有奇数个人的时候，我们假设为2n+1个人，经过第一圈之后还剩下n+1个人。去掉2n之后，下一个要去掉的就是1，最后还是剩下n个人。
编辑ppt