โปรแกรมนับจำนวนไฟที่พลิกโดยคน n คนใน Python

สมมติว่าเรามีหมายเลข n ให้พิจารณาว่าไม่มีสวิตช์เปิดปิดในห้องหนึ่งและมีคนอยู่ในห้องนั้น n คน พวกเขาพลิกสวิตช์ดังนี้ -

• คนที่ 1 มาพลิกสวิตช์ทั้งหมด
• คนที่ 2 มาพลิกสวิตช์ที่เป็นทวีคูณของ 2:2, 4, 6, ...
• คนที่ฉันมาและพลิกสวิตช์ที่เป็นทวีคูณของ 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 ทำ
  • กลาง :=l + ชั้นของ (r - l)/2
  • ถ้า mid * mid <=n <(mid + 1)^2 แล้ว
    • คืนกลางคัน
  • มิฉะนั้นเมื่อ n
  • r :=กลาง
• มิฉะนั้น
  • l :=กลาง + 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