[CPE一星49題] UVA948 - Fibonaccimal Base 題目解析與實作

編輯製作： 蔡豐聲、莊祺仁

單位： 中國醫藥大學醫療資訊學系程式俱樂部

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 是其費氏進位表示法。

## 範例測試

輸入：

輸出：

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)

## 解題思路

建構費氏數列：

題目提及輸入的最大數值小於 100000000。
我們需要先建立一個費氏數列，直到數列最大值超過 100000000 為止。
注意：在費氏進位中，通常不使用費氏數列的前兩項（即 0 和第一個 1），而是從 [1, 2, 3, 5, 8, 13...] 開始計算。

貪婪演算法 (Greedy Approach) 分解：

從費氏數列中「小於或等於 $N$」的最大項開始由大到小檢查。
如果目前的費氏數小於或等於 $N$，就將該位置記為 '1'，並讓 $N$ 減去該費氏數。
如果小於 $N$ 且前面已經開始輸出 '1'（即非字首的 0），則記為 '0'。
持續檢查到數列結束。

## 實作程式碼 (Python)

import sys

# 建立一個足夠大的費氏參考數列
fib = [0, 1]
while fib[-1] < 100000000:
    fib.append(fib[-1] + fib[-2])

# 先讀取資料總筆數
for _ in range(int(sys.stdin.readline())):
    # 假設當前讀入資料數值為n
    n = int(sys.stdin.readline())
    print(n, "=", end=" ")
    found = False
    
    # 對費氏數列進行逆向搜尋，當搜尋到費氏數 i 小於等於 n，就進入印字模式輸出 1 並更新 n = n - i
    for i in fib[:1:-1]:
        if n >= i:
            print("1", end="")
            n -= i
            found = True
        # 在印字模式時，持續對費氏數列進行逆向搜尋。
	# 當費氏數 i 大於 n，則印字輸出 0，反之印字輸出 1 並更新 n = n - i
        elif found:
            print("0", end="")
            
    print(" (fib)")

---

本著作採用創用 CC 姓名標示-非商業性-禁止改作 3.0 台灣授權條款授權。

本部落格的免責聲明。

程式俱樂部YT頻道 https://www.youtube.com/@tsai-cai

搜尋此網誌

中國醫藥大學蔡豐聲