【程序片段题】约瑟夫问题（循环链表实现） 【问题描述】 约瑟夫环问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀的顺序是：5，4，6，2，3，1。 【输入形式】 输入两个正整数N和M，N表示N个人，M表示报数到M； 【输出形式】 输出依次出列的序号。以空格作为分隔。

n, m = map(int, input().split())

# 初始化循环链表
people = [i for i in range(1, n+1)]
current = 0

while len(people) > 1:
    # 找到要删除的人的索引
    current = (current + m - 1) % len(people)
    # 输出要删除的人的序号
    print(people.pop(current), end=' ')
    
print(people[0]) # 最后一个人剩下来

**说明：**

本程序使用循环链表来实现约瑟夫问题，将所有人存在一个列表中，每次找到要删除的人的索引，然后通过 `pop()` 方法删除该人，并输出其序号。由于删除一个人之后，列表的长度改变，所以需要对索引进行调整，这样才能保证循环链表的正确性。最后剩下的一个人即为答案。

相关问题

约瑟夫问题是个有名的问题:n个人围成一圈,从第一个开始报数,第m个将被杀掉,最后剩

约瑟夫问题是一个古老且著名的问题，它描述了n个人围成一圈，从第一个人开始报数，每次报到第m个人，这个人将被杀掉，直到最后只剩下一个人。

这个问题可以通过模拟来解答。首先，我们创建一个包含n个人的循环链表，每个节点表示一个人。然后，我们从第一个人开始，按顺序数m个人，直到找到第m个人。然后，我们将这个人从链表中移除，再次从移除的下一个人开始，继续数m个人，一直重复这个过程，直到链表中只剩下一个人。

为了更好地理解，我们可以用一个具体的例子来说明。假设有5个人（编号为1,2,3,4,5）围成一圈，从第一个人开始报数，第3个人将被杀掉。

首先，我们从第一个人开始，数1,2,3，第3个人是编号为3的人，将其移除。现在剩下4个人：1,2,4,5。接下来，我们从编号为4的人开始，数1,2,3，第3个人是编号为2的人，将其移除。现在剩下3个人：1,4,5。我们继续从编号为4的人开始，数1,2,3，第3个人是编号为5的人，将其移除。现在剩下2个人：1,4。我们再次从编号为1的人开始，数1,2,3，第3个人是编号为1的人，将其移除。最后，只剩下编号为4的人，他是幸存者。

总结来说，约瑟夫问题是一个经典的数学问题，可以通过模拟来解答。每次从围成一圈的人中按顺序数m个人，将第m个人移除，最后只剩下一个人。这个问题具有一定的实际意义，也可以帮助我们理解和运用数学模型。

循环链表解决约瑟夫环问题python 并实现一个完整的主程序

好的，以下是循环链表解决约瑟夫环问题的 Python 实现代码：

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

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

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
        else:
            new_node = Node(data)
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
            new_node.next = self.head

    def remove(self, key):
        if self.head.data == key:
            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
            prev = None
            while cur.next != self.head:
                prev = cur
                cur = cur.next
                if cur.data == key:
                    prev.next = cur.next
                    cur = cur.next

    def __len__(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
            if cur == self.head:
                break
        return count

    def display(self):
        elems = []
        cur = self.head
        while cur:
            elems.append(cur.data)
            cur = cur.next
            if cur == self.head:
                break
        print(elems)

    def get_josephus_position(self, step):
        cur = self.head
        while len(self) > 1:
            count = 1
            while count != step:
                cur = cur.next
                count += 1
            print(f"Removed: {cur.data}")
            self.remove(cur.data)
            cur = cur.next
        return self.head.data

if __name__ == '__main__':
    cll = CircularLinkedList()
    n = int(input("Enter the number of people: "))
    k = int(input("Enter the steps to be skipped: "))
    for i in range(1, n+1):
        cll.append(i)
    cll.display()
    print(f"Josephus Position: {cll.get_josephus_position(k)}")

代码中定义了一个 `Node` 类和一个 `CircularLinkedList` 类。`Node` 类用于创建一个节点，而 `CircularLinkedList` 类用于创建循环链表并实现相关操作。具体来说，`CircularLinkedList` 类实现了以下方法：

- `append(data)`：在链表的末尾添加一个新的节点。
- `remove(key)`：删除链表中的节点。
- `__len__()`：返回链表的长度。
- `display()`：显示链表中的元素。
- `get_josephus_position(step)`：使用约瑟夫环算法获取最后一个幸存者的位置。

在 `main` 函数中，我们首先获取用户输入的总人数和步数。然后，我们使用 `for` 循环将数字从 1 到 n 添加到循环链表中。最后，我们调用 `get_josephus_position(step)` 方法来获取最后一个幸存者的位置，并将其打印出来。

希望能对你有所帮助！