1. PTT
  2. Grad-ProbAsk

[理工] 中央106資演［5］

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

Links booklink

Contact Us: admin [ a t ] ucptt.com