Chương trình C++ cho Định lý Zeckendorf

Đị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 không liền kề (không có hai số Fibonacci liên tiếp).

Ví dụ: 10 = 8 + 2 (8 và 2 là số Fibonacci, không liền kề).

Thuật toán

1. Khi sum > 0:
2. Tìm số Fibonacci lớn nhất ≤ sum.
3. In số đó, trừ khỏi sum.
4. Lặp lại.

Code ví dụ

#include <iostream>
using namespace std;

// Tìm số Fibonacci lớn nhất <= n
int fibonacci(int n) {
    if (n == 0 || n == 1) return n;
    
    int prev = 0, curr = 1, next = 1;
    while (next <= n) {
        prev = curr;
        curr = next;
        next = prev + curr;
    }
    return curr; // curr là số Fibonacci lớn nhất <= n
}

void nonNeighbourFibo(int sum) {
    while (sum > 0) {
        int fibo = fibonacci(sum);
        cout << fibo << " ";
        sum -= fibo;
    }
}

int main() {
    int sum = 120;
    cout << "Tong " << sum << " = cac so Fibonacci khong lien ke: ";
    nonNeighbourFibo(sum);
    return 0;
}

Kết quả

Tong 120 = cac so Fibonacci khong lien ke: 89 21 8 2

Kiểm tra

89 + 21 + 8 + 2 = 120 ✓
Các cặp liên tiếp trong dãy Fibonacci: (1,1), (1,2), (2,3), (3,5), (5,8), (8,13), (13,21), (21,34), (34,55), (55,89)...
89 và 21 không liên tiếp ✓
21 và 8 không liên tiếp ✓
8 và 2 không liên tiếp ✓

Ứng dụng

• Nén dữ liệu (Fibonacci coding).
• Thuật toán tham lam (greedy) tối ưu.
• Lý thuyết trò chơi (Wythoff Nim).