第05周 约瑟夫问题.ppt

北京工商大学　　陈红倩 约瑟夫问题 陈红倩chenhq123@ * 上周作业 课后作业1 直线分割出来的区域中，有些是闭合区域，有些是无界区域 n条直线最多能分割出的闭合区域数是多少？ 解题思路 新的直线 从远端出现，即增加1个无界区域 每遇到交点，即多1个区域 n个闭合区域 最后1个无界区域 解题思路 每条直线出现的区域中 有2个无界区域 其他的都是闭合区域 L(n) = 1 + 1 + 2 + … + n = 1 + Sn H闭合(n) = 1 + Sn – 2 * n 课后作业2 当弯角折线改为锯齿线，n条锯齿线能获得的最大区域数是多少？ 弯角折线 vs 锯齿线 相当于添加了三条直线 但少了几个？ 5个 解题思路 锯齿线 n==1 n==2 n==3 …… n 3条直线 m==3 m==6 m==9 m==3n 最终答案 Z(n)=H(3n)-5*n = = 课后作业3 将平面中的直线问题由2维扩展为3维，即立体空间中的切割面问题 则n个平面，最多能划分出多少个3D区域？ 解题思路 3D中，第n个平面最多可与之前的n-1个平面相交，产生n-1条直线 这n-1条直线，将第n个平面划分为Sn-1+1个区域 每个平面区域，都将1个原有3D区域分割为2个3D区域 解题思路 3D中，每增加第n个平面，增加的3D区域数，与 (n-1)条直线在平面上切割的平面区域数 相同 Sn-1+1 D(1) = 2 D(n) = D(n-1) + Sn-1+1 最终结果 课后思考1 蚂蚁爬格子问题 n==1 2 n==2 6 n==3 20 …… 课后思考2 n个平面上的点，最多能连接出多少条直线？ 增加第n个点，则可与前n-1个点连成直线 1+2+…+(n-1) 课后思考3 两个平面，各有n个点， 这些点，最多能连接出多少个平面？ 解题思路 A平面上的第n个点与B平面上的每1条直线，连成1个平面 B平面上的前n-1个点，连出n(n-1)/2条直线 第n个点增加平面数 n(n-1)/2 * 2 最终结果 约瑟夫问题 约瑟夫问题 1世纪，Flavius Josephus 犹太人 vs 古罗马人的战争 41个犹太人被抓 39人想自杀，2人不想自杀 在剩下人的圆圈中，报到3的人自杀 过程（报2） 易于理解的通用解法 神奇的高效解法(报3) 神奇的高效解法 u = (v+3) % 8 u = (v+3) % 7 u = (v+3) % 6 u = (v+3) % 5 神奇的高效解法 u = (v+3) % 3 u = (v+3) % 2 u = (v+3) % 1 规律 在1人队列中， 0号肯定是最后一个 1人队列中的0号，在2人队列中编号为(0+3) % 2 = 1号，即1号是最后一个 2(1号) = 3( (1+3) % 3 = 1号 ) 3(1号) = 4( (1+3) % 4 = 0号 ) 4(0号) = 5( (0+3) % 5 = 3号 ) 规律 每一次的变换规则 kN = ( kN-1 + m ) % N 教材中的约瑟夫问题 过程（报2） 过程（报2） 递归规律（报2） J(1) = 1 J(2n) = 2 * J(n) – 1 J(2n+1) = 2 * J(n) + 1 J(2n+1) - J(2n) = 2 前部分答案（报2） 公式演算（报2） J(2m+l) = 2*l + 1 2m+l 与 (2*l + 1) 间的关系 2m 即为m+1位二进制数 (100….00)2 2m+l 的第m+1位一定为1， l为后面的那m位二进制数 2*l + 1 即： l 左移1位，并使得末尾位由0变为1（ 第m+1位就是1） 奇怪的规律（报2） J( (bmbm-1…b1b0)2 ) = (bm-1…b1b0bm)2 奇怪的规律（报2） 对于报2的约瑟夫问题来说 只需要将总人数，变为2进制数 然后循环向左移1位，就是最后退出的那个人 约瑟夫函数的性质 J(2m+l) = 2*l + 1 如果一直重复做J函数 则经过n次重复，能使得J函数得到一个稳定解 (11)2 (111)2 (1111)2 (11111)2 J(2m+l) = 2*l + 1 也有一些n 会使得J(n) = n/2 (10)2 (1010)2 (101010)2 2 结论 本周作业 实验 数学?程序 下周进行一次习题课，专门让大家讲解程序 并提交实验报告 程序模块1 汉诺塔问题 输出最小移动次数 输出移动过程 程序模块2 汉诺塔问题 输出AB间不能直接移动条件下 输出最少移动次数 输出移动过程 程序模块3 汉诺塔问题 输出2n个盘子的移动次数