[理工] 台大資工 109 資演 對答案+問問題
看板Grad-ProbAsk作者joywilliamjo (joywilliamjoy)時間4年前 (2021/01/18 10:54)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
如題
選擇題上來跟大家對對看
順便問問
1. 3
2. 4
3. 3
4. 14
5. 235
6. 1
7. 134
8. 1245
9. 1234
10. 4
11. a)
1. 將input兩兩分組，input = 偶數分成n/2組，input = 奇數則分成[n/2]+1組
2. 將這些兩兩一組先比出大小
3. 將每組大的和大的比，小的和小的比
4. 遞迴做step3
5. return (min,Max)
b)
(3n/2) - 2
12. 看不懂題目中第二句的敘述，估計是用dp做類似rod cutting
13.
14.
a)
b)
o
/ | \
o o o
/ | \ / | \ / | \
o o oo o oo o o
c) 用矛盾證法，如果說center不在T的diameter裡面的話，會違背題目對center的定義
(radius為T中的min，如果T的diameter長度一定會超過radius，那表示這條路徑中一定有一個點的長度會是
radius)
15. a)
不太確定題意，但應該是在說set cover
u = {1,2,3,4,5,6,7,8}
F1 = {1,2,3,4}
F2 = {5,6,7,8}
F3 = {1,3,4,5,6}
F4 = {1,7,8}
F5 = {2}
greedy: C = {F3, F4, F5}
optimal = {F1, F2}
b)
given a subset D{Fi~Fj}，可以在polynimal time(O(n))確定是否每個元素都在u中
----NP check
再來證NP-complete 應該用vertex cover去reduce但我不會QQ，可以硬寫但應
該拿不了分就不寫了而且我也沒有很確定REDUCE要怎麼做，還請大家提供意見QQ
大概是這樣，大家考試加油
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.253.17 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1610938443.A.BC2.html
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
