Re: [理工] 107 中央 資結演算法 對答案

看板Grad-ProbAsk作者 (dumpling)時間7年前 (2019/01/19 13:46), 7年前編輯推噓16(16推 0噓 16→)
留言32則, 11人參與, 6年前最新討論串2/2 (看更多)
※ 引述《yijia1127 (我不是豪野人)》之銘言： : 1. E : 2. A (不會) : 3. C : 4. A : 5. D : 6. D : 7. E : 8. C : 9. D : 10. C : 11. E : 12. E : 13. B : 14. E : 15. ABC (不會,E看不太懂要不要選) : 16. ABCE : 17. AC : 18. ABE (不知道C要不要跟著一起選) : 19. ACE : 20. B : 21. B : 22. BC : 主要想請教大家第2,15,18題的答案 : 18題的後面如果已經多做一輪(E選項)，那麽前面的for loop是否還需要多做一輪(C選項) : 謝 我想問ㄧ下第13題 https://imgur.com/sFE2XVo
我覺得答案應該是(C) 因為pivot在最右邊 所以需要跟ㄧ個大於pivot的做交換 不知道有沒有錯 還有第16題 https://imgur.com/GJysBux
(B)應該不能選吧 應該是 If X is a NP-complete problem then every NP problem can polynomial reduce to X 第17題 https://imgur.com/hkTRinA
(B)應該可以選吧 NP-complete ㄧ定是 NP-hard 吧 (E) Y 應該是NP-complete 不過他說他是 NP-hard 應該也沒錯吧 請知道的大神 幫我解惑ㄧ下 最後附上第3題 https://imgur.com/zAgrsiJ
SB 我畫的ㄧ個反例 應該是沒有問題吧 https://imgur.com/oPUJ7Ew
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.125.22 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1547876781.A.A4C.html
推
01/19 13:53, 7年前 , 1F
你看第12題出do-while的條件,就會發現是要跟i交換才對
01/19 13:53, 1F
我懂你的意思了 不過這個code是有一點問題的 在qsort(A,left,j-1); 會出ㄧ些問題應該是因為do while的原因 ※ 編輯: dumpling1234 (36.239.125.22), 01/19/2019 14:55:26
→
01/19 15:15, 7年前 , 2F
問題？
01/19 15:15, 2F
推
01/19 15:18, 7年前 , 3F
這個程式碼的if判斷是不是有點累贅，其實可以直接接swap就
01/19 15:18, 3F
→
01/19 15:18, 7年前 , 4F
好了?
01/19 15:18, 4F
推
01/19 15:31, 7年前 , 5F
Y是NP-hard，不是NP-C，因為沒證明Y屬於NP
01/19 15:31, 5F
推
01/19 15:32, 7年前 , 6F
你自己帶個例子進去就會知道選C會發生什麼事 直接是錯的
01/19 15:32, 6F
→
01/19 15:32, 7年前 , 7F
我在說(E)
01/19 15:32, 7F
→
01/19 15:35, 7年前 , 8F
然後你說的沒錯 pivot要和一個大於pivot的做交換，你do whi
01/19 15:35, 8F
→
01/19 15:35, 7年前 , 9F
le迴圈做完後i停的點會大於pivot，而j停的點會小於pivot
01/19 15:35, 9F
→
01/19 15:40, 7年前 , 10F
更正，上面的大於和小於應該是大於等於和小於等於
01/19 15:40, 10F
太少用do while了有點不太熟 感謝你的說明
推
01/19 21:45, 7年前 , 11F
16 (b) 是對的 你說的也是對的 這是 NPC 定義的一部分
01/19 21:45, 11F
不太懂你的意思 如果所有NP問題能polynomial reduce to NP Hard 那不是所有問題都是 NP complete了嗎? ※ 編輯: dumpling1234 (36.239.38.100), 01/20/2019 00:44:35 ※ 編輯: dumpling1234 (36.239.38.100), 01/20/2019 02:16:22
推
01/20 12:18, 7年前 , 12F
你要不要把你的 NPC 定義寫出來 我才知道要怎麼解釋
01/20 12:18, 12F
我好像有點感覺了所以NP-complete 跟 NP hard 差異只在是不是屬於NP而已嗎? ※ 編輯: dumpling1234 (36.239.125.22), 01/20/2019 14:48:21
推
01/20 22:00, 7年前 , 13F
是的
01/20 22:00, 13F
推
01/21 01:12, 7年前 , 14F
16. abce 17.abe
01/21 01:12, 14F
→
01/21 01:13, 7年前 , 15F
01/21 01:13, 15F
推
01/21 09:14, 7年前 , 16F
不好意思 想請問第三題你畫的反例
01/21 09:14, 16F
→
01/21 09:14, 7年前 , 17F
題目上說unique lightest edge應該是指只有唯一的最
01/21 09:14, 17F
→
01/21 09:14, 7年前 , 18F
小權重
01/21 09:14, 18F
→
01/21 09:16, 7年前 , 19F
覺得題目敘述跟你畫的圖應該不一樣
01/21 09:16, 19F
推
01/21 10:50, 7年前 , 20F
3的SB中央考好幾次了，考這種有爭議的真的...
01/21 10:50, 20F
→
01/21 10:50, 7年前 , 21F
他應該是說cycle中有唯一最小邊但不保證是圖中最小，所以
01/21 10:50, 21F
→
01/21 10:50, 7年前 , 22F
不一定在MST，要選false，如果改成最大必不在MST中就要
01/21 10:50, 22F
→
01/21 10:50, 7年前 , 23F
選true
01/21 10:50, 23F
推
01/22 14:03, 7年前 , 24F
我直接看最後的兩行Qsort 判斷所以選和J換 雖然懂一樓
01/22 14:03, 24F
→
01/22 14:03, 7年前 , 25F
的意思 但是還是覺得這題目很雷 所以請問這題有送分嗎
01/22 14:03, 25F
推
01/22 22:43, 7年前 , 26F
S大 了解了 謝謝！
01/22 22:43, 26F
推
01/23 22:48, 7年前 , 27F
想請問18題(e)不是寫反了嗎為什麼能選？
01/23 22:48, 27F
→
01/23 22:51, 7年前 , 28F
沒事我看錯了
01/23 22:51, 28F
推
01/30 17:03, 6年前 , 29F
弱弱問一下第19題是不是不能選C啊感覺跟0/1背包問題的
01/30 17:03, 29F
→
01/30 17:04, 6年前 , 30F
負重w是同一個道理，不知道觀念有沒有誤?
01/30 17:04, 30F
推
01/30 18:04, 6年前 , 31F
但他選項寫 pseudo 所以還是要選 （定義
01/30 18:04, 31F
推
01/30 21:05, 6年前 , 32F
原來是這樣~謝謝e大~
01/30 21:05, 32F
‣ 更多 dumpling1234 的文章
文章代碼(AID): #1SGhcjfC (Grad-ProbAsk)
‣ 更多 dumpling1234 的文章
文章代碼(AID): #1SGhcjfC (Grad-ProbAsk)