用python编写约瑟夫环问题

# 约瑟夫环问题

# 根据传统，n个人（编号0~(n-1)）围成一圈，把编号为k的人从圈里杀掉，然后从k+1开始数n-1个人继续杀掉该圈中编号为k的人，
# 直到剩下最后一个人时结束。求该圈最后剩下的人的编号。

# 解题思路：采用链表实现，并使用循环链表来模拟整个过程

class Node:
def __init__(self, data):
self.data = data
self.next = None

class LinkList:
def __init__(self):
self.head = None

# 添加节点
def add_node(self, data):
node = Node(data)

if self.head is None:
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
node.next = self.head

# 删除节点
def remove_node(self, node):
if self.head == node:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = self.head.next
self.head = self.head.next
else:
cur = self.head
while cur.next != self.head:
if cur.next == node:
cur.next = node.next
break
cur = cur.next

# 模拟整个杀人过程
def joseph_ring(self, k):
cur = self.head

# 找到第k个节点
for i in range(k):
cur = cur.next

while self.head.next != self.head:
# 找到要删除的节点
for i in range(1):
cur = cur.next
print('删除节点:', cur.data)

# 删除节点
self.remove_node(cur)

return self.head.data

if __name__ == '__main__':
link_list = LinkList()
n = int(input('请输入总人数：'))
for i in range(n):
link_list.add_node(i)

k = int(input('请输入要删除的节点编号：'))
result = link_list.joseph_ring(k)
print(f'最后剩下编号为{result}的人')