ZeroJudge 解題筆記：a134. 00948 - Fibonaccimal Base

作者：王一哲
日期：2025年12月21日


ZeroJudge 題目連結：a134. 00948 - Fibonaccimal Base

解題想法

由於題目限制要轉換的數字是小於 $100,000,000$ 的正整數，而費氏數列第 40 項就已經是 $102,334,155$，所以建表時只要建前 40 項就可以了。 我另外寫一個轉換數字基底用的函式，假設要轉換的數字是 num，先判斷特例，如果 num 等於 0 直接回傳字串 0，如果 num 等於 1 直接回傳字串 1。接下來用一個 for 迴圈，從表格 fib 後面往前找第一個小於等於 num 的值，以這一項作為起點 start。再用一個 for 迴圈，從 start 往回找到 fib[2] 為止，如果 num 大於等於 fib[j]，要選用這一項，儲存轉換結果的字串 s 加上 1，再將 num 減去 fib[j]；反之，字串 s 加上 0。

Python 程式碼

使用時間約為 19 ms，記憶體約為 2.9 MB，通過測試。

def convert(num):
    if num == 0: return "0"
    if num == 1: return "1"
    start = -1
    for j in range(40, 1, -1):
        if fib[j] <= num:
            start = j
            break
    if start == -1: return "-1"
    s = ""
    for j in range(start, 1, -1):
        if num >= fib[j]:
            s += "1"
            num -= fib[j]
        else:
            s += "0"
    return s

fib = [0]*41
fib[1] = 1
for i in range(2, 41):
    fib[i] = fib[i-1] + fib[i-2]
n = int(input())
for _ in range(n):
    m = int(input())
    print(f"{m:d} = {convert(m)} (fib)")

使用時間約為 13 ms，記憶體約為 3 MB，通過測試。

import sys

def convert(num):
    if num == 0: return "0"
    if num == 1: return "1"
    start = -1
    for j in range(40, 1, -1):
        if fib[j] <= num:
            start = j
            break
    if start == -1: return "-1"
    s = ""
    for j in range(start, 1, -1):
        if num >= fib[j]:
            s += "1"
            num -= fib[j]
        else:
            s += "0"
    return s

fib = [0]*41
fib[1] = 1
for i in range(2, 41):
    fib[i] = fib[i-1] + fib[i-2]

result = []
lines = sys.stdin.readlines()
idx = 1
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    m = int(lines[idx])
    idx += 1
    result.append(f"{m:d} = {convert(m)} (fib)\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 328 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

string solve(int num, int* fib) {
    if (num == 0) return "0";
    if (num == 1) return "1";
    int start = -1;
    for(int i=40; i>1; i--) {
        if (fib[i] <= num) {
            start = i;
            break;
        }
    }
    if (start == -1) return "-1";
    string s = "";
    for(int i=start; i>1; i--) {
        if (num >= fib[i]) {
            s += "1";
            num -= fib[i];
        } else {
            s += "0";
        }
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 建表，fib[0] ~ fib[40]
    int fib[41] = {0};
    fib[1] = 1;
    for(int i=2; i<=40; i++) fib[i] = fib[i-1] + fib[i-2];
    // 解題過程
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int m; cin >> m;
        cout << m << " = " << solve(m, fib) << " (fib)\n";
    }
    return 0;
}