[理工] 102 台大演算法

看板Grad-ProbAsk作者leosnake (尼歐)時間12年前 (2014/01/20 21:54)推噓0(0推 0噓 6→)

留言6則, 2人參與討論串1/1

http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102415.pdf 請問一下第三題(a) 如果n=2，也就是 binary tree ，可以用矛盾證明。但是n>2 時，命題就不一定成立了。考慮n=3的case, 假設T為 C={x,y} 的optimal decoding tree，則T會長這樣： root / \ x y 如此T並非full ternary tree(3-ary tree)。也就是說，當要壓縮的字元數量少於n時，optimal decoding tree T好像不會是 full n-ary tree. 以上小弟的想法是對或錯，請各位大大指教:) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.177.23 ※ 編輯: leosnake 來自: 61.228.177.23 (01/20 21:56) ※ 編輯: leosnake 來自: 61.228.177.23 (01/20 21:59) ※ 編輯: leosnake 來自: 61.228.177.23 (01/20 22:00)

→

kiki86151

01/21 01:34, , 1^F

01/21 01:34, 1^F

→

leosnake

01/21 07:09, , 2^F

01/21 07:09, 2^F

→

leosnake

01/21 07:11, , 3^F

01/21 07:11, 3^F