Chương trình tìm số Fibonacci tối thiểu để thêm vào n trong Python?

Giả sử chúng ta có một số n; chúng ta phải tìm số Fibonacci tối thiểu được yêu cầu để thêm vào n.

Vì vậy, nếu đầu vào là n =20, thì đầu ra sẽ là 3, vì Chúng ta có thể sử dụng các số Fibonacci [2,5, 13] để tổng thành 20.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau

• res:=0

• fibo:=một danh sách với các giá trị [1, 1]

• trong khi phần tử cuối cùng của fibo <=n, do

  • x:=tổng của hai phần tử cuối cùng của fibo

  • chèn x vào fibo

  • trong khi n khác 0, thực hiện

    • trong khi phần tử cuối cùng của fibo> n, do

      • xóa phần tử cuối cùng khỏi fibo

    • n:=n - phần tử cuối cùng của fibo

    • res:=res + 1

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

Ví dụ

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))

Đầu vào

20

Đầu ra

3