Josephos问题 假设n个人围坐一圈,现在要求从第k个人开始报数,报到第m个人退出,然后从下一个人开始继续报数并按照同样规则退出,直至所有人退出。要求按照顺序输出退出人的编号。
基于顺序表的解法 当确定退出的人后,就将其编号的元素从列表中删除,这样列表就会越来越短,直至0结束。
1 2 3 4 5 6 7 8 9 def josephos_l (n, k, m) : people = list(range(1 , n+1 )) i = k-1 for num in range(n, 0 , -1 ): i = (i + m-1 ) % num print(people.pop(i)) josephos_l(10 , 2 , 5 )
得出结果为:6 1 7 3 10 9 2 5 8 4
该算法的复杂度是 $O(n^2)$。外出循环体执行n次;内层的pop操作也是需要线性的时间,它的复杂度是n。
基于循环单链表的解法 采用循环单链表来实现,顺序报数,可以认为是沿着结点的next引用一直向后,退出后,就删除该结点。
实现步骤:
创建一个长度为n的链表,
循环链表,并删除确定的结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Josephos (SingleCycleLinkList) : def append (self, item) : node = Node(item) if self.is_empty(): self._head = node node.next = node else : node.next = self._head self._rear.next = node self._rear = node def turn (self, m) : for i in range(m): self._rear = self._rear.next def pop (self) : node = self._rear.next if self._rear.next == self._rear: self._rear = None else : self._rear.next = self._rear.next.next return node.elem def run (self, n, k, m) : for i in range(1 , n+1 ): self.append(i) self.turn(k-1 ) while self._rear: self.turn(m-1 ) print(self.pop())
执行后返回的结果为:
1 2 josephos_link = Josephos() josephos_link.run(10 , 2 , 5 )
结果为:6 1 7 3 10 9 2 5 8 4
它的复杂度可以分为两部分,创建链表的复杂度是$O(n)$,遍历解决问题的复杂度是$O(n*m)$。