› 看板 Grad-ProbAsk 關於我們 聯絡資訊
作者ahahahahah (Kaneshiro Takeshi)
看板Grad-ProbAsk
標題[理工] 台大105資演
時間Fri Jan 12 19:31:04 2018
1) 時間複雜度 發現跟成大某題一樣類型 就直接問這題好了 https://i.imgur.com/iuZWgA7.jpg https://i.imgur.com/X7ryees.jpg 解答看不太懂 他畫的遞迴樹是n^2>M的情況嗎？ 為什麼第二層是16c 而不是16*c/2=8c 那為什麼n^2<=M的情況就不用管了？ 2) https://i.imgur.com/SdZScFH.jpg (c)小題 畫一個最少結點的AVL Tree Ok! 但之後要填入紅黑樹就不太明白了 所以就是隨便畫 只要符合就好了嗎？ 例如 https://i.imgur.com/xknYcCW.jpg 還是有規則嗎？ 3) https://i.imgur.com/ushGfR4.jpg https://i.imgur.com/q8dZgAy.jpg (a)這題應該是要寫計算過程吧？ 用看的應該拿不到分數？ 解法應該是用Floyd-Warshall做4次 可是9*9矩陣好像有點大XD 請問有別的作法嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.105.145 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1515756667.A.6AB.html ※ 編輯: ahahahahah (49.158.105.145), 01/12/2018 19:33:17 ※ 編輯: ahahahahah (49.158.105.145), 01/12/2018 19:35:12
推 PunchShadow: 2.c 之前版上有人解不同的答案，我也還在困惑01/12 19:59
→ PunchShadow: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.01/12 20:00
404 not found XDD
→ PunchShadow: 4.c 就只要滿足Smallest height 3 AVL tree即可01/12 20:01
不是還要畫紅黑樹
→ PunchShadow: 5.a 我是用Dijkstra 先解出最短path，再帶入限制條件01/12 20:03
→ PunchShadow: 把(E,G)、(G,H)換成(E,H)01/12 20:04
→ PunchShadow: 5.a 說錯，替換結果應該是(A,D)換(A,B)+(B,D)01/12 20:21
※ 編輯: ahahahahah (49.158.105.145), 01/12/2018 21:03:26
推 a1596482: 5.a 用bellman 做4次？ 01/12 21:57
推 a1596482: 成大複雜度那題我算O(n^4/M) 01/12 22:00
→ ahahahahah: 對是Bellman我搞錯了XDD 01/12 23:36
→ sarsman: 2c 確保root到所有leaf經過的黑node數一樣、沒有連續兩顆 01/12 23:37
→ sarsman: 紅node相連就行 01/12 23:37
→ sarsman: 1 因為他分割成16個子問題，每個子問題需時theta(1)，加 01/13 00:00
→ sarsman: 總就是16c 01/13 00:00
→ ahahahahah: 謝謝 我研究一下 01/13 14:06
推 PunchShadow: 對 就是有那個性質的紅黑樹即可 01/13 15:54
→ PunchShadow: 網址被截掉了QQ 01/13 15:54
→ PunchShadow: https://www.ptt.cc/bbs/Grad-ProbAsk/ 01/13 15:54
→ PunchShadow: M.1479362612.A.90A.html 01/13 15:55
→ PunchShadow: 上面兩行麻煩加在一起xDD 01/13 15:55