(3Đ) FIBONACCI (7,5 ĐIỂM)DÃY SỐ FIBONACCI ĐƯỢC ĐỊNH NGHĨA NHƯ SAU

Bài 4:(3đ) FIBONACCI (7,5 điểm)Dãy số Fibonacci được định nghĩa như sau:U

1

= U

2

= 1; U

n+1

= U

n

+ U

n-1

(với mọi số nguyên dương n, n > 1).Như vậy, dãy số Fibonacci có dạng sau: 1, 1, 2, 3, 5, 8, 13, 21, 34,… Với một số tự nhiên x bất kỳ khác 0 ta có thể phân tích thành tổng các số Fibonaccikhác nhau (số số hạng của tổng có thể là từ 1 trở lên). Chẳng hạn x = 9, khi đó, ta có: 9 = 1 + 8 hoặc 9 = 1 + 3 + 5Trong hai cách phân tích trên thì cách thứ hai có số số hạng nhiều nhất (3 số hạng).Yêu cầu: Cho trước một số nguyên dương x (x <= 10000). Hãy cho biết, nếu biểu diễn xthành tổng của các số Fibonacci khác nhau thì số số hạng nhiều nhất của một tổng là baonhiêu?Dữ liệu vào: Cho trong file văn bản FIBO.INP chỉ ghi một số nguyên dương x(x<=10000).Dữ liệu ra: Ghi ra file văn bản FIBO.OUT gồm một số nguyên dương n duy nhất là số sốhạng của tổng có số số hạng nhiều nhất trong các tổng.Ví dụ:FIBO.INP FIBO.OUT9 3Chú ý: Đề thi gồm có 2 trang - Giám thị coi thi không được giải thích gì thêmĐ ÁP ÁN áP áN PHẦN LẬP TRÌNH