[103關務3等][資訊處理]資料結構第一題 - 考試

題目是這樣(雖然大家可能都看過了，不過我還是大略抄一遍...)

兩項是係數的組合遞迴演算法如下

C(r,n) =

0, 若 r > n

1, 若 n==r

1, 若 r==0

C(n-1,r)+C(n-1,r-1), 其他

1. 寫出遞迴函數程式

2. 畫出輸入為 n=5, r=3時，遞迴呼叫的二元樹

3. 承2. 求最後回傳值

4. 承2. 共呼叫遞迴幾次

1.
我是用C++寫的

int func(int r, int n)
{
if(r > n)
return 0;
if(n==r)
return 1;
if(r==0)
return 1;
return (func((n - 1), r) + func((n - 1), (r - 1)));
}

2.
(3, 5)
/ \
(4, 3) (4, 2)

===> (4, 3) ===> 4 > 3 ===> 回傳0
===> (4, 2) ===> 4 > 2 ===> 回傳0

3. 0+0 = 0

4.我其實不太確定這叫一次還是兩次，所以我寫2

這樣也有錯嗎？感覺答案太簡單了?




祝各位金榜題名

--