สมมติว่าเรามีตัวเลข 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
