线性表应用－－Josephus问题的解法（Python 版）

线性表应用

－－Josephus问题的解法（Python 版）

Josephus问题描述：假设有n个人围坐一圈，现在要求从第k个人开始报数，报到第m个数的人退出。然后从下一个人开始继续报数并按照相同的规则退出，直到所有人退出。要求按顺序输各出列人的编号。　　

基于数组概念解法

1. 建立一个包含n个人的表
2. 找到第k个人，从那里开始
3. 处理过程中采用吧相应元素修改为0的方式表示已经退出，反复做：
4. 数m个（尚在坐的）人，遇到表的末端转回到下标0继续
4. 把表示第m个人的表元素修改为0
5. n个人出列表示结束

 1 def josephus(n,k,m):
 2     people = list(range(1,n+1))  # 初始化，序列标号 1,2,3,...,n
 3     i = k - 1  # i 记录了第k个人的下标
 4     for num in range(n):  # 循环n次
 5         count = 0
 6         while count < m :
 7             if people[i] > 0:  # 跳过 已经退出的人
 8                 count += 1
 9             if count == m :  # 这里注意: i还没＋1
10                 print(people[i], end="")
11                 people[i] = 0
12             i = (i + 1) % n   # 控制 i 的循环
13         if num < n + 1 :
14             print(", ",end="")
15         else :
16             print("")

基于顺序表的解法　

利用列表的性质，弹出报数为m的人

1 # 利用列表的性质，弹出报数为m的人
2 
3 def josephus_L(n,k,m):
4     people = list(range(1,n+1))
5     num , i  = n , k-1
6     for num in range(n,0,-1):
7         i = (i + m - 1) % num  # 报数m的人的下标
8         print(people.pop(i),end="") # 报数第m个数的人弹出后 i 自动指向下一个
9     return

基于循环单链表的解法

 1 ＃基于单循环链表的解法
 2 
 3 class Josephus(LCList) :
 4 
 5     def turn(self,m):
 6         for i in range(m) :
 7             self._rear = self._rear.next  # self._rear 指向尾节点
 8 
 9     def __init__(self,n,k,m) :
10         LCList.__init__(self) :
11         for i in range(n) :
12             self.append(i + 1)
13         self.turn(k-1)
14         while not self.is_empty() :
15             self.turn(m-1)  # 循环m次，self._rear 指向m，弹出 m＋1
16             print(self.pop(),end=("
" if self.is_empty() else ", "))
17 
18 Josephus(10,2,7) # 运行

LCList 的定义请查看本人博客的文章：数据结构之线性表