Hiểu bài toán

Xây dựng dãy số fibonacy với quy luật: f1 = 1, f2 = 1, fn = fn-1 + fn-2 (với n >= 3). Given n (1 <= n <= 30), in ra n số đầu tiên của dãy trên một dòng, mỗi số cách nhau một khoảng trắng.

Các cách tiếp cận

Cách Quay lui (Recursion)

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << fibo(i) << " ";
    }
    return 0;
}

• Time Complexity: O(2^n)
• Space Complexity: O(n)

Phương pháp này sử dụng công thức truy hồi trực tiếp. Hàm fibo(n) gọi đệ quy cho các giá trị nhỏ hơn để tính toán. Tuy nhiên, cách này cực kỳ kém hiệu quả do tính toán lại các giá trị đã biết nhiều lần. Với n=30, số lượng lời gọi hàm là rất lớn nhưng vẫn có thể chạy do giới hạn n nhỏ.

Cách Lặp (Iteration)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 1, b = 1;

    if (n >= 1) cout << a << " ";
    if (n >= 2) cout << b << " ";

    for (int i = 3; i <= n; i++) {
        long long c = a + b;
        cout << c << " ";
        a = b;
        b = c;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất. Thay vì dùng đệ quy, ta dùng 3 biến để lưu giá trị của 3 số liên tiếp (hoặc 2 biến để cập nhật). Vòng lặp chạy từ 3 đến n, tính số mới dựa trên 2 số trước đó và cập nhật biến. Cách này tránh được việc tính toán lại nhiều lần và sử dụng bộ nhớ tối thiểu.

Cách Mảng động (Dynamic Programming)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long f[35];
    f[1] = 1;
    f[2] = 1;

    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }

    for (int i = 1; i <= n; i++) {
        cout << f[i] << " ";
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng một mảng để lưu trữ tất cả các số fibonacy đã tính toán. Ta điền mảng theo thứ tự từ 1 đến n. Cách này giúp việc truy xuất và in ra các số rất dễ dàng, nhưng tiêu tốn nhiều bộ nhớ hơn so với phương pháp lặp (vẫn chấp nhận được với n <= 30).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vì n nhỏ (<= 30), dữ liệu hoàn toàn nằm trong khả năng xử lý của kiểu long long (số thứ 30 là 832040).
• Phương pháp lặp (Iteration) là hiệu quả nhất về cả thời gian và bộ nhớ cho bài toán này.

Lỗi thường gặp

• Sử dụng kiểu int thay vì long long có thể gây tràn số (overflow) nếu n lớn hơn một chút (ví dụ n=50). Tuy nhiên với n=30 thì int vẫn đủ.
• Đặt sai điều kiện dừng đệ quy hoặc sai bước nhảy của vòng lặp (bắt đầu từ 3 thay vì từ 1).