NOJ 1113 斐波那契數應用：公里轉英里模擬

問題描述

斐波那契數列 F1=1, F2=2, Fn=Fn-1+Fn-2。任意正整數 x 可唯一表示為不相鄰斐波那契數之和（Zeckendorf 表示）。轉換規則：將 x 的 Zeckendorf 表示右移一位（最低位捨去），得到 y 的表示，計算 y 值。多查詢輸出 y。

模擬流程

1. 預計算斐波那契數列（至 > 最大輸入）。
2. 對每個 x，貪心從大到小構造 Zeckendorf 表示（標記 used[i]）。
3. 右移：y = Σ used[i] * F_{i-1}（used[1] 捨去）。

代碼實現

int f[25], used[25];
int main() {
    f[1]=1; f[2]=2;
    for (int i=3;i<25;i++) f[i]=f[i-1]+f[i-2];
    int T; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        fill(used,used+25,0);
        int p=1; while (f[p]<=n) p++; p--; // 最大不超過 n 的索引
        used[p]=1; int sum=f[p];
        for (int i=p-1;i>=1;i--) {
            if (used[i+1]) continue; // 不相鄰
            if (sum+f[i]<=n) { sum+=f[i]; used[i]=1; }
        }
        int ans=0;
        for (int i=2;i<25;i++) if (used[i]) ans+=f[i-1];
        printf("%d\n",ans);
    }
    return 0;
}

關鍵點

• Zeckendorf 表示：貪心取最大不超過剩餘值的斐波那契數，且不取相鄰索引。
• 右移操作：used[i] → used[i-1]，即 y = Σ used[i] * F_{i-1}。
• 輸入範圍較小，int 足夠，斐波那契數列至 F[24] 即覆蓋 2e9。

總結

NOJ 1113 考察 Zeckendorf 表示（斐波那契編碼）的理解與模擬。關鍵在於貪心構造唯一表示，並正確實現「右移一位」的轉換邏輯。代碼簡短，數學性強。