Tính FIBO
Xem dạng PDF
Gửi bài giải
Điểm:
5,00
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++
Yêu cầu: Hãy tính F(n) bằng phương pháp quy hoạch động (lập bảng phương án).
Dữ liệu vào: Ghi trong file văn bản FIBO.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n.
Dữ liệu ra: Ghi ra file văn bản FIBO.OUT theo cấu trúc như sau:
- Dòng 1: Ghi giá trị tính được của F(n).
Ví dụ:
|
FIBO.INP |
FIBO.OUT |
|
5 |
8 |
Thuật toán:
Gọi F[i] là giá trị Fibonaci của fi (0 <= i <= 50).
Ta có công thức quy hoạch động như sau:
F[i] := F[i-1] + F[i-2];
Như vậy, việc tính fn được thực hiện bằng vòng lặp:
F[0] := 1;
F[1] := 1;
For i := 2 to n do
F[i] := F[i-1] + F[i-2];
Kết quả: giá trị fn nằm trong F[n].
Bình luận