Chương trình C++ hiển thị dãy Fibonacci

Dãy Fibonacci chứa các số mà mỗi số là tổng của hai số trước nó. Tạo ra dãy số nguyên:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

Quan hệ truy hồi: F(n) = F(n-1) + F(n-2) với F(0)=0, F(1)=1.

Phương pháp 1: Lập trình động (Dynamic Programming)

#include <iostream>
using namespace std;

void fib(int n) {
    int f[n];
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i < n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    for (i = 0; i < n; i++) {
        cout << f[i] << " ";
    }
}

int main() {
    int n = 10;
    fib(n);
    getchar();
    return 0;
}

Đầu ra

0 1 1 2 3 5 8 13 21 34

Mảng f[n] lưu n số đầu tiên. Khởi tạo f[0]=0, f[1]=1. Vòng lặp tính các phần tử tiếp theo.

for (i = 2; i < n; i++)
    f[i] = f[i-1] + f[i-2];

Phương pháp 2: Đệ quy (Recursive)

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

int main() {
    int n = 10, i;
    for (i = 0; i < n; i++)
        cout << fib(i) << " ";
    return 0;
}

Đầu ra

0 1 1 2 3 5 8 13 21 34

Vòng lặp for gọi hàm fib() đệ quy cho từng số hạng. Hàm trả về 0 hoặc 1 nếu n<=1, ngược lại gọi đệ quy tổng hai số trước.

if (n <= 1) return n;
return fib(n-1) + fib(n-2);