作者foogty (1234)
看板Grad-ProbAsk
标题[理工] 清大计科 100(4) 101(14)
时间Thu Dec 23 20:16:17 2021
1 清大100第四题
https://i.imgur.com/E4Vh4wr.jpg
有查过解答知道是用radix sort来做，但尝试跟着写一遍却卡住了，下面是我的过程，最後
的求出来的结果好像怪怪的，想问问我的问题出在哪里
https://i.imgur.com/YVxuczG.jpg
2 清大101第14题
https://i.imgur.com/BoIRNn2.jpg
这题我没查到解答，不太清楚我的想法是不是正确
下面是我尝试解得过程
https://i.imgur.com/rMNUW0d.jpg
我在推n-tuple的解是prime number problem的解时不知道该怎麽下手
感谢各位
----
Sent from
BePTT on my Samsung SM-A205GN
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 49.216.165.68 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1640261779.A.128.html
1F：推 NCTUCKCurry: 第14题我的想法是 可以把n-tuple optimization probl 12/23 20:32
2F：→ NCTUCKCurry: em修改成decision version 也就是一个数x是否存在n个 12/23 20:32
3F：→ NCTUCKCurry: 正整数相乘=x 且这n个数相加小於等於k 12/23 20:32
4F：→ NCTUCKCurry: 给定任一个prime number problem 的instance x，可以 12/23 20:35
5F：→ NCTUCKCurry: reduce成n-tuple的instance，也就是是否存在x等於n个 12/23 20:35
6F：→ NCTUCKCurry: 正整数相乘，且这n个正整数小於等於K，K取x+n-1 12/23 20:35
7F：推 NCTUCKCurry: 上面讲的有点瑕疵抱歉 应该是这样 12/23 20:46
8F：→ NCTUCKCurry: 给定一个prime number problem的instance x，reduce 12/23 20:46
9F：→ NCTUCKCurry: 成一个decision version的n-tuple optimization prob 12/23 20:46
10F：→ NCTUCKCurry: lem，也就是是否存在n个正整数相乘等於x，且这n个数 12/23 20:46
11F：→ NCTUCKCurry: 相加小於等於K，这边只要n取2 然後取K取x，这样reduc 12/23 20:46
12F：→ NCTUCKCurry: e完以後，如果x是prime的话，一定找不到两个数相乘等 12/23 20:46
13F：→ NCTUCKCurry: 於x且相加小於等於x，也就是说n-tuple那边会是false 12/23 20:46
14F：→ NCTUCKCurry: ；相反的，如果x不是prime，则必定可以找到两个数字 12/23 20:46
15F：→ NCTUCKCurry: 相乘等於x且相加小於x，也就是n-tuple那边是true 12/23 20:46
16F：→ foogty: 先感谢N大的回覆，想请问最後一句x不是质数的话则必有两 12/23 21:34
17F：→ foogty: 数相加小於x且相乘等於x这句该怎麽证明呢？ 12/23 21:34
19F：→ BusterButter: 第四题方向大概是这样，有一些细节我没写很详细 12/23 21:45
20F：→ foogty: 感谢b大，我再研究一下 12/23 21:52
21F：推 BusterButter: 你的问题应该是你取了n进位，你的bucket数应该是n而 12/23 21:56
22F：→ BusterButter: 不是2^(lglgn*lgn), 改掉你就得到O(nlglgn)了 12/23 21:56
23F：→ foogty: 感谢b大 看了你的图我懂了！！ 12/23 21:57
24F：→ BusterButter: 我觉得楼上N大把prime那题弄得有点复杂XD, 令x为我 12/23 22:20
25F：→ BusterButter: 们要test的prime, 设定n = 2, 看他的最小两数和是不 12/23 22:20
26F：→ BusterButter: 是x+1。因为我们一定找得到两个数相乘是x（x和1）, 12/23 22:20
27F：→ BusterButter: 假如最小两数和是x+1，那他就是质数 12/23 22:20
28F：→ BusterButter: （理由是，譬如说观察12=1*12=2*6=3*4，两数和是不 12/23 22:20
29F：→ BusterButter: 是越来越小，如果是质数那他找到的两数和只能有x+1 12/23 22:20
30F：→ BusterButter: ）相反如果最小总数和小於x+1，那x就不是prime 12/23 22:20
31F：推 NCTUCKCurry: 不是质数的话 只要随便找一个正因数分解x=ab，且a和b 12/23 22:27
32F：→ NCTUCKCurry: 都不是1的话，相加起来一定小於x，算是蛮直观的吧， 12/23 22:27
33F：→ NCTUCKCurry: 刚刚想了一下要怎麽严谨的证明这件事都没有成功QQ 12/23 22:27
34F：→ foogty: 感谢楼上两位大大 我懂了 12/23 22:28
35F：→ NCTUCKCurry: B大跟我的想法一模一样 感谢补充 我只是想说要写的严 12/23 22:28
36F：→ NCTUCKCurry: 谨一点LOL 12/23 22:28