Re: [理工] 交大 101 資演

[kather (Kather)]

※ 引述《olderbrother (大蜘蛛)》之銘言：
: 題目
: http://www.lib.nctu.edu.tw/attach/download/id-1532/
: 問題.. 有點多
: 爬文找不到，自己想不通..
好不容易打完 沒有儲存就關掉了 哭哭Q_Q
也有一些不會的，請神人補充

: 5. (13)B (14)C (15)C  請問這些複雜度是怎麼求出來的？
(13)
結構如下
node->node->node-> ... ->node
每個node有m/2個元素
假設有y個node
且 y * m/2 = n (總個數)

首先要找到x是在哪個node裡面
link-list你只能一個一個找看x值落在哪邊就是哪個node
=>O(y) = O(n/m)

找到在哪個node之後
因為他是排序過的
我們可以用二分法找值

看中間的大於等於還是小於x
就決定對左邊還是右邊繼續找找或是return
=>O(log(m/2))=O(logm)
共O(n/m + logm)

(14)
現在要插入x到此結構中
首先一樣先找該插入哪個node
=>O(n/m)

再來因為他是array,你插入值之後還要整理
(例如插入0,那麼1,2,3,4...m都要往後位移一格)
=>O(m/2)
共O(m+n/m)

(15)
同上
刪除也要整理
O(m+n/m)

: 14. (40)A (41)E (42)B 一樣，這些複雜度是怎麼求出來的？
(40)
先排序
=>O(nlogn)
兩兩相減找最小值
=>O(n)
共O(nlogn)

(41)
掃過整條,找最大跟最小值
共O(n)

(42)
一樣用二分法找值
但是多一道程序
每次找值都把該值與目標值相減,若比先前減出來的結果還小,儲存該值與結果
該值大於小於或等於目標值
則往左邊list或右邊list或直接return
如此一來做完後
共O(logn)


: 16. (46)C (47)B (48)B 這些答案不知道怎麼出來的 @@
題目說最短路徑中相距最長的兩個點為optmal(這兩點要能相連)
(46)
單源最短路徑
Dijstra=>greedy=>C

(47)
用floyd-warshal推出來應該是B

(48)
1到4已經是2了
就算繞路走最好也只會是1+1
選2即可
不必再用f-w推..

: 17. (49)B (50)E (51)E N=10 就湊不出答案了@@  不知道這答案怎麼出來的
不知道原理是甚麼,但是列表湊數字可以找到兩題的答案
請神人補充...
(49)
a=5 , Bino(a,3)=10
b=1 , Bino(b,2)=0
c=0 , Bino(c,1)=0
相加=10
a>b>c>=0
選B:a+b=6

(50)
a=5 , 10
b=4 , 6
c=2 , 2
相加=18
a>b>c>=0
選E:b=4

(51)
觀察下來E應該是錯的,但是不知道原理


: 18. (52)D 這個 mystery 是 Prim 嘛？
:     (53)A 這樣換的話 會變成 Dijkstra 嘛？
:     (54)E 如果他是 Prim 的話 應該是 O(n^2) 那 O(n^2 + (m+n)) 是？
(52)
整份code看下來是Prim的演算法

(53)
code變成
v=起始點s
對於v的每個鄰居點w
        若w的weight > v的weight+v與w的距離
                把w的weight更新成 v的weight+v與w的距離
        把v標記起來
(由於v一開始就是起始點s , v的weight即是v與起始點的距離)

然後再找距離最小且沒有標記的點當v繼續做
直到全部的v都標記為止

這樣會找到全部的點跟起始點s的距離

(54)
題目應該是要算沒改的那份code
因為他要求精確的值,我們就去追code

第一個for迴圈
=>n次

看while
        while內第一個for迴圈,當整個while做完,會把全部的邊都跑一遍
        =>m次
        while內第二個for迴圈,這個迴圈跑n次,當整個while(while也n次)做完
        =>n^2次

共O(n^2+n+m)





: 19. (55)E (56)C (57)D 這些答案不知道怎麼出來的？
: 不好意思問題有點多，麻煩大家了 <(_ _)>
看無= =
請神人補充...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.237.41.72
※ 編輯: kather          來自: 36.237.41.72         (02/11 00:49)
推 h56999:55，1講TSP,2講漢米爾頓path,3,HC
→ h56999:甘我腦了，我看錯題
→ h56999:sorry,等其它人解
推 jordanforme:I:找degree不超過2的生成樹,是NP-C
→ jordanforme:II:應該就是Hamilton　III:ham改成點最多經過一次
推 jordanforme:修正一下II,III都是類似ham而已
→ h56999:樓上洪捷老師嗎
→ kiki86151:II我覺得是Ham path III則Ham cycle 知道這兩個題組就
→ kiki86151:好選了I應該是min degree tree NPhard問題 這份其他OK
→ kiki86151:但反而我覺得第一題怎麼像SWAP不是後序啊==
第一題是用後序找值後把兩個子node swap吧 兩者應該並不衝突
※ 編輯: kather          來自: 36.237.36.253        (02/11 12:37)
推 jordanforme:第1題感覺是陷阱 是問怎麼traverse
推 olderbrother:太感謝了 ~~~ <(_ _)>
推 olderbrother:看了快兩小時  終於瞭解這些題目在做什麼了 <(_ _)>
推 ssssIssss: 非常感謝！