约瑟夫问题（PPT讲稿）Josephus problem

Josephus problem 约瑟夫间题 17计拔裴一凡

Josephus problem 约瑟夫问题 17计拔裴一凡

题目描述 on个人(编号为0,1,…,n-1)围成一个圈子,从0号开始依次 报数,每数到第m个人,这个人就得自杀,之后从下个人开始 继续报数,直到所有人都死亡为止。 o问最后一个死的人的编号

题目描述  n 个人 (编号为0, 1, ..., n-1) 围成一个圈子，从0 号开始依次 报数，每数到第m 个人，这个人就得自杀，之后从下个人开始 继续报数，直到所有人都死亡为止。  问最后一个死的人的编号

模拟 ◎依次判断下一个人是否已经死掉,直到找到第m个活着的人, 则为下一个需要自杀的人 ohttps://github.com/hengxin/learning c/blob/master/njucs 7-ps-tutorial/1-2- osephus/josephus o0(n×logm

模拟  依次判断下一个人是否已经死掉，直到找到第 m 个活着的人， 则为下一个需要自杀的人  https://github.com/hengxin/learning￾c/blob/master/njucs17-ps-tutorial/1-2- josephus/josephus.c  𝑂(𝑛 × 𝑙𝑜𝑔 𝑚 𝑚−1 𝑛)

循环链表 O链表直接指向下一个活着的人,这样链表跳m次即可 ohttps://aithub.com/hengxin/learning c/tree/master/njucsI7-ps-futorial/l-4-josephus-linkedlist oO(n*m)

循环链表  链表直接指向下一个活着的人，这样链表跳m 次即可  https://github.com/hengxin/learning￾c/tree/master/njucs17-ps-tutorial/1-4-josephus-linkedlist  O(n * m)

数据结构维护 第ⅰ次操作,将自杀的人(第ⅹ小从列表中清除,则下一次查 询编号第(X+m-1)%n-)小的人 O二叉搜索树 ◎建树、删除、查询第k小 o平衡树Oogn oTC思考题142 oO(n*log n)

数据结构维护  第 i 次操作，将自杀的人(第 x 小) 从列表中清除，则下一次查 询编号第(x + m – 1) % (n – i) 小的人  二叉搜索树  建树、删除、查询第k 小  平衡树O(log n)  TC 思考题 14-2  O(n * log n)

递归式 O老虑n=8,m=3的情况 081234567 08134567 (x + m %n 05681234(如果已知n=7,m=3的情况

递归式  考虑 n = 8, m = 3 的情况  0 1 2 3 4 5 6 7  0 1 3 4 5 6 7  5 6 0 1 2 3 4（如果已知 n = 7, m = 3 的情况 (x + m) % n

递归式 n=1 o f(n, m)= Gf(n-1,m)+m)%,n>1 o On

递归式  𝑓 𝑛, 𝑚 = ቊ 0 ,𝑛 = 1 𝑓 𝑛 − 1, 𝑚 + 𝑚 %𝑛 , 𝑛 > 1  O(n)

递归式2 o考虑一轮,则有2|×m个人报过数,并死了|2个人 081234567 0813467 X-n%m)% m 0234591

递归式2  考虑一轮，则有 𝑛 𝑚 × 𝑚 个人报过数，并死了 𝑛 𝑚 个人  0 1 2 3 4 5 6 7  0 1 3 4 6 7  2 3 4 5 0 1 x − n%m % n − 𝑛 𝑚 × 𝑚 𝑚 − 1

递归式2 ,n=1 Gf(n-1,m)+m)%n,1<n<m o f(n, m) (+=)9y减1)xn n≥m 1 n o olm+log-- m)

递归式2  𝑓 𝑛, 𝑚 = 0 ,𝑛 = 1 𝑓 𝑛 − 1, 𝑚 + 𝑚 % 𝑛 , 1 < 𝑛 < 𝑚 𝑓 𝑛− 𝑛 𝑚 ,𝑚 −𝑛%𝑚 % 𝑛− 𝑛 𝑚 ×𝑚 𝑚−1 ,𝑛 ≥ 𝑚  𝑂 𝑚 + 𝑙𝑜𝑔 𝑚 𝑚−1 𝑛 𝑚

扩展 求第k(从0开始)个自杀的人的编号 081234567891811121314151617181928212223 0812345670134671367363666

扩展  求第 k (从 0 开始) 个自杀的人的编号  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  0 1 2 3 4 5 6 7 0 1 3 4 6 7 1 3 6 7 3 6 3 6 6 6