Re: [問題] 資料結構

[yauhh (喲)]

※ 引述《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)
推 Achen2211:了解了~感謝幫忙謝謝~
→ karcher:等比級數算法跟等差級數一樣 @@
→ yauhh:嗯...最後可不可以上梯形公式我已經不確定..好像是錯的.
→ yauhh:就當做是孔明之罠吧, XDDD 哈哈哈哈
→ Achen2211:那是部是我原本寫的對阿= =?
→ yauhh:這種一元多次真不會化約.
※ 編輯: yauhh           來自: 218.160.214.133      (06/02 21:55)
→ zerodevil:哈哈哈哈
→ zerodevil:原po只是沒加括號而已 他的算式是對的
推 VictorTom:沒化簡的那個看起來像複利公式口也....@_@"
※ 編輯: yauhh           來自: 218.160.214.133      (06/02 22:32)
→ yauhh:嗯,似乎真沒錯.. 不會化簡真是缺憾很多
→ VictorTom:的確是等比級數, 全還給數學老師了....Orz
→ VictorTom:插花問個問題, 以二元樹來說, 高度1, 是指一個節點, 還
→ VictorTom:是3個節點的狀態?? 以前考試好像是老師先公設好就行了@@
→ yauhh:喔對,聽過這種講法,是指起碼有一個直接子節點是高度1...