Hiểu bài toán

Bài toán yêu cầu in ra dãy số Fibonacci gồm N số nguyên dương đầu tiên, bắt đầu từ F1 = 1, F2 = 1. N là số nguyên không vượt quá 100. Dãy số Fibonacci được định nghĩa đệ quy: Fn = F{n-1} + F_{n-2} với n >= 3. Vì N nhỏ (<= 100), ta có thể tính toán trực tiếp và lưu trữ các giá trị.

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

Cách Sử dụng mảng động (Dynamic Programming) với số nguyên lớn (Big Integer)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string add(const string& a, const string& b) {
    string res = "";
    int carry = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int N;
    cin >> N;
    if (N <= 0) return 0;
    if (N == 1) { cout << 1; return 0; }
    vector<string> F(N + 1);
    F[1] = "1";
    F[2] = "1";
    for (int i = 3; i <= N; i++) {
        F[i] = add(F[i - 1], F[i - 2]);
    }
    for (int i = 1; i <= N; i++) {
        cout << F[i];
        if (i < N) cout << " ";
    }
}

• Time Complexity: O(N * M) với M là độ dài số Fibonacci lớn nhất (phức tạp về mặt toán học, nhưng với N=100 thì chạy rất nhanh)
• Space Complexity: O(N * M)

Đây là cách tiếp cận tổng quát nhất, sử dụng thuật toán cộng chuỗi để xử lý các số lớn. F_100 có hàng chục chữ số, vượt quá khả năng lưu trữ của kiểu dữ liệu chuẩn như unsigned long long. Bằng cách lưu trữ số dưới dạng chuỗi ký tự và viết hàm cộng thủ công, ta đảm bảo kết quả chính xác cho mọi giá trị N trong giới hạn của đề bài.

Cách Sử dụng mảng động với kiểu số nguyên không dấu (unsigned long long)

#include<bits/stdc++.h>
#define FOR(i,a,b,c) for(unsigned long long  i = a ; i < b ; i+= c ) 
using namespace std ; 
int main(){
    unsigned long long  n ; cin >> n; 
    unsigned long long  f[n+1];
    f[1] = 1 ;
    f[2] = 1 ;
    FOR(i,3,n+1,1) { 
    f[i] = f[i-1] + f[i-2]; }
    FOR(i,1,n+1,1){ cout << f[i] << " "; }
    return 0 ;
}

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

Phương pháp này sử dụng mảng động để tính toán và lưu trữ các số Fibonacci. Kiểu unsigned long long có thể lưu trữ số nguyên lên đến 2^64 - 1. Tuy nhiên, F94 đã vượt quá giới hạn này (F93 là số lớn nhất có thể lưu trong 64-bit unsigned integer). Vì N <= 100, cách này chỉ chính xác khi N < 94. Nếu N >= 94, kết quả sẽ bị tràn số (overflow) và sai.

Cách Sử dụng biến tạm với kiểu số nguyên không dấu

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    unsigned long long a = 1, b = 1;
    if (n >= 1) cout << a;
    if (n >= 2) cout << " " << b;
    for (int i = 3; i <= n; i++) {
        unsigned long long c = a + b;
        cout << " " << c;
        a = b;
        b = c;
    }
    cout << endl;
    return 0;
}

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

Đây là cách tối ưu về mặt bộ nhớ. Thay vì dùng mảng để lưu trữ toàn bộ dãy, ta chỉ cần 2 biến để lưu hai số Fibonacci cuối cùng, và một biến tạm để tính số tiếp theo. In ra từng số ngay khi tính toán xong. Tương tự cách 2, cách này chỉ chính xác với N < 94 do giới hạn của kiểu dữ liệu.

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

Bài học kinh nghiệm

• Bài toán là ứng dụng cơ bản của quy hoạch động (Dynamic Programming) hoặc lặp.
• Với N <= 100, số Fibonacci F_100 rất lớn, vượt quá khả năng lưu trữ của các kiểu số nguyên chuẩn (int, long long). Do đó, để xử lý toàn bộ phạm vi N, cần sử dụng kiểu dữ liệu lớn hơn (Big Integer).

Lỗi thường gặp

• Sử dụng kiểu int hoặc long long mà không kiểm tra tràn số (overflow) cho N lớn (>= 94). Điều này dẫn đến lỗi runtime hoặc sai kết quả.
• Quên xử lý trường hợp N = 0, N = 1 hoặc N = 2 trong code, dẫn đến lỗi truy cập mảng ngoài phạm vi hoặc in sai.