推 stator:謝謝L大這麼詳細的解說 05/15 21:03
※ 引述《stator (別急著吃棉花糖)》之銘言：
: 因為正在算一題程式結果題
: 以下程式會算出 C(N, M)，如果 count 的值原先為 0
: ，請問計算 C(5, 3) 後，count 的值為何？
: unsigned int count = 0;
: unsigned int getC(unsigned int N, unsigned int M)
: {
: count++;
: if (N == 0) return (N == M ? 1 : 0);
: else if (M == 0) return 1;
: else return getC(N-1, M) + getC(N-1, M-1);
: }
: (A) 5 (B) 15 (C) 51 (D) 63
: 答案是給C
: 但我算出的結果是49。不知可否請教各位前輩能教我怎麼算嗎??謝謝
終止條件為
1. N = 0
2. M = 0
每當你呼叫 getC(N,M) 的時候
getC(N,M) 就會再呼叫 getC(N-1, M) 和 getC(N-1, M-1)
所以計算如下表 表格中的數字是 getC(N,M) 的呼叫次數
M = 0 M = 1 M = 2 M = 3
┌───┬───┬───┬───┐
│(停止)│(停止)│(停止)│(停止)│
N = 0 │ 6 │ 10 │ 5 │ 1 │
├───┼───┼───┼───┤ 把表格中的數字加起來
│(停止)│↖↑ │↖↑ │↖↑ │ 6 + 10 + 5 + 1 +
N = 1 │ 3 │ 6 │ 4 │ 1 │ 3 + 6 + 4 + 1 +
├───┼───┼───┼───┤ 1 + 3 + 3 + 1 +
│(停止)│↖↑ │↖↑ │↖↑ │ 1 + 2 + 1 +
N = 2 │ 1 │ 3 │ 3 │ 1 │ 1 + 1 +
├───┼───┼───┼───┤ 1 = 51
│ │↖↑ │↖↑ │↖↑ │
N = 3 │ │ 1 │ 2 │ 1 │
├───┼───┼───┼───┤
│ │ │↖↑ │↖↑ │
N = 4 │ │ │ 1 │ 1 │
├───┼───┼───┼───┤
│ │ │ │↖↑ │
N = 5 │ │ │ │ 1 │
├───┼───┼───┼───┤
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.120.32.135
※ 編輯: lgen7604 來自: 122.120.32.135 (05/15 19:03)