作者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/cn.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