Chương trình đếm số lần bật đèn của n người bằng Python

Giả sử chúng ta có một số n, coi có n công tắc bật tắt trong một phòng và có n người có mặt trong phòng đó, họ bật công tắc như sau -

• Người 1 đến và bật tất cả các công tắc.
• Người thứ 2 đến và bật các công tắc là bội số của 2:2, 4, 6, ...
• Người tôi đến và bật các công tắc là bội số của tôi. vân vân.

Cuối cùng chúng ta phải tìm số lượng công tắc sẽ ở vị trí.

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là 2, vì bóng đèn ban đầu là [0, 0, 0, 0, 0].

• Sau trình phát 1:[1, 1, 1, 1, 1]
• Sau người chơi 2:[1, 0, 1, 0, 1]
• Sau người chơi 3:[1, 0, 0, 0, 1]
• Sau người chơi 4:[1, 0, 0, 1, 1]
• Sau người chơi 5:[1, 0, 0, 1, 0]

Ở cuối có 2 đèn ở trạng thái BẬT

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• l:=0
• r:=n
• while l <=r, do
  • giữa:=l + tầng của (r - l) / 2
  • nếu mid * mid <=n <(mid + 1) ^ 2, thì
    • trở lại giữa chừng
  • ngược lại khi n
  • r:=mid
• nếu không,
  • l:=mid + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

5

Đầu ra

2