สมมติว่าเรามีตัวเลข n; เราต้องหาจำนวนขั้นต่ำของตัวเลขฟีโบนักชีที่ต้องรวมกันเป็น n
ดังนั้นหากอินพุตเป็น n =20 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถใช้ตัวเลขฟีโบนักชี [2,5, 13] เพื่อรวมเป็น 20
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
-
res :=0
-
fibo :=รายการที่มีค่า [1, 1]
-
ในขณะที่องค์ประกอบสุดท้ายของ fibo <=n ทำ
-
x :=ผลรวมของสององค์ประกอบสุดท้ายของ fibo
-
แทรก x ลงใน fibo
-
ในขณะที่ n ไม่ใช่ศูนย์ ให้ทำ
-
ในขณะที่องค์ประกอบสุดท้ายของ fibo> n ทำ
-
ลบองค์ประกอบสุดท้ายออกจาก fibo
-
-
n :=n - องค์ประกอบสุดท้ายของ fibo
-
res :=res + 1
-
-
-
ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
ตัวอย่าง
class Solution: def solve(self, n): res = 0 fibo = [1, 1] while fibo[-1] <= n: fibo.append(fibo[-1] + fibo[-2]) while n: while fibo[-1] > n: fibo.pop() n -= fibo[-1] res += 1 return res ob = Solution() n = 20 print(ob.solve(n))
อินพุต
20
ผลลัพธ์
3
