※ 引述《Achen2211 (阿辰)》之銘言：
: 一棵高度h的k元樹最多有多少個節點?我是算出(k^h)-1/k-1個節點~是對的嗎??
拆開來只思考任一樹樹根與直接子節點之間的關連,做數學歸納吧
1. 高度 1 的 k 元樹最多有 1 節點!
2. 考慮任一 k 元樹,樹根跟直接子節點的關係是:
令存在 m 個樹根,對任一樹根來說,最多 k 個直接子節點,
所以 m 個樹根的直接子節點最多共 m*k個.
歸納可得,高度 h 的 k 元樹最大節點數目為
maxCoN(h, k) = 1 + 1*k + 1*k*k + 1*k*k*k + ... + 1*k^(h-1)
= sigma_{i=1..h} (k^(i-1))
= (k^0 + k^(h-1)) * h / 2
= 1 + k * (k^0 + k^1 + k^2 + ... + k^(h-2))
= 1 + k * (1 + k * (1 + k * (1 + k * ( ... (1 + k)) ... ))
= ...
* 糟糕,我不會化約...
來檢查 (k^h) - 1/k - 1 是否等於 maxCoN(h, k)
1. 令 k = 1, maxCoN = sigma_{i=1..h} (1^(i-1)) = h,
(k^h)-1/k-1 = (1^h)-1/1-1 = 1-1-1 = -2
所以你算的 (k^h)-1/k-1 跟我的 maxCoN(h,k) 結果不同.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.214.133
※ 編輯: yauhh 來自: 218.160.214.133 (06/02 21:16)
推
06/02 21:20, , 1F
06/02 21:20, 1F
→
06/02 21:22, , 2F
06/02 21:22, 2F
→
06/02 21:22, , 3F
06/02 21:22, 3F
→
06/02 21:23, , 4F
06/02 21:23, 4F
→
06/02 21:27, , 5F
06/02 21:27, 5F
→
06/02 21:44, , 6F
06/02 21:44, 6F
※ 編輯: yauhh 來自: 218.160.214.133 (06/02 21:55)
→
06/02 21:51, , 7F
06/02 21:51, 7F
→
06/02 22:05, , 8F
06/02 22:05, 8F
推
06/02 22:28, , 9F
06/02 22:28, 9F
※ 編輯: yauhh 來自: 218.160.214.133 (06/02 22:32)
→
06/02 22:33, , 10F
06/02 22:33, 10F
→
06/02 22:42, , 11F
06/02 22:42, 11F
→
06/02 22:44, , 12F
06/02 22:44, 12F
→
06/02 22:45, , 13F
06/02 22:45, 13F
→
06/02 22:50, , 14F
06/02 22:50, 14F
討論串 (同標題文章)