更多遞迴的範例

組合數

n 是正整數,0 <= k <= n, 則從 n 個物件中任取 k 個物件的組合數記做 {n\choose k} 它的一個常見的計算公式是

{n\choose k} = \frac{n!}{k!\cdot(n-k)!}
但是直接用這個公式來計算是很不明智的,因為它牽涉到階乘計算, 而階乘數很大,很容易就超過了 intunsigned int 的容許範圍。 另一個常見的公式,或說遞迴公式,是
{n\choose k} = {n-1\choose k-1} + {n-1\choose k}
當然這也未必是最好的計算方法,我們用這個公式來示範 C 的遞迴函式。

以下的主程式,輸出 n 從 0 到 9 的楊輝三角,只是排版不很漂亮。 主程式呼叫函式 choose() 來計算組合數。 此函式規定,若 k > n 則組合數是 0。


#include <stdio.h>
   
main() {
    unsigned int n, k, choose(unsigned int, unsigned int);
    for (n=0; n<10; ++n) {
        for (k=0; k<=n; ++k)
            printf("%u ", choose(n,k));
        putchar('\n');
    }
}
  
unsigned int choose(unsigned int n, unsigned int k) {
    if (k>n)
        return 0;
    else if (k==0 || n==k)
        return 1;
    else
        return choose(n-1,k-1) + choose(n-1,k);
}

【未完待續】

習題

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]



注意:此處所有文件均為原著,個別的版權宣告日後會一一公布, 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片,以免觸犯著作權法。

Created: Feb 25, 2001
Last Revised: Feb 25, 2001
© Copyright 2001 Wei-Chang Shann 單維彰

shann@math.ncu.edu.tw