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

看板Grad-ProbAsk作者 (tsai)時間8年前 (2018/02/08 07:24), 8年前編輯推噓53(53推 0噓 37→)
留言90則, 25人參與, 8年前最新討論串1/1
感覺第五題等等會考 但是該怎麼証呢 拜託大家了@@ https://i.imgur.com/sfoIjSa.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.59.25 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1518045853.A.706.html ※ 編輯: w831231 (42.72.59.25), 02/08/2018 07:24:36
推
02/08 08:02, 8年前 , 1F
證Y不屬於NP但是是NP complete
02/08 08:02, 1F
→
02/08 08:39, 8年前 , 2F
可講的詳細點嗎 謝謝
02/08 08:39, 2F
推
02/08 08:40, 8年前 , 3F
就把你證明的方法跟理論基礎講出來呀
02/08 08:40, 3F
推
02/08 08:41, 8年前 , 4F
搜105 中央 有一篇在對答案
02/08 08:41, 4F
→
02/08 08:41, 8年前 , 5F
一模一樣的題目
02/08 08:41, 5F
→
02/08 08:42, 8年前 , 6F
她問你要怎麼證明y是hp hard你就把證法講一下就好
02/08 08:42, 6F
→
02/08 08:42, 8年前 , 7F
謝謝大大門
02/08 08:42, 7F
→
02/08 08:42, 8年前 , 8F
理論基礎像是np hard定義是所有np都可以reduce到它
02/08 08:42, 8F
→
02/08 08:43, 8年前 , 9F
而np complete的定義是既是np又是np hard
02/08 08:43, 9F
→
02/08 08:44, 8年前 , 10F
回p大 似乎沒有欸 https://i.imgur.com/gW7zvOQ.jpg
02/08 08:44, 10F
→
02/08 08:44, 8年前 , 11F
所以只要把x reduce到y就代表你可以吧所有的np reduce
02/08 08:44, 11F
→
02/08 08:44, 8年前 , 12F
到y 如此得證y是np hard
02/08 08:44, 12F
→
02/08 08:44, 8年前 , 13F
感謝T大
02/08 08:44, 13F
→
02/08 08:44, 8年前 , 14F
這沒考reduce考觀念而已算基本的
02/08 08:44, 14F
推
02/08 08:45, 8年前 , 15F
02/08 08:45, 15F
→
02/08 08:46, 8年前 , 16F
感謝感謝
02/08 08:46, 16F
推
02/08 08:46, 8年前 , 17F
把p, np, np complete, np hard定義搞清楚就沒這麼難
02/08 08:46, 17F
→
02/08 08:46, 8年前 , 18F
了
02/08 08:46, 18F
推
02/08 08:58, 8年前 , 19F
中央很愛考 這四年考了3年 真的不會就背起來吧
02/08 08:58, 19F
推
02/08 09:07, 8年前 , 20F
好
02/08 09:07, 20F
推
02/08 11:16, 8年前 , 21F
幹 考完馬上發現腦殘了，最後最短路徑演算法是小於
02/08 11:16, 21F
推
02/08 11:18, 8年前 , 22F
你是說20.21題嗎
02/08 11:18, 22F
推
02/08 11:19, 8年前 , 23F
最後是我才學術淺嗎
02/08 11:19, 23F
→
02/08 11:19, 8年前 , 24F
我不知道大於要怎麼做
02/08 11:19, 24F
→
02/08 11:19, 8年前 , 25F
不對應該是我他的選項大小於跟我想的相反
02/08 11:19, 25F
推
02/08 11:20, 8年前 , 26F
先知
02/08 11:20, 26F
推
02/08 11:20, 8年前 , 27F
對 我也是 我覺得是大於 可是選項沒有...
02/08 11:20, 27F
→
02/08 11:21, 8年前 , 28F
我也想半天想不出哪個選項能選 求解
02/08 11:21, 28F
推
02/08 11:21, 8年前 , 29F
然後我抓到他heap sort那個建heap他寫錯應該是i--
02/08 11:21, 29F
推
02/08 11:22, 8年前 , 30F
對
02/08 11:22, 30F
→
02/08 11:22, 8年前 , 31F
我當作題目大於小於寫反了在答
02/08 11:22, 31F
→
02/08 11:22, 8年前 , 32F
不然他一直加加 判斷大於0就會一直跑
02/08 11:22, 32F
推
02/08 11:22, 8年前 , 33F
還有quicksort A[i]應該找>pivot，A[j]應該是<pivot的
02/08 11:22, 33F
→
02/08 11:22, 8年前 , 34F
吧。然後用adjust調整heap，後面不是應該是i--嗎？
02/08 11:22, 34F
→
02/08 11:23, 8年前 , 35F
整體而言不難 話說河內塔是39嗎我找不到更短的
02/08 11:23, 35F
推
02/08 11:24, 8年前 , 36F
39+1
02/08 11:24, 36F
推
02/08 11:24, 8年前 , 37F
我也是39
02/08 11:24, 37F
推
02/08 11:25, 8年前 , 38F
1+7+31=39
02/08 11:25, 38F
推
02/08 11:26, 8年前 , 39F
河內塔也算39
02/08 11:26, 39F
推
02/08 11:26, 8年前 , 40F
他選想給不好 有給40的話我會不小心選到ww
02/08 11:26, 40F
推
02/08 11:28, 8年前 , 41F
那個i++怎麼算啊 這樣是送分嗎
02/08 11:28, 41F
推
02/08 11:28, 8年前 , 42F
最後一題bellman ford是不是怪怪的
02/08 11:28, 42F
推
02/08 11:28, 8年前 , 43F
除3的那個sort複雜度是多少啊？
02/08 11:28, 43F
推
02/08 11:30, 8年前 , 44F
做後一題不是floyd warshall嗎
02/08 11:30, 44F
→
02/08 11:31, 8年前 , 45F
tn=3t(2n/3) 我印象中時間遞迴漲這樣
02/08 11:31, 45F
推
02/08 11:32, 8年前 , 46F
先知
02/08 11:32, 46F
推
02/08 11:32, 8年前 , 47F
logn 3/2的3. 我寫這樣
02/08 11:32, 47F
→
02/08 11:32, 8年前 , 48F
我覺得建立heap不會送不過最後幾題就不知道了
02/08 11:32, 48F
推
02/08 11:32, 8年前 , 49F
謝謝 我也是選那項
02/08 11:32, 49F
→
02/08 11:32, 8年前 , 50F
說錯 是 n的log3/2 3
02/08 11:32, 50F
→
02/08 11:33, 8年前 , 51F
空間是n嗎
02/08 11:33, 51F
→
02/08 11:33, 8年前 , 52F
所以T大的i寫 i=n/2嗎
02/08 11:33, 52F
→
02/08 11:34, 8年前 , 53F
對啊雖然+1跟沒加執行結果應該是一樣的
02/08 11:34, 53F
推
02/08 11:35, 8年前 , 54F
額外空間有需要n？
02/08 11:35, 54F
推
02/08 11:35, 8年前 , 55F
我算了stack用的空間
02/08 11:35, 55F
→
02/08 11:36, 8年前 , 56F
想說到底是多少不過現在想想應該小於n
02/08 11:36, 56F
→
02/08 11:36, 8年前 , 57F
要應該也是log的等級
02/08 11:36, 57F
→
02/08 11:37, 8年前 , 58F
應該是logn現在想了一下
02/08 11:37, 58F
推
02/08 11:37, 8年前 , 59F
我寫Logn 不過不是很確定
02/08 11:37, 59F
→
02/08 11:38, 8年前 , 60F
我那時不小心連array也存到stack就變n了QQ
02/08 11:38, 60F
推
02/08 11:38, 8年前 , 61F
我也在猶豫遞迴用的空間要不要算
02/08 11:38, 61F
推
02/08 11:39, 8年前 , 62F
我怎麼覺得我中央有點爆炸 第一題寫log2 3QQ
02/08 11:39, 62F
推
02/08 11:41, 8年前 , 63F
你不可以有台大了就這樣讓分r
02/08 11:41, 63F
推
02/08 11:42, 8年前 , 64F
有台大就很囂張QQ
02/08 11:42, 64F
推
02/08 11:44, 8年前 , 65F
別說台大惹 想到就傷心
02/08 11:44, 65F
推
02/08 11:45, 8年前 , 66F
想問一下np那幾題答案多少 我有連續兩題寫abce 因為
02/08 11:45, 66F
→
02/08 11:46, 8年前 , 67F
當初有點想放沒讀很熟
02/08 11:46, 67F
推
02/08 11:46, 8年前 , 68F
leo大台大電機比80%的人多10分 2^10000
02/08 11:46, 68F
推
02/08 11:47, 8年前 , 69F
Stack的空間不用算嗎？我選n呢QQ
02/08 11:47, 69F
推
02/08 11:48, 8年前 , 70F
可4馬跟asymmetric錯惹 -15
02/08 11:48, 70F
推
02/08 11:48, 8年前 , 71F
至少有兩題程式碼有問題 只是連考卷都收走了讓你也沒辦法
02/08 11:48, 71F
推
02/08 11:49, 8年前 , 72F
而且那題Heap看到i ++我直接選I=0不要進for XD
02/08 11:49, 72F
推
02/08 11:50, 8年前 , 73F
你不能跟教授打錯字過不去啊XD
02/08 11:50, 73F
→
02/08 11:51, 8年前 , 74F
河內塔根本懶的算 直接放了
02/08 11:51, 74F
推
02/08 11:54, 8年前 , 75F
中央教授好爽電腦閱卷都不用改,而且自己應該沒對過考卷
02/08 11:54, 75F
推
02/08 11:55, 8年前 , 76F
不錯了 跟昨天的電機丙比...
02/08 11:55, 76F
推
02/08 11:56, 8年前 , 77F
別提那四隻馬了
02/08 11:56, 77F
→
02/08 11:57, 8年前 , 78F
????
02/08 11:57, 78F
推
02/08 12:05, 8年前 , 79F
河內塔好像是把12345疊在B後 6移到C 7回合 再移動1234
02/08 12:05, 79F
→
02/08 12:05, 8年前 , 80F
5就好 所以是7+2^5-1=38 ？？
02/08 12:05, 80F
推
02/08 12:11, 8年前 , 81F
對 floyd-warshall 打錯XD
02/08 12:11, 81F
推
02/08 12:17, 8年前 , 82F
話說我看到有人帶整本演算法來看整個眼神死
02/08 12:17, 82F
推
02/08 12:17, 8年前 , 83F
123放在45上就要7步了。另外heap那題我直接背誒，印象中
02/08 12:17, 83F
→
02/08 12:17, 8年前 , 84F
是從最後一個父點作adjust
02/08 12:17, 84F
→
02/08 12:21, 8年前 , 85F
可是他一直加加還>0 不給結束了
02/08 12:21, 85F
推
02/08 12:22, 8年前 , 86F
應該是i--打錯成i++
02/08 12:22, 86F
推
02/08 16:22, 8年前 , 87F
123放到45 要7步 然後6放到最右邊一步
02/08 16:22, 87F
→
02/08 16:23, 8年前 , 88F
再加31 共39步？
02/08 16:23, 88F
推
02/08 18:07, 8年前 , 89F
Leo大 有台大了 中央就亂考
02/08 18:07, 89F
推
02/09 00:14, 8年前 , 90F
到底是誰說我有台大QQ 我自己怎都不知道
02/09 00:14, 90F
‣ 更多 w831231 的文章
文章代碼(AID): #1QUugTS6 (Grad-ProbAsk)