Hiểu bài toán

Cho một số nguyên dương N (3 ≤ N ≤ 10^8). Nhiệm vụ là tìm một tập hợp các số Fibonacci phân biệt sao cho tổng của chúng bằng N. Nếu có nhiều cách, in ra một cách bất kỳ. Yêu cầu in ra số lượng số Fibonacci trong tập hợp và các số đó.

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

Cách Greedy (Tham lam)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;

    // Tạo dãy Fibonacci (bắt đầu bằng 1, 2 để loại bỏ số 0 và số 1 trùng lặp)
    vector<long long> fib = {1, 2};
    while (true) {
        long long next = fib.back() + fib[fib.size() - 2];
        if (next > N) break;
        fib.push_back(next);
    }

    vector<long long> res;
    // Duyệt từ số Fibonacci lớn nhất về nhỏ nhất
    for (int i = fib.size() - 1; i >= 0; i--) {
        if (fib[i] <= N) {
            res.push_back(fib[i]);
            N -= fib[i];
        }
    }

    cout << res.size() << endl;
    for (long long x : res) cout << x << " ";
    cout << endl;

    return 0;
}

• Time Complexity: O(log N) - Do số lượng số Fibonacci nhỏ hơn N rất ít (khoảng 45 số nếu N=10^8)
• Space Complexity: O(log N) - Lưu trữ dãy Fibonacci và kết quả

Đây là phương pháp hiệu quả nhất dựa trên định lý Zeckendorf. Định lý này nói rằng bất kỳ số nguyên dương nào cũng có thể biểu diễn duy nhất dưới dạng tổng các số Fibonacci phân biệt không liên tiếp.

Cách thực hiện:

1. Tạo dãy Fibonacci nhỏ hơn hoặc bằng N (bắt đầu 1, 2).
2. Duyệt từ số lớn nhất đến nhỏ nhất.
3. Nếu số Fibonacci đó nhỏ hơn hoặc bằng N còn lại, chọn nó và trừ đi khỏi N.
4. Tiếp tục cho đến khi N bằng 0.

Phương pháp này đảm bảo tìm được một tập hợp các số Fibonacci phân biệt có tổng bằng N.

Cách Quay lui (Backtracking) - Naive

#include <bits/stdc++.h>
using namespace std;

vector<long long> fib;
vector<long long> result;
bool found = false;

void backtrack(int index, long long currentSum, long long target, vector<long long>& path) {
    if (found) return;
    if (currentSum == target) {
        result = path;
        found = true;
        return;
    }
    if (index < 0 || currentSum > target) return;

    // Bỏ qua số hiện tại
    backtrack(index - 1, currentSum, target, path);

    // Chọn số hiện tại
    path.push_back(fib[index]);
    backtrack(index - 1, currentSum + fib[index], target, path);
    path.pop_back();
}

int main() {
    long long N;
    cin >> N;

    fib = {1, 2};
    while (fib.back() + fib[fib.size() - 2] <= N) {
        fib.push_back(fib.back() + fib[fib.size() - 2]);
    }

    vector<long long> path;
    backtrack(fib.size() - 1, 0, N, path);

    cout << result.size() << endl;
    for (long long x : result) cout << x << " ";
    cout << endl;
    return 0;
}

• Time Complexity: O(2^M) - Với M là số lượng số Fibonacci (khoảng 45), đây là quá chậm cho N lớn
• Space Complexity: O(M) - Đệ quy

Sử dụng kỹ thuật quay lui để thử tất cả các tổ hợp có thể của các số Fibonacci để tìm ra tổng bằng N.

Cách thực hiện:

1. Tạo dãy Fibonacci.
2. Dùng đệ quy để thử:
   • Bỏ qua số Fibonacci hiện tại.
   • Hoặc chọn số Fibonacci hiện tại và tiếp tục.
3. Dừng lại khi tìm được tổng bằng N.

Phương pháp này đúng nhưng rất chậm vì phải thử quá nhiều trường hợp.

Cách Lập trình Động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> fib = {1, 2};
    while (fib.back() + fib[fib.size() - 2] <= N) {
        fib.push_back(fib.back() + fib[fib.size() - 2]);
    }

    // dp[i] = true nếu tổng i có thể tạo được
    vector<bool> dp(N + 1, false);
    dp[0] = true;

    for (int x : fib) {
        for (int i = N; i >= x; i--) {
            if (dp[i - x]) dp[i] = true;
        }
    }

    // Tìm đường đi (path reconstruction)
    vector<int> res;
    int curr = N;
    for (int i = fib.size() - 1; i >= 0; i--) {
        if (curr >= fib[i] && dp[curr - fib[i]]) {
            res.push_back(fib[i]);
            curr -= fib[i];
        }
    }

    cout << res.size() << endl;
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

• Time Complexity: O(N * M) - Với N=10^8 thì quá chậm, chỉ hiệu quả cho N nhỏ
• Space Complexity: O(N) - Mảng DP

Sử dụng quy hoạch động để kiểm tra xem tổng N có thể tạo được từ các số Fibonacci không.

Cách thực hiện:

1. Tạo mảng dp[N+1] để đánh dấu các tổng có thể tạo được.
2. Duyệt qua từng số Fibonacci, cập nhật mảng dp.
3. Backtrack để tìm các số tạo nên tổng N.

Phương pháp này chậm và tốn bộ nhớ do N lớn (10^8).

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

Bài học kinh nghiệm

• Định lý Zeckendorf: Mọi số nguyên dương đều có thể biểu diễn duy nhất dưới dạng tổng các số Fibonacci phân biệt không liên tiếp. Điều này cho phép giải bài toán bằng phương pháp tham lam.
• Bắt đầu dãy Fibonacci từ 1, 2 để tránh sự trùng lặp của số 1 (Fibonacci 1 và 2 đều là 1).
• Vì N ≤ 10^8, số lượng số Fibonacci cần dùng rất nhỏ (khoảng 45 số), nên thuật toán tham lam chạy gần như tức thời.

Lỗi thường gặp

• Sử dụng biến kiểu int cho N và các số Fibonacci có thể gây tràn số (overflow) khi N gần 10^8 và các số Fibonacci lớn. Nên dùng long long.
• Quên xử lý trường hợp đặc biệt khi N là số Fibonacci hoặc khi N rất nhỏ.
• Trong thuật toán tham lam, việc duyệt từ lớn đến nhỏ là bắt buộc. Nếu duyệt từ nhỏ đến lớn sẽ không đảm bảo được tính chất 'không liên tiếp' của dãy Fibonacci (ví dụ: 3 = 1 + 2, nhưng 1 và 2 là liên tiếp nhau trong dãy 1, 2, 3, 5...).