作者dumpling1234 (dumpling)
看板Grad-ProbAsk
標題Re: [理工] 107 中央 資結演算法 對答案
時間Sat Jan 19 13:46:19 2019
※ 引述《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547876781.A.A4C.html
1F：推 waynetooni: 你看第12題出do-while的條件,就會發現是要跟i交換才對 01/19 13:53
我懂你的意思了 不過這個code是有一點問題的 在qsort(A,left,j-1);
會出ㄧ些問題應該是因為do while的原因
※ 編輯: dumpling1234 (36.239.125.22), 01/19/2019 14:55:26
2F：→ school4303: 問題？ 01/19 15:15
3F：推 sooge: 這個程式碼的if判斷是不是有點累贅，其實可以直接接swap就 01/19 15:18
4F：→ sooge: 好了? 01/19 15:18
5F：推 cow5566bad: Y是NP-hard，不是NP-C，因為沒證明Y屬於NP 01/19 15:31
6F：推 sooge: 你自己帶個例子進去就會知道選C會發生什麼事 直接是錯的 01/19 15:32
7F：→ cow5566bad: 我在說(E) 01/19 15:32
8F：→ sooge: 然後你說的沒錯 pivot要和一個大於pivot的做交換，你do whi 01/19 15:35
9F：→ sooge: le迴圈做完後i停的點會大於pivot，而j停的點會小於pivot 01/19 15:35
10F：→ sooge: 更正，上面的大於和小於應該是大於等於和小於等於 01/19 15:40
太少用do while了有點不太熟 感謝你的說明
11F：推 FRAXIS: 16 (b) 是對的 你說的也是對的 這是 NPC 定義的一部分 01/19 21:45
不太懂你的意思 如果所有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
12F：推 FRAXIS: 你要不要把你的 NPC 定義寫出來 我才知道要怎麼解釋 01/20 12:18
我好像有點感覺了所以NP-complete 跟 NP hard 差異只在是不是屬於NP而已嗎?
※ 編輯: dumpling1234 (36.239.125.22), 01/20/2019 14:48:21
13F：推 FRAXIS: 是的 01/20 22:00
14F：推 skyHuan: 16. abce 17.abe 01/21 01:12
16F：推 kurtis6741: 不好意思 想請問第三題你畫的反例 01/21 09:14
17F：→ kurtis6741: 題目上說unique lightest edge應該是指只有唯一的最 01/21 09:14
18F：→ kurtis6741: 小權重 01/21 09:14
19F：→ kurtis6741: 覺得題目敘述跟你畫的圖應該不一樣 01/21 09:16
20F：推 skyHuan: 3的SB中央考好幾次了，考這種有爭議的真的... 01/21 10:50
21F：→ skyHuan: 他應該是說cycle中有唯一最小邊但不保證是圖中最小，所以 01/21 10:50
22F：→ skyHuan: 不一定在MST，要選false，如果改成最大必不在MST中就要 01/21 10:50
23F：→ skyHuan: 選true 01/21 10:50
24F：推 jim0611tw: 我直接看最後的兩行Qsort 判斷所以選和J換 雖然懂一樓 01/22 14:03
25F：→ jim0611tw: 的意思 但是還是覺得這題目很雷 所以請問這題有送分嗎 01/22 14:03
26F：推 kurtis6741: S大 了解了 謝謝！ 01/22 22:43
27F：推 bmpss92196: 想請問18題(e)不是寫反了嗎為什麼能選？ 01/23 22:48
28F：→ bmpss92196: 沒事我看錯了 01/23 22:51
29F：推 yunghan15: 弱弱問一下第19題是不是不能選C啊感覺跟0/1背包問題的 01/30 17:03
30F：→ yunghan15: 負重w是同一個道理，不知道觀念有沒有誤? 01/30 17:04
31F：推 ekids1234: 但他選項寫 pseudo 所以還是要選 （定義 01/30 18:04
32F：推 yunghan15: 原來是這樣~謝謝e大~ 01/30 21:05