[理工] 106交大資演 對答案與討論

看板Grad-ProbAsk作者 (老趙)時間6年前 (2018/01/17 17:43), 編輯推噓12(12推 0噓 53→)
留言65則, 9人參與, 6年前最新討論串1/1
版上有關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://www.ptt.cc/bbs/Grad-ProbAsk/M.1516182239.A.CEF.html
→
01/17 18:03, 6年前 , 1F
1應該就很平常的KMP吧？
01/17 18:03, 1F
→
01/17 18:03, 6年前 , 2F
10 應該是randomized algorithm 我也還沒看QQ
01/17 18:03, 2F
→
01/17 18:03, 6年前 , 3F
11應該是output整顆Tree
01/17 18:03, 3F
→
01/17 18:03, 6年前 , 4F
15用greedy應該沒問題
01/17 18:03, 4F
推
01/17 18:50, 6年前 , 5F
1. 條件式還有一個Pi+1=/=Pj+1，應該只剩f(6)=3，其他
01/17 18:50, 5F
→
01/17 18:50, 6年前 , 6F
為-1
01/17 18:50, 6F
推
01/17 18:52, 6年前 , 7F
9. 是不是只有extract-min是logn ，其他都是1？
01/17 18:52, 7F
→
01/17 19:03, 6年前 , 8F
那不是本來就是定義嗎 囧
01/17 19:03, 8F
推
01/17 19:53, 6年前 , 9F
第十題我看了是哭笑不得
01/17 19:53, 9F
→
01/17 19:53, 6年前 , 10F
乾...我沒有被很熟那段
01/17 19:53, 10F
→
01/17 19:53, 6年前 , 11F
不過這題真的是送分題
01/17 19:53, 11F
→
01/17 19:53, 6年前 , 12F
你沒有把洪逸的講義看熟喔
01/17 19:53, 12F
→
01/17 19:53, 6年前 , 13F
雖然多希望考這種
01/17 19:53, 13F
→
01/17 19:53, 6年前 , 14F
因為我不用擔心我選擇題寫不完
01/17 19:53, 14F
→
01/17 19:53, 6年前 , 15F
而且這個分數一定拿得到不少
01/17 19:53, 15F
→
01/17 19:54, 6年前 , 16F
還有第九題你寫錯了
01/17 19:54, 16F
→
01/17 19:54, 6年前 , 17F
那個筆記有
01/17 19:54, 17F
推
01/17 20:52, 6年前 , 18F
15題應該可以在 O(|E|)時間內解
01/17 20:52, 18F
→
01/17 21:17, 6年前 , 19F
其實應該是看熟才知道不能用他筆記上的證吧XD
01/17 21:17, 19F
推
01/17 21:37, 6年前 , 20F
15不需要sort，一個個檢查顏色正不正確就好了
01/17 21:37, 20F
→
01/18 00:02, 6年前 , 21F
回agg大:我是後來對答案時發現有討論這題，對於f(i)=t
01/18 00:02, 21F
→
01/18 00:02, 6年前 , 22F
he largest i<j 這段的意思有點難以理解
01/18 00:02, 22F
→
01/18 00:02, 6年前 , 23F
請問第11題你會怎麼寫呢，有點摸不著頭緒該如何下筆
01/18 00:02, 23F
→
01/18 00:02, 6年前 , 24F
第15這樣分析還ok囉?
01/18 00:02, 24F
→
01/18 00:12, 6年前 , 25F
a大:請問對於f(i)=the largest i<j...這段的你是如何
01/18 00:12, 25F
→
01/18 00:12, 6年前 , 26F
解讀的?
01/18 00:12, 26F
→
01/18 00:12, 6年前 , 27F
01/18 00:12, 27F
→
01/18 00:12, 6年前 , 28F
01/18 00:12, 28F
→
01/18 00:12, 6年前 , 29F
剛剛發現union寫錯了,extract-min我要再找找，謝謝你
01/18 00:12, 29F
→
01/18 00:12, 6年前 , 30F
的提點
01/18 00:12, 30F
→
01/18 00:21, 6年前 , 31F
h大:這題我只有看個印象，沒有認真去背它@@
01/18 00:21, 31F
→
01/18 00:21, 6年前 , 32F
剛剛找了一下，應該是這個推導
01/18 00:21, 32F
→
01/18 00:21, 6年前 , 33F
01/18 00:21, 33F
→
01/18 00:21, 6年前 , 34F
01/18 00:21, 34F
→
01/18 00:21, 6年前 , 35F
那時候看完覺得實在沒把握在時間緊迫的情況下寫出來，
01/18 00:21, 35F
→
01/18 00:21, 6年前 , 36F
所以就投注心力在其他基本題上了xD
01/18 00:21, 36F
→
01/18 00:24, 6年前 , 37F
F大 w大:謝謝你們，我再思考看看如何表達
01/18 00:24, 37F
→
01/18 00:33, 6年前 , 38F
你說failure function嗎 我就用KMP下去做而已
01/18 00:33, 38F
→
01/18 00:34, 6年前 , 39F
然後你貼的筆記 Hmm 我覺得出題教授應該是看了這個
01/18 00:34, 39F
→
01/18 00:34, 6年前 , 40F
出了這題 XD
01/18 00:34, 40F
推
01/18 08:47, 6年前 , 41F
想了一下15好像還是要sort
01/18 08:47, 41F
→
01/18 08:58, 6年前 , 42F
1. 我覺得應該是f(j)才對
01/18 08:58, 42F
推
01/18 09:12, 6年前 , 43F
quick sort avg. prove跟你一樣..看到覺得不會 翻筆記看
01/18 09:12, 43F
→
01/18 09:12, 6年前 , 44F
到一樣的東西 覺得自己考試時應該還是寫不出來XD
01/18 09:12, 44F
推
01/18 11:26, 6年前 , 45F
15 就算要排序 因為只有兩種類型 counting sort 就可以了
01/18 11:26, 45F
推
01/18 14:58, 6年前 , 46F
1我也覺得定義應該是f(j)，i都是input了找什麼largest啦X
01/18 14:58, 46F
→
01/18 14:58, 6年前 , 47F
D
01/18 14:58, 47F
推
01/18 16:00, 6年前 , 48F
11，將m個sorted list建成m個只有一顆node的tree，定義no
01/18 16:00, 48F
→
01/18 16:00, 6年前 , 49F
de weight為element個數
01/18 16:00, 49F
推
01/18 16:05, 6年前 , 50F
挑兩個weight最小的tree（令為T1、T2）；再新增一個一顆n
01/18 16:05, 50F
→
01/18 16:05, 6年前 , 51F
ode的tree （令為T），將T1、T2接在T的左右子樹
01/18 16:05, 51F
→
01/18 16:07, 6年前 , 52F
T的root weight為T1跟T2的weight sum，重複到剩下一棵tre
01/18 16:07, 52F
→
01/18 16:08, 6年前 , 53F
e就是輸出
01/18 16:08, 53F
→
01/18 17:54, 6年前 , 54F
agg大:如果因為這樣多拿了點分數，那真是賺到了xD
01/18 17:54, 54F
→
01/18 17:54, 6年前 , 55F
y大:我覺得還是穩穩地把握其他基本分比較實在，這題就
01/18 17:54, 55F
→
01/18 17:54, 6年前 , 56F
給高手得分吧QQ
01/18 17:54, 56F
→
01/18 17:56, 6年前 , 57F
w大、F大:演算法設計的部分我比較不熟要再多思考，先
01/18 17:56, 57F
→
01/18 17:56, 6年前 , 58F
謝謝指教
01/18 17:56, 58F
→
01/18 18:00, 6年前 , 59F
謝謝s大的第11題，我了解node該怎麼定義了! 這是Huffm
01/18 18:00, 59F
→
01/18 18:00, 6年前 , 60F
an的應用吧？
01/18 18:00, 60F
推
01/19 20:49, 6年前 , 61F
15題就先排序 把set依序由小排到大在 兩兩做merge
01/19 20:49, 61F
→
01/19 20:49, 6年前 , 62F
11題打錯
01/19 20:49, 62F
→
01/19 20:50, 6年前 , 63F
15題 我是把red edge設0 blue edge設1做dijkstra
01/19 20:50, 63F
→
01/19 20:51, 6年前 , 64F
不對kruskal打錯
01/19 20:51, 64F
→
01/19 20:52, 6年前 , 65F
一直打錯XDD
01/19 20:52, 65F
‣ 更多 painechaos 的文章
文章代碼(AID): #1QNnhVpl (Grad-ProbAsk)