Chương trình C++ tìm số Fibonacci bằng quy hoạch động

Dãy Fibonacci như sau:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...

Trong dãy này, số hạng thứ n là tổng của số hạng (n-1) và (n-2).

Để tạo ra dãy, chúng ta có thể dùng cách đệ quy, nhưng trong quy hoạch động (dynamic programming), thủ tục đơn giản hơn. Nó có thể lưu trữ tất cả các số Fibonacci trong một bảng, bằng cách dùng bảng đó có thể dễ dàng tạo ra các số hạng tiếp theo trong dãy.

Đầu vào — Nhập số hạng cần tìm. Giả sử là 10

Đầu ra — Số hạng Fibonacci thứ 10 là 55

Thuật toán

genFiboSeries(n)

Đầu vào: Số lượng hạng tối đa.

Đầu ra: Số hạng Fibonacci thứ n.

Bắt đầu
    Định nghĩa mảng fibo kích thước n+2
    fibo[0] := 0
    fibo[1] := 1
    for i := 2 đến n
        fibo[i] := fibo[i-1] + fibo[i-2]
    Trả về fibo[n]
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

int genFibonacci(int n) {
    int fibo[n+2];
    fibo[0] = 0;
    fibo[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    return fibo[n];
}

int main() {
    int n;
    cout << "Nhập số hạng: ";
    cin >> n;
    cout << n << "th Fibonacci Terms: " << genFibonacci(n) << endl;
}

Kết quả đầu ra

Nhập số hạng: 10
10th Fibonacci Terms: 55