Python 程序：计算 n 个人翻动开关后亮着的灯泡数量

假设我们有一个数字 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))

输入

5

输出

2

Arnab Chakraborty

更新于: 2021-10-19

144 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习