如題
選擇題上來跟大家對對看
順便問問
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?