推 ggg12345: 這個式子有助於推估老鼠會的最下游終端點節數 10/01 18:49
推 KAOKAOKAO: 推 01/13 10:27
※ 引述《bbggorin (無心)》之銘言：
: 請教一個關於資料結構的問題
: 題目:假如有一個非空樹，其分支度為5，已知分支度為i的節點數有i個，其中 1 <= i <=5，
: 請問終端節點數總數是多少？
: 答案是==>41
: 請問是怎麼算出來的?
假設你已有一個終端節點數為 k 的樹,
現在對它加入一個分支度為 i 的節點在一個終端節點上,
它會吃掉一個終端結點, 然後再貢獻 i 個新的終端節點,
使得這個長大的樹終端節點數為 k + i - 1,
也就是每加一個分支度為 i 的點, 終端節點數就增加 i - 1,
而且跟節點加入的順序無關.
不失一般性, 我們把這個題目描述的樹的 root 前面再延伸一個 super root.
這個加上 super root 的樹, 其終端節點數和原本的樹應該是一樣的.
而這個新的樹的終端節點數應該是....
1 + (只有 super root 自己時, 終端節點數是 1)
1 * (1-1) +
2 * (2-1) +
3 * (3-1) +
4 * (4-1) +
5 * (5-1)
= 1 + 0 + 2 + 6 + 12 + 20
= 41
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.80.249
※ 文章網址: http://www.ptt.cc/bbs/CSSE/M.1409249952.A.55E.html