[理工] 成大 資演1

看板Grad-ProbAsk作者 (一顆星5566)時間9年前 (2017/01/08 13:37), 編輯推噓14(14推 0噓 28→)
留言42則, 6人參與, 最新討論串1/1
給定一圖和圖中每個點的鄰居 給任兩點求共同鄰居的個數 http://i.imgur.com/2nowkWg.jpg
直覺就是把nodeA的鄰居表的每個點都去檢查是不是在nodeB中 但這題給15分耶 不太懂這題到底想問什麼 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.242.158 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483853871.A.F2C.html
推
01/08 13:46, , 1F
就是叫我們寫一個演算法想辦法讓複雜度低一點吧，應該
01/08 13:46, 1F
→
01/08 13:46, , 2F
有很多種做法,我會把每一個neighbor的編號除以總node數
01/08 13:46, 2F
→
01/08 13:47, , 3F
這樣得到的餘數一定就是node編號，再依序放到bucket裡面
01/08 13:47, 3F
→
01/08 13:47, , 4F
bucket個數就是編號個數（有點像bucket sort), 每丟一個
01/08 13:47, 4F
→
01/08 13:47, , 5F
就記錄一次bukcet內點的個數，最後如果A和B都丟完了，如
01/08 13:47, 5F
→
01/08 13:48, , 6F
,再去check每個bucket內count的數字，如果是2的話那就是
01/08 13:48, 6F
→
01/08 13:48, , 7F
共同neighbor,這樣複雜度應該O(n)就行了
01/08 13:48, 7F
→
01/08 14:28, , 8F
感謝你
01/08 14:28, 8F
→
01/08 14:30, , 9F
順便問一下第二題的avl 是3 1 0 1 嗎？
01/08 14:30, 9F
推
01/08 14:35, , 10F
是的，我剛剛畫一下也是3,1,0,1
01/08 14:35, 10F
→
01/08 14:40, , 11F
水喔 謝啦
01/08 14:40, 11F
→
01/08 16:10, , 12F
再順便一下第三題的smmh4個小題分別是 96 18 25 interv
01/08 16:10, 12F
→
01/08 16:10, , 13F
al heap,min-max heap
01/08 16:10, 13F
推
01/08 16:38, , 14F
前3小題跟樓上一樣,第四題我寫Deap/min-max heap
01/08 16:38, 14F
→
01/08 16:39, , 15F
第七題沒甚麼頭緒中...是求最長路徑嗎?
01/08 16:39, 15F
推
01/08 16:41, , 16F
我算96,18,40欸，前面兩個應該沒問題，delete-max刪掉25
01/08 16:41, 16F
→
01/08 16:42, , 17F
說錯，刪掉96後，把25拿上來，再去比較40和50誰比較大，
01/08 16:42, 17F
→
01/08 16:43, , 18F
50>40,所以50搬到T[3],T[5]是40不是嗎
01/08 16:43, 18F
→
01/08 16:43, , 19F
然後T[7]是25
01/08 16:43, 19F
推
01/08 16:45, , 20F
又打錯了，T[6]才是25,忘記左右交換了
01/08 16:45, 20F
→
01/08 16:52, , 21F
應該是刪掉96後,拿該點右子點/左兄弟右子點跟25去比
01/08 16:52, 21F
→
01/08 16:53, , 22F
50勝,接著調整50空出來的位置. 發現25>22 所以直接
01/08 16:53, 22F
→
01/08 16:53, , 23F
放25. 所以T[5]=25
01/08 16:53, 23F
推
01/08 16:54, , 24F
SMMH我算的跟t大一樣
01/08 16:54, 24F
→
01/08 16:58, , 25F
所以我們的刪法根本不一樣囉XD
01/08 16:58, 25F
→
01/08 17:09, , 26F
50搬到T[5]後,40不用動不是嗎?直接調整T[5]
01/08 17:09, 26F
→
01/08 17:09, , 27F
拿T[9]跟25比發現25比較大直接放入
01/08 17:09, 27F
推
01/08 17:50, , 28F
96，18，25
01/08 17:50, 28F
推
01/08 17:58, , 29F
t大為什麼要移動40？50和40比完50放t3，25放t5，t4沒有大於t
01/08 17:58, 29F
→
01/08 17:58, , 30F
5，再看t9有沒有大於25，因為t9=22所以結束
01/08 17:58, 30F
推
01/08 17:58, , 31F
你們畫還沒delete之前是13,96,16,40,30,50,18,22,19,25
01/08 17:58, 31F
→
01/08 17:58, , 32F
嗎
01/08 17:58, 32F
推
01/08 18:00, , 33F
13,96,16,50,30,40,18,22,19,25
01/08 18:00, 33F
推
01/08 18:05, , 34F
同G大. 難怪刪完不一樣QQ
01/08 18:05, 34F
推
01/08 18:07, , 35F
啊啊我剛剛檢查了一下是我insert時候畫錯了，delete-max
01/08 18:07, 35F
→
01/08 18:07, , 36F
完是25沒錯><
01/08 18:07, 36F
→
01/08 18:11, , 37F
這種題目真考驗細心度><
01/08 18:11, 37F
→
01/08 18:19, , 38F
第七題是差分約束系統 可以用三角不等式轉成有向圖 用b
01/08 18:19, 38F
→
01/08 18:19, , 39F
ellmanford
01/08 18:19, 39F
→
01/08 18:19, , 40F
如果有負環就無解
01/08 18:19, 40F
推
01/08 18:25, , 41F
瞬間秒懂. 感謝A大
01/08 18:25, 41F
推
01/08 19:35, , 42F
第七題應該是用Dijkstra吧
01/08 19:35, 42F
‣ 更多 Astar5566 的文章
文章代碼(AID): #1OST0lyi (Grad-ProbAsk)