Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมค้นหาการดำเนินการขั้นต่ำหนึ่งบิตเพื่อทำให้จำนวนเต็มเป็นศูนย์ใน Python


สมมติว่าเรามีตัวเลข n เราต้องแปลงเป็น 0 โดยใช้การดำเนินการต่อไปนี้กี่ครั้งก็ได้ -

  • เลือกบิตขวาสุดในการแทนค่าไบนารีของ n

  • เปลี่ยนบิต ith ในการแทนค่าไบนารีของ n เมื่อบิต (i-1) ถูกตั้งค่าเป็น 1 และบิต (i-2)th ถึง 0 ถูกตั้งค่าเป็น 0

ในที่สุด เราก็ต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นในการแปลง n เป็น 0

ดังนั้น หากอินพุตเป็น n =6 เอาต์พุตจะเป็น 4 เพราะเริ่มแรก 6 ="110" จากนั้นแปลงเป็น "010" โดยการดำเนินการครั้งที่สอง จากนั้นแปลงเป็น "011" โดยใช้การดำเนินการครั้งแรก แล้วแปลงเป็น " 001" โดยใช้การดำเนินการครั้งที่สอง และสุดท้ายแปลงเป็น "000" โดยใช้การดำเนินการครั้งแรก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=รายการไบนารีบิตของตัวเลข n

  • m:=รายการใหม่

  • ล่าสุด:=0

  • สำหรับแต่ละ d ใน n ทำ

    • ถ้าสุดท้ายเหมือนกับ 1 แล้ว

      • d:=1-d

    • สุดท้าย:=d

    • ใส่ d ต่อท้าย m

  • m:=สร้างเลขฐานสองโดยการรวมองค์ประกอบของ m

  • คืนค่า m ในรูปแบบทศนิยม

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

def solve(n):
   n=list(map(int,bin(n)[2:]))
   m=[]
   last=0
   for d in n:
      if last==1:
         d=1-d
      last=d
      m.append(d)
   m=''.join(map(str,m))
   return int(m,2)

n = 6
print(solve(n))

อินพุต

"95643", "45963"

ผลลัพธ์

4