[理工] 清大計科 100(4) 101(14)
作者: foogty (夫葛踢) 2021-12-23 20:16:17
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的解時不知道該怎麼下手
感謝各位
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的解時不知道該怎麼下手
感謝各位
作者: NCTUCKCurry (CKNCTUCurry) 2021-12-23 20:32:00
第14題我的想法是 可以把n-tuple optimization problem修改成decision version 也就是一個數x是否存在n個正整數相乘=x 且這n個數相加小於等於k給定任一個prime number problem 的instance x，可以reduce成n-tuple的instance，也就是是否存在x等於n個正整數相乘，且這n個正整數小於等於K，K取x+n-1上面講的有點瑕疵抱歉 應該是這樣給定一個prime number problem的instance x，reduce成一個decision version的n-tuple optimization problem，也就是是否存在n個正整數相乘等於x，且這n個數相加小於等於K，這邊只要n取2 然後取K取x，這樣reduce完以後，如果x是prime的話，一定找不到兩個數相乘等於x且相加小於等於x，也就是說n-tuple那邊會是false；相反的，如果x不是prime，則必定可以找到兩個數字相乘等於x且相加小於x，也就是n-tuple那邊是true
作者: foogty (夫葛踢) 2021-12-23 21:34:00
先感謝N大的回覆，想請問最後一句x不是質數的話則必有兩數相加小於x且相乘等於x這句該怎麼證明呢？
作者: BusterButter (奶油巴斯特) 2021-12-23 21:45:00
作者: foogty (夫葛踢) 2021-12-23 21:52:00
感謝b大，我再研究一下
作者: BusterButter (奶油巴斯特) 2021-12-23 21:56:00
你的問題應該是你取了n進位，你的bucket數應該是n而不是2^(lglgn*lgn), 改掉你就得到O(nlglgn)了
作者: foogty (夫葛踢) 2021-12-23 21:57:00
感謝b大 看了你的圖我懂了！！
作者: BusterButter (奶油巴斯特) 2021-12-23 22:20:00
我覺得樓上N大把prime那題弄得有點複雜XD, 令x為我們要test的prime, 設定n = 2, 看他的最小兩數和是不是x+1。因為我們一定找得到兩個數相乘是x（x和1）,假如最小兩數和是x+1，那他就是質數（理由是，譬如說觀察12=1*12=2*6=3*4，兩數和是不是越來越小，如果是質數那他找到的兩數和只能有x+1）相反如果最小總數和小於x+1，那x就不是prime
作者: NCTUCKCurry (CKNCTUCurry) 2021-12-23 22:27:00
不是質數的話 只要隨便找一個正因數分解x=ab，且a和b都不是1的話，相加起來一定小於x，算是蠻直觀的吧，剛剛想了一下要怎麼嚴謹的證明這件事都沒有成功QQ
作者: foogty (夫葛踢) 2021-12-23 22:28:00
感謝樓上兩位大大 我懂了
作者: NCTUCKCurry (CKNCTUCurry) 2021-12-23 22:28:00
B大跟我的想法一模一樣 感謝補充 我只是想說要寫的嚴謹一點LOL