[理工] 清大計科 100(4) 101(14)

看板Grad-ProbAsk作者 (1234)時間2年前 (2021/12/23 20:16), 編輯推噓4(4推 0噓 32→)
留言36則, 3人參與, 2年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1640261779.A.128.html
推
12/23 20:32, 2年前 , 1F
第14題我的想法是 可以把n-tuple optimization probl
12/23 20:32, 1F
→
12/23 20:32, 2年前 , 2F
em修改成decision version 也就是一個數x是否存在n個
12/23 20:32, 2F
→
12/23 20:32, 2年前 , 3F
正整數相乘=x 且這n個數相加小於等於k
12/23 20:32, 3F
→
12/23 20:35, 2年前 , 4F
給定任一個prime number problem 的instance x，可以
12/23 20:35, 4F
→
12/23 20:35, 2年前 , 5F
reduce成n-tuple的instance，也就是是否存在x等於n個
12/23 20:35, 5F
→
12/23 20:35, 2年前 , 6F
正整數相乘，且這n個正整數小於等於K，K取x+n-1
12/23 20:35, 6F
推
12/23 20:46, 2年前 , 7F
上面講的有點瑕疵抱歉 應該是這樣
12/23 20:46, 7F
→
12/23 20:46, 2年前 , 8F
給定一個prime number problem的instance x，reduce
12/23 20:46, 8F
→
12/23 20:46, 2年前 , 9F
成一個decision version的n-tuple optimization prob
12/23 20:46, 9F
→
12/23 20:46, 2年前 , 10F
lem，也就是是否存在n個正整數相乘等於x，且這n個數
12/23 20:46, 10F
→
12/23 20:46, 2年前 , 11F
相加小於等於K，這邊只要n取2 然後取K取x，這樣reduc
12/23 20:46, 11F
→
12/23 20:46, 2年前 , 12F
e完以後，如果x是prime的話，一定找不到兩個數相乘等
12/23 20:46, 12F
→
12/23 20:46, 2年前 , 13F
於x且相加小於等於x，也就是說n-tuple那邊會是false
12/23 20:46, 13F
→
12/23 20:46, 2年前 , 14F
；相反的，如果x不是prime，則必定可以找到兩個數字
12/23 20:46, 14F
→
12/23 20:46, 2年前 , 15F
相乘等於x且相加小於x，也就是n-tuple那邊是true
12/23 20:46, 15F
→
12/23 21:34, 2年前 , 16F
先感謝N大的回覆，想請問最後一句x不是質數的話則必有兩
12/23 21:34, 16F
→
12/23 21:34, 2年前 , 17F
數相加小於x且相乘等於x這句該怎麼證明呢？
12/23 21:34, 17F
→
12/23 21:45, 2年前 , 18F
12/23 21:45, 18F
→
12/23 21:45, 2年前 , 19F
第四題方向大概是這樣，有一些細節我沒寫很詳細
12/23 21:45, 19F
→
12/23 21:52, 2年前 , 20F
感謝b大，我再研究一下
12/23 21:52, 20F
推
12/23 21:56, 2年前 , 21F
你的問題應該是你取了n進位，你的bucket數應該是n而
12/23 21:56, 21F
→
12/23 21:56, 2年前 , 22F
不是2^(lglgn*lgn), 改掉你就得到O(nlglgn)了
12/23 21:56, 22F
→
12/23 21:57, 2年前 , 23F
感謝b大 看了你的圖我懂了！！
12/23 21:57, 23F
→
12/23 22:20, 2年前 , 24F
我覺得樓上N大把prime那題弄得有點複雜XD, 令x為我
12/23 22:20, 24F
→
12/23 22:20, 2年前 , 25F
們要test的prime, 設定n = 2, 看他的最小兩數和是不
12/23 22:20, 25F
→
12/23 22:20, 2年前 , 26F
是x+1。因為我們一定找得到兩個數相乘是x（x和1）,
12/23 22:20, 26F
→
12/23 22:20, 2年前 , 27F
假如最小兩數和是x+1，那他就是質數
12/23 22:20, 27F
→
12/23 22:20, 2年前 , 28F
（理由是，譬如說觀察12=1*12=2*6=3*4，兩數和是不
12/23 22:20, 28F
→
12/23 22:20, 2年前 , 29F
是越來越小，如果是質數那他找到的兩數和只能有x+1
12/23 22:20, 29F
→
12/23 22:20, 2年前 , 30F
）相反如果最小總數和小於x+1，那x就不是prime
12/23 22:20, 30F
推
12/23 22:27, 2年前 , 31F
不是質數的話 只要隨便找一個正因數分解x=ab，且a和b
12/23 22:27, 31F
→
12/23 22:27, 2年前 , 32F
都不是1的話，相加起來一定小於x，算是蠻直觀的吧，
12/23 22:27, 32F
→
12/23 22:27, 2年前 , 33F
剛剛想了一下要怎麼嚴謹的證明這件事都沒有成功QQ
12/23 22:27, 33F
→
12/23 22:28, 2年前 , 34F
感謝樓上兩位大大 我懂了
12/23 22:28, 34F
→
12/23 22:28, 2年前 , 35F
B大跟我的想法一模一樣 感謝補充 我只是想說要寫的嚴
12/23 22:28, 35F
→
12/23 22:28, 2年前 , 36F
謹一點LOL
12/23 22:28, 36F
‣ 更多 foogty 的文章
文章代碼(AID): #1Xn6YJ4e (Grad-ProbAsk)