# Fibonaccimal Base(UVA948)
## [程式繳交區](https://hackmd.io/@Renektonn/Bkn63Fldyx/edit)
## 題目
[點我](https://onlinejudge.org/external/9/948.pdf)
## 解題網站
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=889)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=a134)

## 演算法

1. 建立費式數列的表格fib與ans，並輸入n
2. 重複n次
2.1 輸入num
2.2 從最高位掃到最低位，若num大於等於該項費式數列，則將num減掉它，並
2.2 標註在ans上
2.3 輸出答案，格式為:10 = 10010 (fib)
2.4 清空ans

## 程式碼

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

int main() {
    int fib[41];
    int ans[41] = {};
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i <= 40; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    int n, num;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num;
        cout << num << " = ";
        for (int j = 40; j >= 0; j--) {
            if (num >= fib[j]) {
                ans[j] = 1;
                num -= fib[j];
            }
        }
        int idx = 40;
        //必定找得到1，因為輸入皆為正整數
        while (ans[idx] == 0) {
            idx--;
        }
        for (int j = idx; j >= 0; j--) {
            cout << ans[j];
        }
        cout << " (fib)" << endl;
        for (int j = 0; j <= 40; j++) {
            ans[j] = 0;
        }
    }
    return 0;
}

:::info
不必手動處理不能相鄰的部分(greedy)
:::