[理工] 102 交大 资工 资演 对答案
楼主: ken52011219 (呱) 2016-12-14 14:47:29
小弟有先检讨了一下才po上来
![]()
2.F少一条连至E
![]()
![]()
![]()
![]()
![]()
![]()
12. O((V+E)α(V)) , O(Eα(V))
14. 15
![]()
18.
０ 91/32 #
╱╲
１ 2/2 59/32
╱╲
２ 3/4 35/32
╱╲
３ 4/8 19/32
╱╲
４ 4/16 11/32
╱╲
５ 5/32 6/32
谢谢大家
2.F少一条连至E
12. O((V+E)α(V)) , O(Eα(V))
14. 15
18.
０ 91/32 #
╱╲
１ 2/2 59/32
╱╲
２ 3/4 35/32
╱╲
３ 4/8 19/32
╱╲
４ 4/16 11/32
╱╲
５ 5/32 6/32
谢谢大家
作者: beargg0305 (bear) 2016-12-14 16:19:00
第12题的加速![]()
" target="_blank" rel="nofollow">
![]()
![]()
" target="_blank" rel="nofollow">
![]()
我写的第2题
" target="_blank" rel="nofollow">
" target="_blank" rel="nofollow">我写的第2题楼主: ken52011219 (呱) 2016-12-14 19:01:00
我少画一条 感谢
作者: moooner (moooner) 2016-12-14 21:17:00
14题第一个答案是算x和y之间的距离哦～
作者: beargg0305 (bear) 2016-12-14 21:28:00
问一下最后一题 是要求单一个node 还是 6个node加起来？
作者: yupog2003 (屁股) 2016-12-14 22:04:00
max of w[i]*(1/2)^d[i] is minimized感觉不用加起来？
作者: beargg0305 (bear) 2016-12-14 22:04:00
因为我看题目问说 要求最小的最大值如果是霍夫曼的话感觉不会这样问吧？不过这题我也不会就是了@@
作者: yupog2003 (屁股) 2016-12-14 22:07:00
我的理解是每个tree都有一个max of w[i]*(1/2)^d[i]值找一个tree让这个值变成最小而这个值是由所有node之中w[i]*(1/2)^d[i]的最大值决定不知道我的英文这样理解有没有错XD我建出来的tree也是把2,3放第二层，4,4,5,6放第三层算出来max值是4/3，也不知道对不对阿要设计greedy算法那个我也不会就是了打错，max值是3/4
作者: aa06697 (todo se andarà) 2016-12-15 01:01:00
印象中第二题引线二元树是head node指向A喔
作者: hut326521 (yuyu) 2016-12-15 01:23:00
个人觉得ken大想法是对的 如果只是要让那六个leaves的weight跟depth算出来的最大值最小化的话 一直弄出degree为1的节点把leaves的depth弄到无限大就无解了...若是以这方向下去解 应该是要让整棵树里面最大的那个值（root）最小化 我画出来的树是这样 http://i.imgur.com/8vPCRqe.jpg![]()
" target="_blank" rel="nofollow">
![]()
思考方向是利用huffman 把权重越高的node放在越下面建出来的91/32为最小 也符合第二题的greedy个人想法啦QQ 觉得题目没写清楚的可能比较大忘了说我在说最后一题
" target="_blank" rel="nofollow">思考方向是利用huffman 把权重越高的node放在越下面建出来的91/32为最小 也符合第二题的greedy个人想法啦QQ 觉得题目没写清楚的可能比较大忘了说我在说最后一题作者: yupog2003 (屁股) 2016-12-15 07:08:00
这样讲我也觉得hut大和ken大对题目的理解才是对的了我没考虑到internal node的weight，回去重算XD希望大家都有看到最后不要被我上面的误导
作者: yellow60127 (nickyellow) 2016-12-16 18:38:00
" target="_blank" rel="nofollow"> 第18题怪怪的，如果树这样会有更小值欸作者: hut326521 (yuyu) 2016-12-16 18:55:00
91/32比47/16小吧QQ