[理工] 102台大資工 資演

看板Grad-ProbAsk作者 (E神)時間7年前 (2017/01/23 16:00), 編輯推噓3(3推 0噓 61→)
留言64則, 4人參與, 最新討論串2/2 (看更多)
http://i.imgur.com/xTNqm5d.jpg
想問一下大家b小題的圖長什麼樣子 因為union到最後我的圖似乎有點醜 順便問一下Find的答案是多少，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.50.59 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485158419.A.32A.html
→
01/23 16:22, , 1F
做完第二個for 迴圈就不變了
01/23 16:22, 1F
→
01/23 16:23, , 2F
我做的答案是回傳為x2
01/23 16:23, 2F
→
01/23 16:25, , 3F
http://imgur.com/a/VCNCx 楓葉本21.2-2 習題
01/23 16:25, 3F
→
01/23 16:26, , 4F
01/23 16:26, 4F
→
01/23 16:27, , 5F
我是看不太懂它答案在寫甚麼啦@@ return 1有點答非
01/23 16:27, 5F
→
01/23 16:27, , 6F
所問
01/23 16:27, 6F
→
01/23 16:27, , 7F
我是畫這樣，箭頭指的方向是parent，有用union by rank
01/23 16:27, 7F
→
01/23 16:27, , 8F
和path compression，但我沒有答案也不知道這樣對不對
01/23 16:27, 8F
→
01/23 16:29, , 9F
原來All x are in the same set，那我鐵定畫錯，先不要
01/23 16:29, 9F
→
01/23 16:29, , 10F
理我的圖
01/23 16:29, 10F
→
01/23 16:30, , 11F
喔不我看到其實有改題目了，Union(x1,x5)被改成
01/23 16:30, 11F
→
01/23 16:30, , 12F
Union(x1,x15)，那好像有一點點機會是對的XD
01/23 16:30, 12F
→
01/23 16:30, , 13F
01/23 16:30, 13F
→
01/23 16:31, , 14F
感覺是沒差QQ 我是憑印象照著union的code走
01/23 16:31, 14F
→
01/23 16:32, , 15F
做到第二個迴圈結束就不會有任何相異了
01/23 16:32, 15F
→
01/23 16:35, , 16F
第二個for loop的union是Union(x1,x2),Union(x3,x4),
01/23 16:35, 16F
→
01/23 16:35, , 17F
Union(x5,x6),...,Union(x15,x16)嗎？
01/23 16:35, 17F
→
01/23 16:35, , 18F
還是我誤會了什麼...
01/23 16:35, 18F
→
01/23 16:38, , 19F
我畫出來跟yu的差不多，不過x10是在x9那串
01/23 16:38, 19F
→
01/23 16:39, , 20F
是 X1,X2 X2,X3 ...下去
01/23 16:39, 20F
→
01/23 16:41, , 21F
我x10是在Union(x1,x10)的時候因為會先find(x10)，因此
01/23 16:41, 21F
→
01/23 16:41, , 22F
根據path compression會把x10的parent指向root
01/23 16:41, 22F
→
01/23 16:41, , 23F
by2 by4是什麼意思？
01/23 16:41, 23F
→
01/23 16:42, , 24F
不過Union by rank應該是rank大當root，我搞成小的了
01/23 16:42, 24F
→
01/23 16:42, , 25F
我覺得應該是i一次+2 or +4拉...第一次看到這種寫法
01/23 16:42, 25F
→
01/23 16:45, , 26F
union by rank 我是當成高度來看
01/23 16:45, 26F
→
01/23 16:53, , 27F
題目沒說要 union by rank
01/23 16:53, 27F
→
01/23 16:53, , 28F
剛剛po的解答無誤，我畫錯了 QQ
01/23 16:53, 28F
→
01/23 16:55, , 29F
等等 我理解錯誤 我再想一下@_@
01/23 16:55, 29F
→
01/23 17:00, , 30F
我還是覺得我的
01/23 17:00, 30F
→
01/23 17:00, , 31F
答案讓我可以接受XDD
01/23 17:00, 31F
→
01/23 17:01, , 32F
看有沒有人有其他的看法
01/23 17:01, 32F
→
01/23 17:20, , 33F
大標題有寫
01/23 17:20, 33F
→
01/23 17:23, , 34F
哦哦 我看到了! 原本只看原po的圖而已
01/23 17:23, 34F
→
01/23 17:30, , 35F
http://imgur.com/a/e7W9N 剛剛模擬跑的跟我想得差
01/23 17:30, 35F
→
01/23 17:30, , 36F
不多
01/23 17:30, 36F
→
01/23 17:35, , 37F
抱歉 應該是yupog大說的 Orz +2 +4 沒錯
01/23 17:35, 37F
→
01/23 17:50, , 38F
01/23 17:50, 38F
→
01/23 17:50, , 39F
再畫一次用rank大的當root的，這樣才跟simulation跑出
01/23 17:50, 39F
→
01/23 17:51, , 40F
來的一樣，我剛剛那個教授應該會直接打錯...
01/23 17:51, 40F
→
01/23 17:55, , 41F
The first way, called譃nion by rank, is to always
01/23 17:55, 41F
→
01/23 17:55, , 42F
attach the smaller tree to the root of the larger
01/23 17:55, 42F
→
01/23 17:56, , 43F
tree. Since it is the depth of the tree that affec
01/23 17:56, 43F
→
01/23 17:56, , 44F
ts the running time, the tree with smaller depth g
01/23 17:56, 44F
→
01/23 17:56, , 45F
ets added under the root of the deeper tree, which
01/23 17:56, 45F
→
01/23 17:56, , 46F
only increases the depth if the depths were equal
01/23 17:56, 46F
→
01/23 17:56, , 47F
.
01/23 17:56, 47F
→
01/23 17:56, , 48F
wiki 上的說法
01/23 17:56, 48F
→
01/23 17:57, , 49F
嗯嗯，確實是要用大的當root，小的attach上去，感謝
01/23 17:57, 49F
→
01/23 17:58, , 50F
模擬網頁上面有給我們兩個union by rank的選項：
01/23 17:58, 50F
→
01/23 17:59, , 51F
1.Rank = # of nodes, 2.Rank = estimated height
01/23 17:59, 51F
→
01/23 17:59, , 52F
看來的確如A大所說，兩者皆可
01/23 17:59, 52F
推
01/23 20:08, , 53F
http://imgur.com/a/Ul05C 沒有用path-compression我畫
01/23 20:08, 53F
→
01/23 20:09, , 54F
這樣,用union-by-rank我把號碼比較大的當Root值比較大
01/23 20:09, 54F
→
01/23 20:09, , 55F
最後Find-Set()兩個我都回傳x16
01/23 20:09, 55F
→
01/23 20:12, , 56F
Find-Set應該有沒有用union-by-rank和path-compression
01/23 20:12, 56F
→
01/23 20:13, , 57F
結果都會一樣？只是速度上的差異而已，確認一下觀念
01/23 20:13, 57F
→
01/23 20:19, , 58F
我是覺得除了5、6、7、8其他都有可能
01/23 20:19, 58F
推
01/23 20:20, , 59F
結果不會一樣吧? 不同Union方法最後Find-set可能就會不
01/23 20:20, 59F
→
01/23 20:20, , 60F
一樣
01/23 20:20, 60F
→
01/23 20:21, , 61F
嗯嗯對，有沒有用union-by-rank的Find-Set應該不一樣
01/23 20:21, 61F
→
01/23 20:21, , 62F
path-compression應該沒差？
01/23 20:21, 62F
推
01/23 20:23, , 63F
path-compression應該是沒差
01/23 20:23, 63F
→
01/23 20:26, , 64F
嗯嗯好的，感謝你們
01/23 20:26, 64F
‣ 更多 EasonGod 的文章
文章代碼(AID): #1OXRWJCg (Grad-ProbAsk)
‣ 更多 EasonGod 的文章
文章代碼(AID): #1OXRWJCg (Grad-ProbAsk)