用 Python 编写程序来计算 n 个人拨动的灯的数量

pythonserver side programmingprogramming更新于 2026/1/23 6:04:17

假设我们有数字 n，假设房间里有 n 个拨动开关，房间里有 n 个人，他们按如下方式拨动开关 −

第 1 个人过来拨动所有开关。
第 2 个人过来拨动 2 的倍数的开关:2、4、6、...
第 i 个人过来拨动 i 的倍数的开关。等等。

我们必须找到最终处于开启位置的开关数量。

因此，如果输入为 n = 5，则输出将为 2，因为最初的灯泡为 [0, 0, 0, 0, 0]。

玩家 1 之后:[1, 1, 1, 1, 1]
玩家 2 之后:[1, 0, 1, 0, 1]
玩家 3 之后:[1, 0, 0, 0, 1]
玩家 4 之后:[1, 0, 0, 1, 1]
玩家 5 之后:[1, 0, 0, 1, 0]

最后有 2 盏灯处于开启状态状态

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

l := 0
r := n
当 l <= r 时，执行
- mid := l + floor of (r - l)/2
- 如果 mid * mid <= n < (mid + 1)^2，则
  - 返回 mid
- 否则，当 n < mid^2 时，则
  - r := mid
- 否则，
  - l := mid + 1

示例

让我们看看下面的实现以便更好地理解 −

def solve(n):
   l, r = 0, n
   while l <= r:
      mid = l + (r - l) // 2
      if mid * mid <= n < (mid + 1) * (mid + 1):
         return mid
      elif n < mid * mid:
         r = mid
      else:
         l = mid + 1

n = 5
print(solve(n))