[理工] 離散 7-5 Huffman algo

看板Grad-ProbAsk作者時間7年前 (2018/10/12 15:32), 編輯推噓2(2推 0噓 15→)
留言17則, 3人參與, 7年前最新討論串1/1
https://i.imgur.com/98ft7IF.jpg
https://i.imgur.com/aIfwLfC.jpg
這題(a)的Huffman tree不知道是不是唯一 因為我畫出來的跟答案不一樣 不過總bit數都是10 不知道哪裡想錯了 麻煩各位一下 感恩 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.14.186 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539329549.A.1C6.html
推
10/12 16:08, 7年前 , 1F
兩個都對，Huffman答案可能不唯一，所以一般都會採stable
10/12 16:08, 1F
→
10/12 16:08, 7年前 , 2F
的方法，就是遇到值一樣的node會擺前面
10/12 16:08, 2F
→
10/12 16:08, 7年前 , 3F
10/12 16:08, 3F
→
10/12 16:09, 7年前 , 4F
算出來成本都會一樣
10/12 16:09, 4F
→
10/12 16:28, 7年前 , 5F
所以課本答案採用的是stable的作法?
10/12 16:28, 5F
→
10/12 16:32, 7年前 , 6F
是的，老師上課也有說用stable比較好答案會跟出題老師想
10/12 16:32, 6F
→
10/12 16:32, 7年前 , 7F
的一樣
10/12 16:32, 7F
→
10/12 16:41, 7年前 , 8F
好哦 感謝你
10/12 16:41, 8F
→
10/12 23:49, 7年前 , 9F
話說我看到洪兔都放後面XD 實在不知道哪個比較stable
10/12 23:49, 9F
推
10/13 00:51, 7年前 , 10F
我記得洪逸沒有特別講stable子嘉才有強調，stable應該是
10/13 00:51, 10F
→
10/13 00:51, 7年前 , 11F
放前面沒錯，sort的stable也是放前面
10/13 00:51, 11F
→
10/13 00:51, 7年前 , 12F
實作上應該要看用什麼DS，如果用min heap，好像可能會uns
10/13 00:51, 12F
→
10/13 00:51, 7年前 , 13F
table
10/13 00:51, 13F
→
10/13 01:21, 7年前 , 14F
s大是說，後面可能stable嗎？
10/13 01:21, 14F
→
10/13 01:51, 7年前 , 15F
你說最後一句嗎？實作會不會stable是看用什麼資料結構決
10/13 01:51, 15F
→
10/13 01:51, 7年前 , 16F
定，一次要刪兩個min可能會用min heap，如果用heap應該
10/13 01:51, 16F
→
10/13 01:51, 7年前 , 17F
有可能不stable，就是原本在前面的跑到後面去
10/13 01:51, 17F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1Rm4uD76 (Grad-ProbAsk)