Re: [問題] 請問排列組合的遞迴呼叫次數計算
※ 引述《minimatsumi (sugar)》之銘言：
: 以下程式會算出 C(N, M)，即從 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); }
: 請問count值最後是多少
: (A) 5 (B) 15 (C) 51 (D) 63
: 我一直算出26耶~
: 有人答案給D
: 有人答案給C
: 所以答案到底是....?
M\N 0 1 2 3 4 5
0 １ １ １ １ １ １
↖ ↖ ↖ ↖ ↖
1 １ ← ３ ← ５ ← ７ ← ９ ← 11
↖ ↖ ↖ ↖ ↖
2 １ ← ３ ← ７ ← 13 ← 21 ← 31
↖ ↖ ↖ ↖ ↖
3 １ ← ３ ← ７ ← 15 ← 29 ← 51
這表是這樣來的:
首先 最左和最上是１這沒問題
其他的值則是它左上加上它左邊再加１
(因為 C(N,M) 呼叫了 C(N-1,M-1) 和 C(N-1,M)
再加上自己的一次)
因此答案是 51
如果這題問 C(5,5) 答案才會是 63 (再往下算兩行就知道了)
--
順帶一提, 這張表在 OEIS 有紀錄: http://oeis.org/A131247/table
http://oeis.org/A131248/table (這兩個互為轉置)
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.62
推
05/05 09:29, , 1F
05/05 09:29, 1F
推
05/05 23:47, , 2F
05/05 23:47, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：