[理工] [資結][分享] C(n,k) 遞迴函數 呼叫次數

作者: JKLee (J.K.Lee)   2017-12-21 01:00:15
考慮以下計算二項式係數(binomial coefficient)的C程式碼:
int C(int n, int k)
{
if(n == k || k == 0 )
return 1;
else
return C(n-1, k) + C(n-1, k-1);
}
令 T(n,k) 為計算 C(n,k) 的過程中,呼叫函數 C 的次數。
則 T(n,k) =
1 , if n = k or k = 0 ;
作者: kobebset105 (小小小妹)   2017-12-21 11:15:00
感謝大大分享~
作者: twps6106 (雞場)   2017-12-21 12:25:00
感謝分享
作者: winiel559 (大漢天威)   2017-12-21 13:09:00
Pretty cool, thanks
作者: s89162504 (阿本)   2017-12-21 14:07:00
今年中山就考了 QQ
作者: FRAXIS (喔喔)   2017-12-21 16:31:00
其實我覺得不用想那麼複雜吧 因為 base case 只有 1所以 recursion tree 的 leaves 一定是 C(n, k) 個然後加上 internal node 有 C(n, k) - 1 個

Links booklink

Contact Us: admin [ a t ] ucptt.com