Hiểu bài toán

Cho một số nguyên dương M. Tìm một dãy các số Fibonacci (với các số Fibonacci là các số thuộc dãy: 1, 1, 2, 3, 5, 8, ... nhưng trong dãy kết quả không được phép có số 1) sao cho tổng của các số trong dãy bằng chính M. Dãy số tìm được phải được in ra theo thứ tự giảm dần. Ví dụ, với M = 30, dãy số có thể là 21, 8, 1 (nếu cho phép 1) hoặc 13, 8, 5, 2, ... Tuy nhiên,题目要求 không dùng số 1, và dãy phải giảm dần. Yêu cầu của bài toán là biểu diễn M dưới dạng tổng các số Fibonacci phân biệt (không dùng số 1) sao cho dãy số giảm dần.

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

Cách Quay lui (Backtracking) tìm kiếm toàn bộ

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

ll f[100];
void fibo(){
    f[1] = f[2] = 1;
    for(int i = 3; i <= 45; i++) f[i] = f[i-1] + f[i-2];
}

ll M, X[1000], sum = 0;

void Try(int i, int pos){
    for(int j = pos; j >= 2; j--){
        if(f[j] < M){
            if((sum + f[j]) <= M){
                X[i] = f[j];
                sum += f[j];
                if(sum == M){
                    for(int l = 1; l <= i; l++) cout << X[l] << endl;
                    return;
                }
                else Try(i + 1, j);
            }
        }
    }
}

int main(){
    fibo();
    cin >> M;
    Try(1, 45);
    return 0;
}

• Time Complexity: O(2^N) (N là số lượng số Fibonacci nhỏ hơn M, tối đa khoảng 45)
• Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp nhất. Ban đầu, ta tạo sẵn dãy Fibonacci. Hàm Try(i, pos) sẽ thử tất cả các số Fibonacci từ vị trí 'pos' trở xuống để thêm vào dãy hiện tại. Nếu tổng hiện tại chưa vượt quá M, ta đệ quy gọi Try cho vị trí tiếp theo. Nếu tổng bằng M, ta in ra dãy và dừng. Nhược điểm của phương pháp này là độ phức tạp cao, có thể tốn kém thời gian nếu số lượng cách biểu diễn nhiều (tuy nhiên với M lớn, số Fibonacci là 45, nên thực tế vẫn chạy nhanh). Tuy nhiên, giải pháp này chỉ tìm được 1 cách biểu diễn, và cách biểu diễn đó phụ thuộc vào thứ tự duyệt.

Cách Tham lam (Greedy)

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

int64_t solieu(intmax_t a[], intmax_t n) {
    intmax_t k;
    for (long i = 45; i >= 1; i--) {
        if (a[i] < n) {
            k = a[i];
            break;
        }
    }
    return k;
}

int main() {
    freopen("fibonaci.inp", "r", stdin);
    freopen("fibonaci.out", "w", stdout);
    intmax_t n, k = 1, h = 1; cin >> n;
    intmax_t a[46], b[46];
    a[0] = 0; a[1] = 1;
    for (intmax_t i = 2; i < 46; i++) {
        a[i] = a[i - 1] + a[i - 2];
        if (a[i] <= n) k = a[i];
    }
    // Logic tiếp theo để in ra dãy giảm dần...
    // ... (đoạn code bị cắt xén nhưng logic là chọn số Fibonacci lớn nhất <= n còn lại, trừ đi nó, lặp lại)
    while (n != 0) {
        if (ktra(a, n) == 1 && h != 0) {
            h++;
            b[h] = n;
            n = 0;
        } else {
            h++;
            b[h] = solieu(a, n);
            n -= b[h];
        }
    }
    // ... in ra b
    return 0;
}

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

Phương pháp này sử dụng chiến lược tham lam. luân phiên chọn số Fibonacci lớn nhất nhỏ hơn hoặc bằng phần còn lại của M, trừ đi số đó và tiếp tục cho đến khi M về 0. Logic cơ bản là 'luôn chọn bước đi lớn nhất'. Tuy nhiên, cách làm này có thể sai đối với một số bài toán tổng hợp số Fibonacci (ví dụ 10 = 8+2, nhưng tham lam 8 xong thì còn 2, ok; nhưng 19 = 13+5+1, tham lam 13 xong còn 6, chọn 5 xong còn 1, chọn 1 -> 13+5+1. Nếu không được dùng 1 thì sẽ không được). Trong bài này, dường như cách này được sử dụng để tạo ra một dãy giảm dần.

Cách Biểu diễn Zeckendorf (Quy hoạch động / Tham lam theo tính chất)

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

vector<ll> fib(100, 0);
void Fibonacci() {
     fib[1] = 1; fib[2] = 1;
     for (ll i = 3; i <= 60; i++) fib[i] = fib[i - 1] + fib[i - 2];
}

ll m;
void solve(ll sum, vector<ll> v) {
     if (sum > m) return;
     if (sum == m) {
          for (ll x : v) cout << x << '\n';
          exit(0);
     }
     for (int i = 45; i >= 2; i--) {
          if (fib[i] < m) {
               sum += fib[i]; v.push_back(fib[i]);
               solve(sum, v);
               sum -= fib[i]; v.pop_back();
          }
     }
}
int main() {
    Fibonacci(); cin >> m;
    vector<ll> v;
    solve(0, v);
    return 0;
}

• Time Complexity: O(1) - O(45)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất dựa trên tính chất của dãy Fibonacci. 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 (Zeckendorf's Theorem). Tuy nhiên, bài này yêu cầu in ra dãy giảm dần và dường như yêu cầu tìm một cách biểu diễn (có thể không duy nhất). Giải pháp hiệu quả nhất là dùng tham lam: chia M cho số Fibonacci lớn nhất có thể, rồi tiếp tục với phần dư. Ví dụ: M = 30. F(45) > 30. F(44)=... F(13)=233. F(12)=144. ... F(7)=13, F(6)=8, F(5)=5, F(4)=3, F(3)=2, F(2)=1. Chọn 21 (F(8)), dư 9. Chọn 8 (F(6)), dư 1. Chọn 1. Dừng. Dãy: 21, 8, 1. Nếu không được dùng 1, ta dừng ở 21+8=29, dư 1 không dùng được. Nhưng bài này dường như chỉ yêu cầu tìm một cách biểu diễn giảm dần. Cách tối ưu là dùng mảng F, lặp từ lớn đến nhỏ, nếu F[i] <= M thì in ra F[i] và trừ M đi F[i].

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

Bài học kinh nghiệm

• Các số Fibonacci tăng rất nhanh, chỉ cần khoảng 45 số là đủ biểu diễn số lớn hơn 10^9.
• Bài toán có thể được giải quyết bằng cách tìm một dãy con của dãy Fibonacci sao cho tổng bằng M.
• Thuật toán tham lam (luôn chọn số Fibonacci lớn nhất có thể nhỏ hơn phần còn lại của M) là cách hiệu quả nhất để tìm một cách biểu diễn.

Lỗi thường gặp

• Sử dụng số 1 (Fibonacci số 1 hoặc 2) có thể gây sai lệch nếu đề bài cấm (mặc dù trong code mẫu có dùng). Cần kiểm tra kỹ đề bài.
• Quên cập nhật lại biến tổng hoặc vị trí duyệt trong đệ quy/quay lui dẫn đến lặp vô hạn hoặc sai kết quả.
• Độ phức tạp thuật toán nếu không sử dụng tham lam mà dùng quay lui toàn bộ có thể rất lớn.