Re: [理工] [DS]103 台大资工 对答案+问题

楼主: hyc1227   2015-01-31 22:34:06
※ 引述《winnie48 (winnie)》之铭言:
: 先附上题目连结:
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103424.pdf
: 就快要考试了,却还是都找不到这份的相关讨论,所以就po上自己写的和大家讨论!不过
: 这年的感觉有点难,有些不会的题目希望大家能给点提示~有错误的欢迎指正!
: 不会写的题目有:
: 1(b) 这感觉蛮基本...、3(c)、4
: 谢谢!大家加油!
: http://i.imgur.com/gPRLRxT.jpg
: http://i.imgur.com/VfrkNFE.jpg
: http://i.imgur.com/d56ynn5.jpg
这份的第4题
有看到说用topologic sort + DP 是要怎么做啊
另外第5题的(a)
要怎么判断 我只想到画图法 怎么用算法表示
感谢
这张真的好难...
作者: A4P8T6X9 (残废的名侦探)   2015-02-01 00:16:00
5-a 克拉马公式加上ㄧ些条件应该可以
作者: dslin (Magic)   2015-02-01 01:38:00
这不是A大吗?有神快拜!到底怎么考到70几分的^^
作者: galapous (墨)   2015-02-01 09:16:00
先将DAG topological sort 这课本应该有,最佳解结构我是设三个变量 一个纪录点的次序一个thin数一个thick数
作者: winnie48 (winnie)   2015-02-01 17:22:00
不好意思我第四题还是不太会!对DP不太熟…能不能请g大再解释详细一点?
作者: galapous (墨)   2015-02-01 18:25:00
走到第k点的x个thin边y个thick边的值等于第1~第k-1点thick边x-1thin边y然后有thick边到k点跟第1~第k-1点x个thick边y-1个thin边有thin边到k点中取最小疴 我好雷 打错好多..应该看得懂吧
作者: winnie48 (winnie)   2015-02-01 20:30:00
还是不太懂QAQ 好像懂一点,不过都选最小值怎么保证粗细边个数呢? 谢谢了!
作者: galapous (墨)   2015-02-01 20:37:00
所以全部粗细个数都要做出来~假如要求第三个点的3个thick3个thin走法那前面点3个thick3个thin以下的都要先建好恩,不过我叙述的算法应该可以再修正,有些计算应该是不必要的,比如检查2thick1thin时前两个点可以不用纳入
作者: victor801120 (说好要11点睡的)   2015-02-01 23:09:00
想问g大是课本的哪一题呢?请问你是用第三版的吗?@@
作者: galapous (墨)   2015-02-02 00:01:00
我不知道有没有在课本里耶..课本放在老家= =不过第五题好像有在课本里,我战友有翻到不知道不是全部小题都有就是了
作者: victor801120 (说好要11点睡的)   2015-02-02 07:53:00
好噢,感谢你!

Links booklink

Contact Us: admin [ a t ] ucptt.com