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