推 leoone: 證Y不屬於NP但是是NP complete 02/08 08:02
→ w831231: 可講的詳細點嗎 謝謝 02/08 08:39
推 TMDTMD2487: 就把你證明的方法跟理論基礎講出來呀 02/08 08:40
推 pinchieh1996: 搜105 中央 有一篇在對答案 02/08 08:41
→ pinchieh1996: 一模一樣的題目 02/08 08:41
→ TMDTMD2487: 她問你要怎麼證明y是hp hard你就把證法講一下就好 02/08 08:42
→ w831231: 謝謝大大門 02/08 08:42
→ TMDTMD2487: 理論基礎像是np hard定義是所有np都可以reduce到它 02/08 08:42
→ TMDTMD2487: 而np complete的定義是既是np又是np hard 02/08 08:43
→ TMDTMD2487: 所以只要把x reduce到y就代表你可以吧所有的np reduce 02/08 08:44
→ TMDTMD2487: 到y 如此得證y是np hard 02/08 08:44
→ w831231: 感謝T大 02/08 08:44
→ TMDTMD2487: 這沒考reduce考觀念而已算基本的 02/08 08:44
→ w831231: 感謝感謝 02/08 08:46
推 TMDTMD2487: 把p, np, np complete, np hard定義搞清楚就沒這麼難 02/08 08:46
→ TMDTMD2487: 了 02/08 08:46
推 leoone: 中央很愛考 這四年考了3年 真的不會就背起來吧 02/08 08:58
推 gR7P4zXH: 好 02/08 09:07
推 agag5123: 幹 考完馬上發現腦殘了，最後最短路徑演算法是小於 02/08 11:16
推 moneylon: 你是說20.21題嗎 02/08 11:18
推 TMDTMD2487: 最後是我才學術淺嗎 02/08 11:19
→ TMDTMD2487: 我不知道大於要怎麼做 02/08 11:19
→ TMDTMD2487: 不對應該是我他的選項大小於跟我想的相反 02/08 11:19
推 gR7P4zXH: 先知 02/08 11:20
推 moneylon: 對 我也是 我覺得是大於 可是選項沒有... 02/08 11:20
→ devilkool: 我也想半天想不出哪個選項能選 求解 02/08 11:21
推 TMDTMD2487: 然後我抓到他heap sort那個建heap他寫錯應該是i-- 02/08 11:21
推 moneylon: 對 02/08 11:22
→ TMDTMD2487: 我當作題目大於小於寫反了在答 02/08 11:22
→ moneylon: 不然他一直加加 判斷大於0就會一直跑 02/08 11:22
推 tcc080206: 還有quicksort A[i]應該找>pivot，A[j]應該是<pivot的 02/08 11:22
→ tcc080206: 吧。然後用adjust調整heap，後面不是應該是i--嗎？ 02/08 11:22
→ TMDTMD2487: 整體而言不難 話說河內塔是39嗎我找不到更短的 02/08 11:23
推 tcc080206: 39+1 02/08 11:24
推 agag5123: 我也是39 02/08 11:24
推 age01282005: 1+7+31=39 02/08 11:25
推 havewind: 河內塔也算39 02/08 11:26
推 TMDTMD2487: 他選想給不好 有給40的話我會不小心選到ww 02/08 11:26
推 wei5280: 那個i++怎麼算啊 這樣是送分嗎 02/08 11:28
推 shownlin: 最後一題bellman ford是不是怪怪的 02/08 11:28
推 agag5123: 除3的那個sort複雜度是多少啊？ 02/08 11:28
推 TMDTMD2487: 做後一題不是floyd warshall嗎 02/08 11:30
→ TMDTMD2487: tn=3t(2n/3) 我印象中時間遞迴漲這樣 02/08 11:31
推 microchianag: 先知 02/08 11:32
推 moneylon: logn 3/2的3. 我寫這樣 02/08 11:32
→ TMDTMD2487: 我覺得建立heap不會送不過最後幾題就不知道了 02/08 11:32
推 agag5123: 謝謝 我也是選那項 02/08 11:32
→ moneylon: 說錯 是 n的log3/2 3 02/08 11:32
→ TMDTMD2487: 空間是n嗎 02/08 11:33
→ moneylon: 所以T大的i寫 i=n/2嗎 02/08 11:33
→ TMDTMD2487: 對啊雖然+1跟沒加執行結果應該是一樣的 02/08 11:34
推 HungDa: 額外空間有需要n？ 02/08 11:35
推 TMDTMD2487: 我算了stack用的空間 02/08 11:35
→ TMDTMD2487: 想說到底是多少不過現在想想應該小於n 02/08 11:36
→ TMDTMD2487: 要應該也是log的等級 02/08 11:36
→ TMDTMD2487: 應該是logn現在想了一下 02/08 11:37
推 lion83395: 我寫Logn 不過不是很確定 02/08 11:37
→ TMDTMD2487: 我那時不小心連array也存到stack就變n了QQ 02/08 11:38
推 king8313: 我也在猶豫遞迴用的空間要不要算 02/08 11:38
推 leoone: 我怎麼覺得我中央有點爆炸 第一題寫log2 3QQ 02/08 11:39
推 Xunion: 你不可以有台大了就這樣讓分r 02/08 11:41
推 TMDTMD2487: 有台大就很囂張QQ 02/08 11:42
推 leoone: 別說台大惹 想到就傷心 02/08 11:44
推 jimmy45689: 想問一下np那幾題答案多少 我有連續兩題寫abce 因為 02/08 11:45
→ jimmy45689: 當初有點想放沒讀很熟 02/08 11:46
推 moneylon: leo大台大電機比80%的人多10分 2^10000 02/08 11:46
推 ReanoX: Stack的空間不用算嗎？我選n呢QQ 02/08 11:47
推 leoone: 可4馬跟asymmetric錯惹 -15 02/08 11:48
推 djmez: 至少有兩題程式碼有問題 只是連考卷都收走了讓你也沒辦法 02/08 11:48
推 ReanoX: 而且那題Heap看到i ++我直接選I=0不要進for XD 02/08 11:49
推 TMDTMD2487: 你不能跟教授打錯字過不去啊XD 02/08 11:50
→ djmez: 河內塔根本懶的算 直接放了 02/08 11:51
推 HungDa: 中央教授好爽電腦閱卷都不用改,而且自己應該沒對過考卷 02/08 11:54
推 TMDTMD2487: 不錯了 跟昨天的電機丙比... 02/08 11:55
推 moneylon: 別提那四隻馬了 02/08 11:56
→ gR7P4zXH: ???? 02/08 11:57
推 harryboy23: 河內塔好像是把12345疊在B後 6移到C 7回合 再移動1234 02/08 12:05
→ harryboy23: 5就好 所以是7+2^5-1=38 ？？ 02/08 12:05
推 shownlin: 對 floyd-warshall 打錯XD 02/08 12:11
推 HungDa: 話說我看到有人帶整本演算法來看整個眼神死 02/08 12:17
推 agag5123: 123放在45上就要7步了。另外heap那題我直接背誒，印象中 02/08 12:17
→ agag5123: 是從最後一個父點作adjust 02/08 12:17
→ djmez: 可是他一直加加還>0 不給結束了 02/08 12:21
推 Dora5566: 應該是i--打錯成i++ 02/08 12:22
推 MOUOREO: 123放到45 要7步 然後6放到最右邊一步 02/08 16:22
→ MOUOREO: 再加31 共39步？ 02/08 16:23
推 jacky804024: Leo大 有台大了 中央就亂考 02/08 18:07
推 leoone: 到底是誰說我有台大QQ 我自己怎都不知道 02/09 00:14