948 Fibonaccimal Base

題目敘述

著名的 Fibonacci 數列從 0 和 1 開始，然後將最後兩個數字相加以得到下一個數字。例如，序列中的第三個數是 1（1 = 1 + 0），第四個是 2（2 = 1 + 1），第五個是 3（3 = 2 + 1），依此類推。

i	0	1	2	3	4	5	6	7	8	9
Fib(i)	0	1	1	2	3	5	8	13	21	34

序列出現在我們生活和自然界的許多事物中，具有深遠的意義。你知道所有正整數都可以表示為費氏數列中某些數字的和嗎？更進一步，任意正整數都能表示為一組不重複的費氏數字之和。例如：

• 13 可以表示為 {13}、{5, 8} 或 {2, 3, 8}；
• 17 可以表示為 {1, 3, 13} 或 {1, 3, 5, 8}。

由於所有正整數都有這個性質（你可以試著自己證明看看），我們可以用這組費氏數作為一種「基底」來表示數字。但如上所見，有些數字可能有多種表示方式。如何解決這個問題？很簡單，如果我們加上「集合中不能有兩個連續的費氏數字」的限制，那麼每個數字就有唯一的表示方式！這個限制之所以合理，是因為任何兩個連續費氏數字的和，正好等於下一個費氏數字。

現在我們已經知道這些，我們可以用二進位序列（只有 0 和 1）來表示任意正整數。例如，17 = 1 + 3 + 13（記住不能使用連續的兩個費氏數字）。我們從最右邊開始，對每個費氏數字，若使用則寫 1，不使用則寫 0。這樣 17 就表示為 100101。詳見下圖。注意，在這種表示法中，最左邊不應該有多餘的 0，因此我們從第一個 1 開始寫。由於「不能使用連續的費氏數字」等價於「二進位序列中不會有連續兩個 1」，我們將這種表示稱為 費氏數進位（Fibonaccimal base），並寫作：

17 = 100101 (fib)
17 = 1 0 0 1 0 1  
    13 8 5 3 2 1  

輸入說明

第一行包含一個整數 N，表示接下來有 N 個數字（1 ≤ N ≤ 500）
接下來有 N 行，每行包含一個小於 100,000,000 的正整數，順序不限

輸出說明

對於每個輸入的十進位整數，輸出格式為：

DEC_BASE = FIB_BASE (fib)

其中 DEC_BASE 是原本的十進位數字，FIB_BASE 是其費氏數基底表示法。詳見範例。

範例輸入

10
1
2
3
4
5
6
7
8
9
10

範例輸出

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)

解題思路

根據測資範圍建一個費式數列表
並依序判斷當前的數字有沒有大於費式數 若有則記錄下來，並將當前的數字減去該費式數 這樣就能找出所有可以組成該輸入的費式數

程式碼

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

int main() {
    vector<int> f(40); f[39] = 1; f[38] = 2; // 建費式數列表
    for (int i = 37; i >= 0; i--) f[i] = f[i+1]+f[i+2];

    int n; cin >> n;
    while (n--) {
        int k; cin >> k; cout << k;
        string ans; // 將結果紀錄於 ans 字串中
        for (auto &i : f) { // 依序判斷費式數
            if (k >= i) ans += "1", k -= i;
            else ans += "0";
        }
        cout << " = " << ans.substr(ans.find('1')) << " (fib)\n"; // 使用 substr 省略掉前面無意義的 0
    }
}