Re: [理工] [DS]103 台大資工 對答案+問題

看板Grad-ProbAsk作者時間11年前 (2015/01/31 22:34), 11年前編輯推噓10(10推 0噓 14→)
留言24則, 5人參與, 最新討論串2/3 (看更多)
※ 引述《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) 要怎麼判斷 我只想到畫圖法 怎麼用演算法表示 感謝 這張真的好難... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.57.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422714849.A.063.html
推
02/01 00:16, , 1F
5-a 克拉馬公式加上ㄧ些條件應該可以
02/01 00:16, 1F
推
02/01 01:38, , 2F
這不是A大嗎？有神快拜！到底怎麼考到70幾分的^^
02/01 01:38, 2F
推
02/01 09:16, , 3F
先將DAG topological sort 這課本應該有,最佳解結構我是
02/01 09:16, 3F
→
02/01 09:16, , 4F
設三個變數 一個紀錄點的次序一個thin數一個thick數
02/01 09:16, 4F
感謝以上回答 ※ 編輯: hyc1227 (140.123.57.203), 02/01/2015 15:38:31
推
02/01 17:22, , 5F
不好意思我第四題還是不太會！對DP不太熟…能不能請g大
02/01 17:22, 5F
→
02/01 17:22, , 6F
再解釋詳細一點？
02/01 17:22, 6F
推
02/01 18:25, , 7F
走到第k點的x個thin邊y個thick邊的值等於
02/01 18:25, 7F
→
02/01 18:25, , 8F
第1~第k-1點thick邊x-1thin邊y然後有thick邊到k點跟
02/01 18:25, 8F
→
02/01 18:27, , 9F
第1~第k-1點x個thick邊y-1個thin邊有thin邊到k點中
02/01 18:27, 9F
→
02/01 18:27, , 10F
取最小
02/01 18:27, 10F
→
02/01 18:27, , 11F
痾 我好雷 打錯好多..應該看得懂吧
02/01 18:27, 11F
推
02/01 20:30, , 12F
還是不太懂QAQ 好像懂一點，不過都選最小值怎麼保證粗
02/01 20:30, 12F
→
02/01 20:30, , 13F
細邊個數呢？ 謝謝了！
02/01 20:30, 13F
推
02/01 20:37, , 14F
所以全部粗細個數都要做出來~
02/01 20:37, 14F
→
02/01 20:39, , 15F
假如要求第三個點的3個thick3個thin走法那前面點3個thic
02/01 20:39, 15F
→
02/01 20:39, , 16F
k3個thin以下的都要先建好
02/01 20:39, 16F
講一下我理解的部分 由起點開始經過每個點都要記錄下到這個點 每種thick 和 thin邊數組合path之最小 然後一路到終點 終點要得到的thick 和 thin 邊數組合要是題目所求 這樣有沒有錯啊 ※ 編輯: hyc1227 (140.123.57.203), 02/01/2015 20:56:49
推
02/01 21:28, , 17F
恩,不過我敘述的演算法應該可以再修正,有些計算應該是不
02/01 21:28, 17F
→
02/01 21:28, , 18F
必要的,比如檢查2thick1thin時前兩個點可以不用納入
02/01 21:28, 18F
推
02/01 23:09, , 19F
想問g大是課本的哪一題呢？請問你是用第三版的嗎？@
02/01 23:09, 19F
→
02/01 23:09, , 20F
@
02/01 23:09, 20F
→
02/02 00:01, , 21F
我不知道有沒有在課本裡耶..課本放在老家= =
02/02 00:01, 21F
→
02/02 00:03, , 22F
不過第五題好像有在課本裡,我戰友有翻到
02/02 00:03, 22F
→
02/02 00:03, , 23F
不知道不是全部小題都有就是了
02/02 00:03, 23F
推
02/02 07:53, , 24F
好噢，感謝你！
02/02 07:53, 24F
‣ 更多 hyc1227 的文章
文章代碼(AID): #1KpEVX1Z (Grad-ProbAsk)
‣ 更多 hyc1227 的文章
文章代碼(AID): #1KpEVX1Z (Grad-ProbAsk)