推 NCTUCKCurry: 第14題我的想法是 可以把n-tuple optimization probl 12/23 20:32
→ NCTUCKCurry: em修改成decision version 也就是一個數x是否存在n個 12/23 20:32
→ NCTUCKCurry: 正整數相乘=x 且這n個數相加小於等於k 12/23 20:32
→ NCTUCKCurry: 給定任一個prime number problem 的instance x，可以 12/23 20:35
→ NCTUCKCurry: reduce成n-tuple的instance，也就是是否存在x等於n個 12/23 20:35
→ NCTUCKCurry: 正整數相乘，且這n個正整數小於等於K，K取x+n-1 12/23 20:35
推 NCTUCKCurry: 上面講的有點瑕疵抱歉 應該是這樣 12/23 20:46
→ NCTUCKCurry: 給定一個prime number problem的instance x，reduce 12/23 20:46
→ NCTUCKCurry: 成一個decision version的n-tuple optimization prob 12/23 20:46
→ NCTUCKCurry: lem，也就是是否存在n個正整數相乘等於x，且這n個數 12/23 20:46
→ NCTUCKCurry: 相加小於等於K，這邊只要n取2 然後取K取x，這樣reduc 12/23 20:46
→ NCTUCKCurry: e完以後，如果x是prime的話，一定找不到兩個數相乘等 12/23 20:46
→ NCTUCKCurry: 於x且相加小於等於x，也就是說n-tuple那邊會是false 12/23 20:46
→ NCTUCKCurry: ；相反的，如果x不是prime，則必定可以找到兩個數字 12/23 20:46
→ NCTUCKCurry: 相乘等於x且相加小於x，也就是n-tuple那邊是true 12/23 20:46
→ foogty: 先感謝N大的回覆，想請問最後一句x不是質數的話則必有兩 12/23 21:34
→ foogty: 數相加小於x且相乘等於x這句該怎麼證明呢？ 12/23 21:34
→ BusterButter: 第四題方向大概是這樣，有一些細節我沒寫很詳細 12/23 21:45
→ foogty: 感謝b大，我再研究一下 12/23 21:52
推 BusterButter: 你的問題應該是你取了n進位，你的bucket數應該是n而 12/23 21:56
→ BusterButter: 不是2^(lglgn*lgn), 改掉你就得到O(nlglgn)了 12/23 21:56
→ foogty: 感謝b大 看了你的圖我懂了！！ 12/23 21:57
→ BusterButter: 我覺得樓上N大把prime那題弄得有點複雜XD, 令x為我 12/23 22:20
→ BusterButter: 們要test的prime, 設定n = 2, 看他的最小兩數和是不 12/23 22:20
→ BusterButter: 是x+1。因為我們一定找得到兩個數相乘是x（x和1）, 12/23 22:20
→ BusterButter: 假如最小兩數和是x+1，那他就是質數 12/23 22:20
→ BusterButter: （理由是，譬如說觀察12=1*12=2*6=3*4，兩數和是不 12/23 22:20
→ BusterButter: 是越來越小，如果是質數那他找到的兩數和只能有x+1 12/23 22:20
→ BusterButter: ）相反如果最小總數和小於x+1，那x就不是prime 12/23 22:20
推 NCTUCKCurry: 不是質數的話 只要隨便找一個正因數分解x=ab，且a和b 12/23 22:27
→ NCTUCKCurry: 都不是1的話，相加起來一定小於x，算是蠻直觀的吧， 12/23 22:27
→ NCTUCKCurry: 剛剛想了一下要怎麼嚴謹的證明這件事都沒有成功QQ 12/23 22:27
→ foogty: 感謝樓上兩位大大 我懂了 12/23 22:28
→ NCTUCKCurry: B大跟我的想法一模一樣 感謝補充 我只是想說要寫的嚴 12/23 22:28
→ NCTUCKCurry: 謹一點LOL 12/23 22:28