Re: [理工] [資演］109台大電機對答案 joywilliamjo PTT批踢踢實業坊

作者: joywilliamjo (joywilliamjoy) 2021-01-30 15:06:28

想問這張的第17題
照他上面order的定義是root的child樹
那不是應該要是2^6=64嗎？
有點看不懂為什麼是21以及21怎麼畫出來的
感謝

作者: try66889 (小皮) 2021-01-30 15:43:00

字有點多用貼圖的> <https://i.imgur.com/swEnPD1.jpg發現上面的圖剛才手殘畫錯>< 這個才對～https://i.imgur.com/fr3Wrb1.jpg不過最小我覺得應該是可以到19 @@ B4+B0+B1的話好像可以不知道有沒有沒考慮到的地方@@

作者: linnom (繁星) 2021-01-30 16:04:00

因為費波那契堆積在delete node時採用標記的方式，所以可以從64個node的多項式堆積切看看

作者: try66889 (小皮) 2021-01-30 16:11:00

https://i.imgur.com/Xfxx6vK.jpg可能我也不是很會畫Fibonacci tree 所以畫的比較醜QQ32+2是B5和B1嗎OAO?Degree7最小我覺得應該是16+1+2+4

作者: linnom (繁星) 2021-01-30 16:29:00

https://i.imgur.com/y6WClki.jpg我是這樣思考的～可能有更簡單的方式，僅供參考抱歉好像寫錯哈哈我想看看找到了，綠色少看，已更正https://i.imgur.com/WMWPDT2.jpg

作者: try66889 (小皮) 2021-01-30 16:48:00

原Po抱歉，先不要理我，我發現剛才我有弄錯的地方。Fibonacci heap 建立時若有剩下沒同level可以merge的tree應該是直接link root起來，而不是我畫的那樣跑到大的tree下面,樓上l大解法應該比較正確，抱歉> <

作者: alex391a (麥基) 2021-01-30 17:02:00

https://i.imgur.com/86cmCVY.jpg我是這樣寫的能刪的最多點剩下的點可以寫出遞迴就變費式數列了圈起來是要刪掉的

作者: linnom (繁星) 2021-01-30 17:08:00

喔喔喔樓上的方法好聰明，原來費波那契堆積名字是這樣來的嗎（？

作者: joywilliamjo (joywilliamjoy) 2021-01-30 20:04:00

感謝大家

繼續閱讀