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/learningc/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/learningc/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