[理工] 105 成大 程式設計

看板Grad-ProbAsk作者 (光芒今年拿冠軍)時間8年前 (2017/12/31 13:56), 編輯推噓11(11推 0噓 25→)
留言36則, 5人參與, 9年前最新討論串1/1
https://i.imgur.com/5vO858Y.jpg
https://i.imgur.com/FHjB1fG.jpg
請問這一題我這樣寫可以嗎？ 有什麼bug嗎？ 感謝～ ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.96.254 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1514699780.A.241.html
推
12/31 14:50, 8年前 , 1F
If那行沒講怎麼找的 如果linear search 是O(|V|^2)
12/31 14:50, 1F
推
12/31 15:04, 8年前 , 2F
If 那段應該寫成迴圈一個一個比對最簡易
12/31 15:04, 2F
→
12/31 15:06, 8年前 , 3F
所以我要假設G是一個adjancency matrix
12/31 15:06, 3F
→
12/31 15:06, 8年前 , 4F
V€adj.[B]就去測那個欄位是不是1就好
12/31 15:06, 4F
→
12/31 15:06, 8年前 , 5F
不過他的input只有A B
12/31 15:06, 5F
→
12/31 15:06, 8年前 , 6F
不是應該要有個G嗎？
12/31 15:06, 6F
→
12/31 15:06, 8年前 , 7F
不管是用什麼來存那個圖？
12/31 15:06, 7F
推
12/31 15:07, 8年前 , 8F
我覺得可以用hash? A相鄰點的丟進hash table,再檢測B相鄰
12/31 15:07, 8F
→
12/31 15:07, 8年前 , 9F
的點有沒有在table裡,有個話count++
12/31 15:07, 9F
→
12/31 15:07, 8年前 , 10F
我原本也想用迴圈，不過他的input沒有讓我傳矩陣，
12/31 15:07, 10F
→
12/31 15:07, 8年前 , 11F
寫起來毛毛的XD
12/31 15:07, 11F
→
12/31 15:08, 8年前 , 12F
這樣O(|V|)
12/31 15:08, 12F
→
12/31 15:11, 8年前 , 13F
用adjMatrix是O(|V|^2)題目要求要最佳化運算量
12/31 15:11, 13F
推
12/31 15:11, 8年前 , 14F
也可以用bfs喔
12/31 15:11, 14F
推
12/31 15:14, 8年前 , 15F
用bfs code超簡單
12/31 15:14, 15F
→
12/31 15:15, 8年前 , 16F
只要將a,b兩個node各別作一次的enqueue adj vertex
12/31 15:15, 16F
→
12/31 15:16, 8年前 , 17F
然後dequeue兩個queue來比對
12/31 15:16, 17F
→
12/31 15:17, 8年前 , 18F
用bfs的前提是不是要把相鄰node由小到大enqueue?
12/31 15:17, 18F
推
12/31 15:20, 8年前 , 19F
謝謝樓上補充 忘了假設這前題
12/31 15:20, 19F
→
12/31 15:21, 8年前 , 20F
反正他題目要儘量優化 這樣假設應該ok
12/31 15:21, 20F
→
12/31 15:26, 8年前 , 21F
那我直接假設用adjacency matrix存
12/31 15:26, 21F
→
12/31 15:26, 8年前 , 22F
然後跑for i = 1 to |v|
12/31 15:26, 22F
→
12/31 15:26, 8年前 , 23F
If G(i,a)=1 and G(i,b)=1 then count++
12/31 15:26, 23F
→
12/31 15:26, 8年前 , 24F
這樣好像更快？就O(v)
12/31 15:26, 24F
推
12/31 15:29, 8年前 , 25F
可是你a,b兩個graph這樣只有scan一點吧
12/31 15:29, 25F
→
12/31 15:37, 8年前 , 26F
什麼意思？
12/31 15:37, 26F
→
12/31 15:38, 8年前 , 27F
A B不是在同一張圖上嗎？
12/31 15:38, 27F
推
12/31 15:44, 8年前 , 28F
我的意思是你用舉陣是二維 你給了i只有一維阿
12/31 15:44, 28F
推
12/31 15:46, 8年前 , 29F
噢我誤會了 應該可以
12/31 15:46, 29F
→
12/31 16:00, 8年前 , 30F
好喔
12/31 16:00, 30F
→
12/31 16:00, 8年前 , 31F
不過這樣寫出來沒幾句話就15分XD
12/31 16:00, 31F
推
01/01 17:43, 9年前 , 32F
用matrix跟你一樣 或是用adj list 但是點由大到小存在
01/01 17:43, 32F
→
01/01 17:43, 9年前 , 33F
裡面應該也可以八 應該八@@
01/01 17:43, 33F
推
01/02 10:48, 9年前 , 34F
有大大能分享 用bfs的寫法嗎 小弟太菜了
01/02 10:48, 34F
→
01/02 16:31, 9年前 , 35F
01/02 16:31, 35F
→
01/02 16:31, 9年前 , 36F
大概是這樣？
01/02 16:31, 36F
‣ 更多 TampaBayRays 的文章
文章代碼(AID): #1QI7m491 (Grad-ProbAsk)