Problem 948 Fibonaccimal Base，費氏級數進位

Problem 948 是要寫一個「十進位」轉成「費氏級數進位」的程式。

首先這要先求出費氏級數擺入陣列，大概宣告 39 個就夠了，依照 f(1) = 1、f(2) = 2，當 n > 2時，f(n) = f(n-1) + f(n-2)，則程式碼如下：

int fib[39] = {0};

void getFib()
{
     int i;
     fib[0] = 1, fib[1] = 2;
     for (i = 2; i < 39; i ++)
         fib[i] = fib[i - 1] + fib[i - 2];
}

只須再程式一開始呼叫 getFib() 函式，就會建立 Fib 的表出來。而主程式中只須將輸入的數值去除每一個 Fib 的數值看它是否為 1，為 1 就印出 1，沒有就印出 0，而程式碼如下：

int n, i, m, j, isPut;
getFib();
scanf("%d", &n);
for (i = 0; i < n; i++)
{
    scanf("%d", &m);
    printf("%d = ", m);
    isPut = 0;
    for (j = 38; j >= 0;j --)
    {
        if ((m / fib[j]) == 1)
        {
            printf("1");
            m %= fib[j];   
            isPut = 1;   
        }
        else if (isPut && (m / fib[j]) == 0)
            printf("0");     
    }
    printf(" (fib)\n");
}

By David.K

p948題目連結
回ACM題庫目錄
回首頁