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)