作者painechaos (老趙)
看板Grad-ProbAsk
標題[理工] 106交大資演 對答案與討論
時間Wed Jan 17 17:43:56 2018
版上有關106交大的文章蠻少的@@ 所以直接po上來跪求指教
http://i.imgur.com/3z5eu4h.jpg
http://i.imgur.com/WAvH7QW.jpg
http://i.imgur.com/bDgqZqI.jpg
http://i.imgur.com/TYegNa1.jpg
http://i.imgur.com/srd34BN.jpg
http://i.imgur.com/9pREQuJ.jpg
http://i.imgur.com/x4OG9cT.jpg
http://i.imgur.com/LO7lcCj.jpg
http://i.imgur.com/DSPXwXH.jpg
http://i.imgur.com/ysnD99S.jpg
比較有疑惑的是第1、3、11、15題
1.一開始我是用課本定義的pi去做再轉換為p，做完後看了題目的定義跟印象中的不太相同，爬文後發現定義有改，但用題目的定義去操作還是怪怪的
3.看完程式碼，我的想法是第一輪q=n1開始往後比較，n1的value=8可以被2整除且後面的value皆小於8，所以一直swap直到8跑到n4;第二輪q從n2比較，最後得到3 2 7 8 ，這樣的想法正確嗎？
10.這題我自認在考場時也不會寫，所以直接放棄...
11.第一眼看到"greedy"和"2-way tree"，腦海中浮現的想法是Huffman algo，但看到optimal merge tree就不懂要的是怎樣子的tree
15.看到spanning tree就想到Krustal's algo和Prim algo，之後決定採用Krustal，接著令red edge weight=0,blue edge weight =1的想法下去做，請問這樣子可行嗎？
希望大家不吝指教@@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.240.137
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1516182239.A.CEF.html
1F：→ aggress5566: 1應該就很平常的KMP吧？ 01/17 18:03
2F：→ aggress5566: 10 應該是randomized algorithm 我也還沒看QQ 01/17 18:03
3F：→ aggress5566: 11應該是output整顆Tree 01/17 18:03
4F：→ aggress5566: 15用greedy應該沒問題 01/17 18:03
5F：推 a1596482: 1. 條件式還有一個Pi+1=/=Pj+1，應該只剩f(6)=3，其他 01/17 18:50
6F：→ a1596482: 為-1 01/17 18:50
7F：推 a1596482: 9. 是不是只有extract-min是logn ，其他都是1？ 01/17 18:52
8F：→ aggress5566: 那不是本來就是定義嗎 囧 01/17 19:03
9F：推 howard31622: 第十題我看了是哭笑不得 01/17 19:53
10F：→ howard31622: 乾...我沒有被很熟那段 01/17 19:53
11F：→ howard31622: 不過這題真的是送分題 01/17 19:53
12F：→ howard31622: 你沒有把洪逸的講義看熟喔 01/17 19:53
13F：→ howard31622: 雖然多希望考這種 01/17 19:53
14F：→ howard31622: 因為我不用擔心我選擇題寫不完 01/17 19:53
15F：→ howard31622: 而且這個分數一定拿得到不少 01/17 19:53
16F：→ howard31622: 還有第九題你寫錯了 01/17 19:54
17F：→ howard31622: 那個筆記有 01/17 19:54
18F：推 FRAXIS: 15題應該可以在 O(|E|)時間內解 01/17 20:52
19F：→ aggress5566: 其實應該是看熟才知道不能用他筆記上的證吧XD 01/17 21:17
20F：推 winiel559: 15不需要sort，一個個檢查顏色正不正確就好了 01/17 21:37
21F：→ painechaos: 回agg大:我是後來對答案時發現有討論這題，對於f(i)=t 01/18 00:02
22F：→ painechaos: he largest i<j 這段的意思有點難以理解 01/18 00:02
23F：→ painechaos: 請問第11題你會怎麼寫呢，有點摸不著頭緒該如何下筆 01/18 00:02
24F：→ painechaos: 第15這樣分析還ok囉? 01/18 00:02
25F：→ painechaos: a大:請問對於f(i)=the largest i<j...這段的你是如何 01/18 00:12
26F：→ painechaos: 解讀的? 01/18 00:12
29F：→ painechaos: 剛剛發現union寫錯了,extract-min我要再找找，謝謝你 01/18 00:12
30F：→ painechaos: 的提點 01/18 00:12
31F：→ painechaos: h大:這題我只有看個印象，沒有認真去背它@@ 01/18 00:21
32F：→ painechaos: 剛剛找了一下，應該是這個推導 01/18 00:21
35F：→ painechaos: 那時候看完覺得實在沒把握在時間緊迫的情況下寫出來， 01/18 00:21
36F：→ painechaos: 所以就投注心力在其他基本題上了xD 01/18 00:21
37F：→ painechaos: F大 w大:謝謝你們，我再思考看看如何表達 01/18 00:24
38F：→ aggress5566: 你說failure function嗎 我就用KMP下去做而已 01/18 00:33
39F：→ aggress5566: 然後你貼的筆記 Hmm 我覺得出題教授應該是看了這個 01/18 00:34
40F：→ aggress5566: 出了這題 XD 01/18 00:34
41F：推 winiel559: 想了一下15好像還是要sort 01/18 08:47
42F：→ a1596482: 1. 我覺得應該是f(j)才對 01/18 08:58
43F：推 yaya517: quick sort avg. prove跟你一樣..看到覺得不會 翻筆記看 01/18 09:12
44F：→ yaya517: 到一樣的東西 覺得自己考試時應該還是寫不出來XD 01/18 09:12
45F：推 FRAXIS: 15 就算要排序 因為只有兩種類型 counting sort 就可以了 01/18 11:26
46F：推 sarsman: 1我也覺得定義應該是f(j)，i都是input了找什麼largest啦X 01/18 14:58
47F：→ sarsman: D 01/18 14:58
48F：推 sarsman: 11，將m個sorted list建成m個只有一顆node的tree，定義no 01/18 16:00
49F：→ sarsman: de weight為element個數 01/18 16:00
50F：推 sarsman: 挑兩個weight最小的tree（令為T1、T2）；再新增一個一顆n 01/18 16:05
51F：→ sarsman: ode的tree （令為T），將T1、T2接在T的左右子樹 01/18 16:05
52F：→ sarsman: T的root weight為T1跟T2的weight sum，重複到剩下一棵tre 01/18 16:07
53F：→ sarsman: e就是輸出 01/18 16:08
54F：→ painechaos: agg大:如果因為這樣多拿了點分數，那真是賺到了xD 01/18 17:54
55F：→ painechaos: y大:我覺得還是穩穩地把握其他基本分比較實在，這題就 01/18 17:54
56F：→ painechaos: 給高手得分吧QQ 01/18 17:54
57F：→ painechaos: w大、F大:演算法設計的部分我比較不熟要再多思考，先 01/18 17:56
58F：→ painechaos: 謝謝指教 01/18 17:56
59F：→ painechaos: 謝謝s大的第11題，我了解node該怎麼定義了! 這是Huffm 01/18 18:00
60F：→ painechaos: an的應用吧？ 01/18 18:00
61F：推 leoone: 15題就先排序 把set依序由小排到大在 兩兩做merge 01/19 20:49
62F：→ leoone: 11題打錯 01/19 20:49
63F：→ leoone: 15題 我是把red edge設0 blue edge設1做dijkstra 01/19 20:50
64F：→ leoone: 不對kruskal打錯 01/19 20:51
65F：→ leoone: 一直打錯XDD 01/19 20:52
66F：推 tinhanho: 1很奇怪 但f(8)應該是0吧?? 12/16 00:12
67F：→ tinhanho: 直接用KMP的failure func. 看的話 12/16 00:13