※ 引述《lovefo (lovefo)》之銘言：
: ※ 引述《fj90406 (阿亮)》之銘言：
: : 先問個基本問題...
: : 考試的時候 如果題目沒有特別說
: : 那麼 root 層算是高度1還是0阿?
: : http://tinyurl.com/ydn6zdt
: : 第6題的第(C)小題
: 借問一下
: 第6題的第(a).(b)小題
: 要怎麼解???
: : 題意是說
: : 假設有一個三元樹是120個邊
: : 那麼他的高度至少是多少?
: : 小弟不管怎算都是5層(如果root層是1的話)
: : 但是黃子X 的 題庫解答本 寫4...
: : 請高手算算看多少
6.已知條件graph是連通，邊數:120
(a)求最多點數?
sol:當此圖是tree時(即邊數=點數-1)，graph會有最多點數
所以最多點數=121
(b)求最少點數?
sol:當邊數達到complete grah時，邊數最多，點數最少
n
所以 C ≦ 120
2
=> n(n-1) ≦ 240
=> n^2 - n - 240 ≦ 0
=> n ≦ 16，-15(點數不可能是負的)
因此最少點數=16
(c)若G是三元樹，求G的最小樹高?
sol:(1)[DM版本] (root的level是0，ref.Rosen寫的離散)
tree的邊數=點數-1 => 點數=121
求最小樹高，即代表此tree是fully ternary tree
2 3 h h+1
令樹高為h，1 + 3 + 3 + 3 + ... + 3 = (3 -1)/2 = 121
h+1
=> 3 -1 = 242
h+1
=> 3 = 243
=> h+1 = 5
=> h = 4
所以最小樹高是4
(2)[DS版本] (root的level是1，ref.Horowitz寫的資結)
tree的邊數=點數-1 => 點數=121
求最小樹高，即代表此tree是complete tree
2 h-1
令樹高為h => 1 + 3 + 3 + ... + 3 ≧ 121
h
=> 3 - 1 ≧ 242
=> h ≧ 5
所以最小樹高為5
因為這份考卷是離散，寫(1)的答案即可，或依照題目定義來做答
如果此小題配分很重，那就兩個都寫
--
「不懂不羞恥，不學才內疚」
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.36.239
※ 編輯: crazykk 來自: 60.244.36.239 (04/03 09:30)
※ 編輯: crazykk 來自: 60.244.36.239 (04/03 09:34)