PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 109清大 計科
作者:
seafoodccu
(c-看看你)
2021-01-04 20:05:21
想問這題,不太確定自己對題目的理解正不正確
https://i.imgur.com/Ht1Fuer.jpg
https://i.imgur.com/8RFOJrv.jpg
這三題答案我都寫yes,然後下面是我畫的example,若有錯再麻煩各大神糾正,謝謝!
https://i.imgur.com/UdksBYK.jpg
還有這一題,不知道該怎麼證明
https://i.imgur.com/R6Qa95Q.jpg
作者:
mathtsai
(mathtsai)
2021-01-04 21:23:00
b-ii 畫個等腰三角形 邊長2,2,19.很經典 新增一個元素 sum/2就可以從2-partition reduce成 3-partition12.應該只要能構造就好
作者:
seafoodccu
(c-看看你)
2021-01-04 22:46:00
m大,還是不太懂,為什麼是新增sum/2的元素?
作者:
mathtsai
(mathtsai)
2021-01-05 00:38:00
https://reurl.cc/e80A07
參考
作者:
seafoodccu
(c-看看你)
2021-01-05 13:58:00
懂了,感謝m大!
作者:
alex391a
(麥基)
2021-01-07 10:28:00
https://i.imgur.com/SmZqPnO.jpg
各位你們b-ii 的例子都是錯的喔
作者:
seafoodccu
(c-看看你)
2021-01-07 11:38:00
感謝a大!請問有什麼好的例子嗎?畫不出來QQ
作者:
alex391a
(麥基)
2021-01-07 13:04:00
https://i.imgur.com/SveTCTJ.jpg
我朋友畫的 看起來應該是對的沒錯
作者:
try66889
(小皮)
2021-01-07 13:12:00
想請問a大原PO原本畫的是哪裡有誤呢?看起來x到各點max shortest都是8 其他abc點max shortestpath也是8,不知道我有哪裡沒注意到的地方QQ不好意思 發現上面打錯更正 abcd max shortest path
作者:
seafoodccu
(c-看看你)
2021-01-07 13:28:00
我畫的如果X點把邊切成6:2的話,max shortest path會變成6這樣center只能在邊上
https://i.imgur.com/9DPQi9G.jpg
a大,如果x這樣設,好像也不符合了
作者:
try66889
(小皮)
2021-01-07 13:40:00
不過s大原本不是切成44嗎@@?
作者:
seafoodccu
(c-看看你)
2021-01-07 13:47:00
但有更好的切法讓shortest path變更短呀,X只是我假設的,所以對那張圖來說,有其他的在邊上的center可以有最短的距離
作者:
try66889
(小皮)
2021-01-07 13:52:00
不過題目不是只有說舉例嗎 > <?
作者:
seafoodccu
(c-看看你)
2021-01-07 14:05:00
https://i.imgur.com/PPM8Mig.jpg
不知道改成這樣對不對,我找不到任何其他在邊上的點有最大最短距離小於2,且點a、c的最大最短距離也是2
作者:
try66889
(小皮)
2021-01-07 15:29:00
看起來沒錯,我也是最小只有找到2 acx
作者:
alex391a
(麥基)
2021-01-07 16:00:00
題目的absolutely center定義是要找可以到所有點的距離的max最小那個 所以原po的那個只有切4,2那個點符合我剛剛的那個反例中間是沒有點的 那是兩條邊 所以你只能點在其中一邊上原po新的那張圖你x只能選一個邊畫 不能畫在兩個邊上啦
https://i.imgur.com/yZxbUhO.jpg
要把他拉開來看左邊是我的右邊是原po新的我的應該才行得通
作者:
seafoodccu
(c-看看你)
2021-01-07 16:21:00
https://i.imgur.com/kCxtXaV.jpg
作者:
try66889
(小皮)
2021-01-07 16:21:00
a大抱歉,我愚鈍還是不太懂QQ
https://i.imgur.com/wRuafOK.jpg
這是原Po最一開始的圖,各點到各點的maximum shortestpath = 8(abcdx),這樣不是表示abcdx每個都是 absolutely center嗎?(大家都相同,所以大家都是minimum?)有誤會弄錯的地方請打醒我QQ
作者:
alex391a
(麥基)
2021-01-07 16:28:00
https://i.imgur.com/8ffEKMp.jpg
t大b小題說我們現在定義讓center可以在邊上讓到各點距離更小 稱為absolutely center 所以我找到x到各點的距離最多6 其他點就不可能是absolutely center了回原po 竟然!看來我的也沒找到QQ不知道有沒有大大能找到反例或是證明不會同時在點跟邊上了
作者:
try66889
(小皮)
2021-01-07 17:17:00
了解惹! 謝謝大家QQ
作者:
mathtsai
(mathtsai)
2021-01-07 17:53:00
欸欸 所以我b-ii的例子也是錯的嗎QQ?結果隨便舉個例子都錯 看來要想清楚一點QQ會不會其實這題根本沒反例啊XD考慮三個點a,b,c d(a,b) = L (最長的shortest path)
https://imgur.com/UqlK6C4
這樣有符合b-ii嗎自答 不符合
https://imgur.com/xasTue5
上面的edge都是最短路徑a,b是absolute center , d1+d2 < max假設有一點p在edge上,並且p也是absolute centerp必須在ab的最短路徑上(簡單證明)令d(a,p) = max-d1,則d(b,p) = d1根據定義 d(c,p) = max但是根據上面所述 d(c,p) = min(max, d1+d2) = d1+d2抱歉我寫錯了 我等等重回我放棄 感覺有啥地方卡住了 應該可以從上面的方向去思考
作者:
alex391a
(麥基)
2021-01-08 18:30:00
https://i.imgur.com/OlhFpb0.jpg
目前想到的 看起來可以 求大大幫檢查在2的邊中點 還有中間那點
作者: coco5747769
2021-01-27 00:50:00
https://i.imgur.com/kj6bCF9.jpg
我是畫這樣求檢查
作者:
alex391a
(麥基)
2021-01-29 20:48:00
跟我畫的類似吧
繼續閱讀
[理工] 108 清大系計
lucy35
Re: [理工] 109台大電信資演對答案
jimmylin1024
[理工] 資演 交大109 (4)(9)(12)
try66889
[心得] 國家預報月
settima
[理工] 108 交大資工 計系 第二題
ChouEita
[理工] 109台大電信資演對答案
shashayou
[理工] 交大 103 線代 均方近似解
terry8575
[理工] 109 交大資工 8、9、12、14
liljimmy
[理工] 108中央 資演
lucy35
[理工] 107年 交大資聯 計系 20 與題組D
uuxx66
Links
booklink
Contact Us: admin [ a t ] ucptt.com