约瑟夫环问题 Python3 实现：模拟报数游戏，找出淘汰顺序

约瑟夫环问题 Python3 实现：模拟报数游戏，找出淘汰顺序

问题描述

N 个人围成一圈，编号按顺序从 1 到 N 编号，从 1 号开始按照 1，2，3，4 顺序报数，报道 4 者出局并退出圈外，接下来的下一个人重新从 1 开始报数，报到 4 的人退出去圈外，以此类推，请用 Python3 实现，并打印出每个退出人的原序号。

代码实现

def josephus(n):
    circle = list(range(1, n+1))
    idx = 0
    count = 1

    while len(circle) > 0:
        if count % 4 == 0:
            print(circle.pop(idx))
        else:
            idx = (idx + 1) % len(circle)
        count += 1


n = int(input('请输入参与游戏的人数：'))
josephus(n)

代码解释

1. josephus(n) 函数：
   • 初始化一个列表 circle，包含从 1 到 N 的所有编号。
   • idx 表示当前报数的人在列表中的索引，初始为 0，指向第一个元素。
   • count 表示当前的报数，初始为 1。
2. 循环遍历：
   • 循环条件为 len(circle) > 0，即列表不为空，表示还有人留在圈内。
   • 如果当前报数 count 是 4 的倍数，说明该人需要退出，使用 circle.pop(idx) 将其从列表中移除并打印其原序号。
   • 否则，将 idx 更新为下一个要报数的人的索引，使用 (idx + 1) % len(circle) 来确保索引在列表范围内循环。
   • 无论是否淘汰，count 都自增 1。
3. 输入人数：
   • 程序开始时，会提示用户输入参与游戏的人数 n。
4. 调用函数：
   • 然后调用 josephus(n) 函数，开始模拟报数游戏，并打印出每个退出人的原序号。

注意事项

• 该代码假设输入的参与游戏的人数 n 大于 0。

总结

以上代码使用 Python3 实现了约瑟夫环问题，并附带详细的解释说明。该代码简洁易懂，可以方便地理解约瑟夫环问题的算法逻辑。