用 Python 编写程序来查找收到最后一个气球的孩子的起始索引?

pythonserver side programmingprogramming更新于 2026/2/16 3:24:17

假设我们有 n 个孩子站成一个圈，他们正在等待得到一个气球。分配从第 k 个孩子(第一个在索引 0 处)开始，并给他们一个气球，他们离开圆圈。现在每个第 k 个孩子都会得到一个气球，顺时针旋转，直到只剩下一个孩子得到气球。所以如果我们有 n 和 k，我们必须找到收到最后一个气球的孩子的起始索引。

所以，如果输入是 n = 3 k = 2，那么输出将是 1，在第一轮中，孩子 2 得到一个气球，然后离开，所以圆圈将是 [0, 1]。在第二轮中，孩子 0 得到一个气球，圆圈将为 [1]。

为了解决这个问题，我们将遵循以下步骤:

arr := 一个从 0 到 n 的新列表
init := 0
当 arr 的大小 > 1 时，执行
- remove := (init + k) mod size of arr
- delete arr[remove]
- init := remove
return arr[0]

让我们看看以下实现以便更好地理解:

示例

class Solution:
   def solve(self, n, k):
      arr = list(range(0, n))
      init = 0
      while len(arr) > 1:
         remove = (init + k) % len(arr)
         del arr[remove]
         init = remove
      return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))