สมมติว่าเรามีตัวเลข n เราต้องหารหัสสีเทาสำหรับตัวเลขที่ระบุ (หรืออีกนัยหนึ่งคือ รหัสสีเทาที่ n) อย่างที่เราทราบดีว่ารหัสสีเทาเป็นวิธีการเรียงลำดับเลขฐานสอง โดยที่ค่าของตัวเลขที่ต่อเนื่องกันแต่ละจำนวนจะต่างกันเพียงหนึ่งบิตเท่านั้น รหัสสีเทาบางส่วน ได้แก่ [0, 1, 11, 10, 110, 111 เป็นต้น]
ดังนั้น หากอินพุตเป็น n =12 ผลลัพธ์จะเป็น 10 เนื่องจาก 12 คือ (1100) ในรูปแบบไบนารี รหัสสีเทาที่สอดคล้องกันจะเป็น (1010) ซึ่งมีค่าทศนิยมเท่ากับ 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา n
- ถ้า n เหมือนกับ 0 แล้ว
- คืน 0
- x :=1
- ในขณะที่ x * 2 <=n ทำ
- x :=x * 2
- ผลตอบแทน x + แก้(2 * x - n - 1)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, n): if n == 0: return 0 x = 1 while x * 2 <= n: x *= 2 return x + self.solve(2 * x - n - 1) ob = Solution() n = 12 print(ob.solve(n))
อินพุต
12
ผลลัพธ์
10
