(b)
書上解答直接列出來的 不清楚如何來
我先從(d)開始解
我的想法是 T(n)=T(n-1)+T(n-2)+1 //T(n) 是總node數
T(1)=T(2)=1
解出來 T(n) 等於 2Fn-1
且 T(n)=L+I //L是 leaf I是 internal node
L=I+1 得 T(n)=2I+1
得出 (b)和(C)的答案
我想問的是 如何直接做(b)小題
麻煩老師解答了
Research Space for Linear Algebra & Discrete Mathematics
2 則留言:
可以畫個幾棵樹出來看看就會有感覺了,
嚴謹一點寫可以用數學歸納法證 l_n = F_n:
By inbuction on n,
l_1 = l_2 = 1, l_3 = l_1 + L_2, 設當 n<k 時皆成立,
i.e., l_(n-1) = F_(n-1), consider n=k:
l_k = l_(k-1) + l_(k-2) = F_(k-1) + F_(k-2) = F_k
張貼留言