中國醫藥大學蔡豐聲

編輯製作： 蔡豐聲、莊祺仁  單位： 中國醫藥大學 醫療資訊學系 程式俱樂部  YT： https://youtu.be/ph0WJF3h0Qw ## 題目資訊 題目名稱： Fibonaccimal Base 編號： CPE10401, UVA948  相關平台： Zero Judge , Online Judge ## 題目解析 有名的費氏數列（Fibonacci sequence）是以 0 和 1 開始，然後把最後的兩個數字相加以得到下一項。例如數列的第三項為 1 ($1=1+0$)，第四項為 2 ($2=1+1$)，第五項為 3 ($3=2+1$)，依此類推。 本題要求我們使用「費氏進位法（Fibonaccimal Base）」來表示一個正整數。齊肯多夫定理（Zeckendorf's Theorem）指出：任何正整數都可以唯一分解成若干個不連續的費氏數之和。我們用一連串的 0 與 1 來表示，其中 1 表示有用到該項費氏數，0 表示沒有用到。為了維持唯一性，不可以連續使用費氏數列中相鄰的項（例如不能同時使用 2 和 3，因為 $2+3=5$，應該直接使用 5）。 舉例來說： $17 = 13 + 3 + 1$ （對應費氏數列中的項，且沒有相鄰項） 將有使用到的項記為 1，沒用到的記為 0，由左至右排列，因此 $17 = 100101 \text{ (fib)}$。 ## 輸入說明 輸入的第一行含有一個數字 $N$，代表以下有幾個數字 ($1 \le N \le 500$)。 接下來有 $N$ 行，每行有一個小於 100000000 的正整數。 ## 輸出說明 對於每個輸入的整數，必須依據下列格式輸出一行： X = Y (fib) 其中 X 是原本的十進位數字，Y 是其費氏進位表示法。 ## 範例測試 輸入：                  10                  1                  2   ...