Python 约瑟夫环问题解法 - 手拉手报数出列

Python 约瑟夫环问题解法 - 手拉手报数出列

问题描述：

假设有 n 个小孩子手拉手围成一个圈，编号为 k(1 <= k <= n )的人从 1 开始报数，报到 m 的那个人出列，它的下一位又从 1 开始报数，报到 m 的又出列……依此类推，直到所有人都出列，由此产生一个出队编号的序列。

示例：

• n=4 [1, 2, 3, 4]
• k=3

则输出：3 2 4 1

Python 代码实现：

n = int(input())
m = int(input())

list6 = list(range(1, n + 1))

while len(list6) != 0:
    if len(list6) < m:
        list6 = list6 + list6[:-1]
    print(list6[m - 1])
    list6 = list6[m:] + list6[:m]

代码解释：

1. 初始化：

   • n：人数
   • m：报数到多少出列
   • list6：保存孩子编号的列表，初始值为 1 到 n

2. 循环出列：

   • while len(list6) != 0：当列表不为空时循环
   • if len(list6) < m：如果列表长度小于 m，则将列表复制一份并追加到末尾，确保有足够的人报数
   • print(list6[m - 1])：输出出列人的编号
   • list6 = list6[m:] + list6[:m]：将列表从第 m 个元素开始截取，并与前面 m 个元素拼接，模拟报数出列过程

运行结果：

输入 n 和 m 的值，程序将输出出队编号的序列。

注意：

• 该代码实现的是约瑟夫环问题的模拟解法，时间复杂度较高，尤其当 n 和 m 较大时。
• 对于更高效的解法，可以使用循环链表等数据结构优化。

其他资源：

• 约瑟夫环问题介绍：https://zh.wikipedia.org/wiki/%E7%B4%84%E7%91%9F%E7%9B%B8%E5%9B%A0%E7%89%87
• 循环链表实现约瑟夫环：https://www.geeksforgeeks.org/josephus-problem-using-circular-linked-list/