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

更新於: 2021-10-19

144 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告