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