定义“圆桌”函数,实现以下功能:有8个人,分别为abcdefgh,编号为别为1~8,按顺序围绕圆桌坐下,从第一个人按顺序报数1,2,3,数到3的倍数的人退出,再从下一个人重新开始数,请输出依次退出人的姓名。(约瑟夫环) Eg.8个人abcdefgh,则输出cfaebhdg
时间: 2023-02-05 22:01:42 浏览: 102
圆桌函数的定义如下:
```
def round_table(names: List[str], m: int) -> List[str]:
"""
names: 代表人的姓名列表
m: 每次报数的倍数
"""
result = []
# 初始化环状链表
circle = CircleList(names)
# 循环报数
while circle.size > 0:
# 每次移动m-1步,再取出元素
for i in range(m-1):
circle.move_next()
result.append(circle.pop_current())
return result
```
其中,`CircleList`是一个环状链表的数据结构,具体实现可以参考下面的代码:
```
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class CircleList:
def __init__(self, values):
self.size = len(values)
self.current = None
if self.size > 0:
self.current = Node(values[0])
p = self.current
for value in values[1:]:
p.next = Node(value)
p = p.next
p.next = self.current
def move_next(self):
"""移动到下一个元素"""
if self.current is not None:
self.current = self.current.next
def pop_current(self):
"""取出当前元素,并将当前指针指向下一个元素"""
if self.current is None:
return None
value = self.current.value
if self.current.next == self.current:
self.current = None
else:
self.current.value = self.current.next.value
self.current.next = self.current.next.next
self.size -= 1
return value
```
最后,你可以这样调用圆桌函数:
```
names = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
result = round_table(names, 3)
print(result) # 输出 ['c', 'f', 'a', 'e', 'b', 'h', 'd', 'g']
```
阅读全文