Problem 834 Continued Fractions，連續的整數加分數

又是一個用到遞迴的題目，這題一開始是 A 除以 B，求得餘數 C 後，再來 B 除以 C，每次這樣除下去，答案就出來了。遞迴要停在餘數為 1 或 0 時，餘數1，表示找到最後的 1/x，餘數0，表示可以整除，就等於找到了 1/x。下列只有first是全域變數，專為列印時使用。

void compFraction(int n, int d)
{
    int quo, remainder;
    quo = n/d;
    remainder = n%d;
    if (first)
    {
        first=0;
        printf("%d;", quo);
    }
    else
        printf("%d,", quo);
    if (remainder!=1 && remainder!=0)
        compFraction(d, remainder);
    else
        printf("%d]\n", d);
}

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