[理工] [資結][分享] C(n,k) 遞迴函數 呼叫次數
考慮以下計算二項式係數(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 ; -----(1)
T(n-1, k) + T(n-1, k-1) + 1 , otherwise. -----(2)
以下提供一種方法求出 T(n,k) 的 closed form。
方法為把 T(n,k) 的遞迴關係(2)與初始條件(1)調整到與 C(n,k) 的相同。
C(n,k) 的初始條件與遞迴關係如下：
C(n,k) =
1 , if n = k or k = 0 ; -----(3)
C(n-1, k) + B(n-1, k-1) , otherwise. -----(4)
首先把 T(n,k) 的遞迴關係調整到與 C(n,k) 相同。
令 U(n,k) = T(n,k) + 1 。
If n = k or k = 0, then
U(n,k) = 2. -----(5)
Otherwise,
U(n,k) = T(n-1, k) + 1 + T(n-1, k-1) + 1
= U(n-1, k) + U(n-1, k-1) . -----(6)
U(n,k) 的遞迴關係(6)已經與 C(n,k) 相同。
接者，在不改變遞迴關係的條件下，把 U(n,k) 的初始條件(5)調整到與 C(n,k) 相同。
令 V(n,k) = 1/2 * U(n,k)。
If n = k or k = 0, then
V(n,k) = 1. -----(7)
Otherwise,m
V(n,k) = 1/2 * U(n-1, k) + 1/2 * U(n-1, k-1)
= V(n-1, k) + V(n-1, k-1) . -----(8)
至此，V(n,k) 已與 C(n,k) 相同，因為兩個函數的遞迴關係與初始條件都一樣。
又 V(n,k) = 1/2 * U(n,k) = 1/2 * [T(n,k) + 1]
所以，計算 C(n,k) 的過程中，呼叫函數 C 的次數為
T(n,k) = 2 * C(n,k) - 1
或是寫成
T(n,k) = 2 * n!/[k!*(n-k)!] - 1
---
用類似的方法，也可以推出阿克曼(Ackermann)函數的呼叫次數，不過考試應該不會考:P
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.155.137
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1513789218.A.785.html
推
12/21 11:15,
6年前
, 1F
12/21 11:15, 1F
推
12/21 12:25,
6年前
, 2F
12/21 12:25, 2F
推
12/21 13:09,
6年前
, 3F
12/21 13:09, 3F
推
12/21 14:07,
6年前
, 4F
12/21 14:07, 4F
有考Ackermann函數的呼叫次數？
看起來只有考Ackermann函數的值而已。
而且掃描品質很差勁，A(4,1)印成A(1,1)。
推
12/21 16:31,
6年前
, 5F
12/21 16:31, 5F
→
12/21 16:32,
6年前
, 6F
12/21 16:32, 6F
幫補充: 由遞迴關係可知，recursion tree 是 strict binary tree
→
12/21 16:32,
6年前
, 7F
12/21 16:32, 7F
推F大
※ 編輯: JKLee (61.231.155.137), 12/22/2017 10:09:53