约瑟夫环问题：多轮游戏后的队列顺序 - Python 代码实现

约瑟夫环问题：多轮游戏后的队列顺序 - Python 代码实现

约瑟夫环问题是一个经典的算法问题，描述的是一群人围成一个圆圈，从某个位置开始报数，每报到特定数字的人就出局，直到最后剩下一个人。本文将介绍如何在约瑟夫环问题中实现多轮游戏，并得到每轮游戏完成后出列人员的顺序。

问题描述： 假设有 M 个人围成一个圆圈，从编号为 1 的人开始报数，每报到密码 K 的人就出局。游戏可能玩很多遍，每遍都有新的报数密码。求若干遍游戏完成后队列次序。

解决方案： 为了在约瑟夫环中实现所有出列的人形成新队列，并支持多遍游戏，可以在每次游戏结束后保存出列顺序的列表，然后将该列表作为下一次游戏的初始队列。

Python 代码实现：

# 定义单链表节点结构体
class Node:
    def __init__(self, num):
        self.num = num
        self.next = None

# 创建循环链表
def create_circle_linked_list(M):
    head = Node(1)
    curr = head
    for i in range(2, M + 1):
        newNode = Node(i)
        curr.next = newNode
        curr = newNode
    curr.next = head
    return head

# 删除指定位置节点，并返回其编号
def remove_node(head, pos):
    if pos == 1:
        prev = head
        while prev.next != head:
            prev = prev.next
        removedNode = head
        if head == head.next:
            head = None
        else:
            head = head.next
            prev.next = head
    else:
        prev = head
        for _ in range(pos - 2):
            prev = prev.next
        removedNode = prev.next
        prev.next = removedNode.next
    return removedNode.num, head

# 游戏完成后队列次序
def josephus_game(M, passwords):
    result = []
    head = create_circle_linked_list(M)
    for password in passwords:
        sequence = []
        while head:
            pos = password % M
            if pos == 0:
                pos = M
            removedNum, head = remove_node(head, pos)
            M -= 1
            sequence.append(removedNum)
        result.append(sequence)
        # 更新队列为上一轮的出列顺序
        for num in sequence:
            newNode = Node(num)
            newNode.next = head
            head = newNode
    return result

# 主函数
def main():
    # 读取输入
    inputs = input().split()
    M = int(inputs[0])
    passwords = list(map(int, inputs[1:]))

    # 游戏完成后队列次序
    result = josephus_game(M, passwords)

    # 输出结果
    for sequence in result:
        for num in sequence:
            print(f'{num:4}', end='')
        print()

if __name__ == "__main__":
    main()

代码说明：

1. **Node 类：**定义了单链表节点的结构体，包含编号 num 和指向下一个节点的指针 next。
2. **create_circle_linked_list 函数：**创建了一个包含 M 个节点的循环链表，并将第一个节点作为头节点返回。
3. **remove_node 函数：**从循环链表中删除指定位置的节点，并返回被删除节点的编号。
4. **josephus_game 函数：**执行约瑟夫环游戏，接受参数 M 和 passwords 列表，其中 M 表示初始人数，passwords 列表包含每一轮游戏的密码。该函数返回一个列表，其中每个元素都是一个列表，表示每一轮游戏结束后出列人员的顺序。
5. **main 函数：**读取用户输入，调用 josephus_game 函数进行游戏，并将游戏结果输出。

总结： 本文介绍了如何在约瑟夫环问题中实现多轮游戏，并得到每轮游戏完成后出列人员的顺序。文章包含详细的Python代码示例，并解释了代码逻辑，方便读者理解和应用。希望这篇文章能够帮助您更好地理解约瑟夫环问题，并运用相关算法解决实际问题。