python约瑟夫环问题列表

以下是 Python 中约瑟夫环问题的一些常见实现方式：

1. 使用列表模拟环，每次根据规则删除列表中的元素，直到只剩下一个元素：

def josephus(n, k):
    people = list(range(1, n+1))
    i = 0
    while len(people) > 1:
        i = (i + k - 1) % len(people)
        people.pop(i)
    return people[0]

2. 使用递归实现，每次找到被淘汰的人的下一个人，然后从该人开始递归，直到只剩下一个人：

def josephus(n, k):
    if n == 1:
        return 1
    else:
        return (josephus(n-1, k) + k-1) % n + 1

3. 使用循环链表实现，每次找到被淘汰的节点的下一个节点，然后删除该节点：

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

def josephus(n, k):
    head = Node(1)
    prev = head
    for i in range(2, n+1):
        current = Node(i)
        prev.next = current
        prev = current
    prev.next = head
    
    current = head
    while current.next != current:
        for i in range(k-1):
            current = current.next
        current.next = current.next.next
    return current.data