BIỂU DIỄN SỐ (7 ĐIỂM)DÃY SỐ FIBONACI F1, F2, .., FN, .. ĐỢC ĐỊN...

Bài 1: Biểu diễn số (7 điểm)Dãy số Fibonaci F

1

, F

2

, .., F

n

, .. đợc định nghĩa qui nạp nh sau:F

1

= F

2

= 1; F

n

= F

n-1

+ F

n-2

với n>2Yêu cầu: Cho số tự nhiên S (S< 2

³¹

), phân tích số S thành tổng của các sốthuộc dãy Fibonaci và số lợng các số đợc dùng là ít nhất.S = F

i1

+ F

i2

+ .. + F

ik

(1< i

1

< i

2

< .. < i

k

)Dữ liệu vào từ tệp văn bản BDFIBO.INP: chứa duy nhất một số S.Dữ liệu đa ra tệp văn bản BDFIBO.OUT: chứa hai dòngDòng 1: Chứa số K là số lợng các số đợc dùng ít nhất tìm đợc.Dòng 2: Chứa K số theo thứ tự tăng dần thể hiện chỉ số các số trongdãy Fibonaci tìm đợc (nếu có nhiều cách thì chỉ cần đa ra 1 cách)Ví dụ về dữ liệu vào và dữ liệu raBDFIBO.INP BDFIBO.OUT10 23 6