约瑟夫问题

n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。

方法一:列表操作

 1 #n表示总人数,m表示报到的数
 2 def yuesefu_1(n,m):
 3     #1.将所有元素放进列表中,并定义初始的下标为0
 4     people = [i for i in range(1,n+1)]
 5     x = 0
 6     #2.在列表不空的时候循环
 7     while len(people) > 0:
 8         #3.计算报数的人的下标,
 9         # 1,2,3,4,5,6,7,8 报数
10         # 0,1,2,3,4,5,6,7 下标,每次取出对总人数的余数就是要找的人 
11         dead_location = (x+(m-1))%len(people)
12         yield people.pop(dead_location) #将找到的人移除出列表
13         x = dead_location #从移除出去的人的位置上,继续执行
14 
15 print(list(yuesefu_1(9,4)))

View Code

方法二:链表操作

 1 class LinkList:
 2     #自定义链表实现类
 3     class Node:
 4         def __init__(self,item=None):
 5             self.item = item
 6             self.next = None
 7 
 8     class LinkListIterator:
 9         def __init__(self,node):
10             self.node = node
11 
12         def __next__(self):
13             if self.node:
14                 cur_node = self.node
15                 self.node = cur_node.next
16                 return cur_node.item
17         def __iter__(self):
18             return self
19 
20     def __init__(self,iteratbe=None):
21         self.head = LinkList.Node(0)
22         self.tail = self.head
23         self.extend(iteratbe)
24     
25     #链表添加
26     def append(self,obj):
27         s = LinkList.Node(obj)
28         self.tail.next = s
29         self.tail = s
30     
31     #链表扩展
32     def extend(self,iterable):
33         for obj in iterable:
34             self.append(obj)
35         self.head.item += len(iterable)
36 
37     def remove_nth_node(self,node,m):
38         #删除链表第n个元素
39         for i in range(m-2):
40             node = node.next
41         p = node.next
42         node.next = p.next
43         self.head.item -= 1
44         return p
45 
46 
47     def __iter__(self):
48         return self.LinkListIterator(self.head.next)
49 
50     def __len__(self):
51         return self.head.item
52 
53     def __str__(self):
54         return '<<'+", ".join(map(str,self)) +">>"
55 
56 def yuesefu_link(n,m):
57     people = LinkList([i for i in range(1,n+1)])
58     people.tail.next = people.head.next
59     x = people.head.next
60     while len(people)>0:
61         p = people.remove_nth_node(x,m)
62         x = p.next
63         yield p.item
64 
65 print(list(yuesefu_link(9,4)))

View Code

总结:

时间复杂度: 第一种列表法的时间复杂度是O(n²).第二种链表法的时间复杂度是O(nm)

如果n>m时,链表法优于列表法,n<m时,列表法优于链表法