[理工][演算法]清大104計科

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間7年前 (2016/12/23 22:20), 編輯推噓4(4推 0噓 24→)
留言28則, 5人參與, 最新討論串1/1
想請問11和12題要怎麼寫? http://i.imgur.com/ylfClGU.jpg
http://i.imgur.com/o7vczhs.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.235.130.102 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482502804.A.2BF.html
推
12/23 22:24, , 1F
11題我猜題目沒有拍好？
12/23 22:24, 1F
→
12/23 22:25, , 2F
12題，sum要等於m，代表這些integer的range介於1~m
12/23 22:25, 2F
→
12/23 22:25, , 3F
用counting sort先排序，需要0(n)
12/23 22:25, 3F
→
12/23 22:29, , 4F
然後第一個數先跟最後一個數相加，如果超過m就捨棄最後
12/23 22:29, 4F
→
12/23 22:30, , 5F
一個數，然後換第一個數先跟倒數第二個相加，超過m的話
12/23 22:30, 5F
→
12/23 22:30, , 6F
再捨棄，一直找到<=m的，等於m的話就找到了，<m的話就
12/23 22:30, 6F
→
12/23 22:31, , 7F
第二個數跟剛剛還沒捨棄的倒數第x個數，依此類推
12/23 22:31, 7F
→
12/23 22:32, , 8F
阿不對，我想錯了，剛剛那段全部都錯XD
12/23 22:32, 8F
→
12/23 22:35, , 9F
12(b)因為m要k=log_2(m)個bit去存他，佔的空間是k
12/23 22:35, 9F
→
12/23 22:36, , 10F
所以真正的input size是k，而m=2^k，故O(mn)=O(n*2^k)
12/23 22:36, 10F
→
12/23 22:38, , 11F
這個叫做pseudo-polynomial time algorithm
12/23 22:38, 11F
→
12/23 22:38, , 12F
這個問題可以叫做weakly-NP-complete
12/23 22:38, 12F
→
12/23 22:41, , 13F
12(a)我好像想到了，一樣counting sort
12/23 22:41, 13F
→
12/23 22:42, , 14F
for i=1 to n
12/23 22:42, 14F
→
12/23 22:43, , 15F
for j=2 to n
12/23 22:43, 15F
→
12/23 22:43, , 16F
if a[i]+a[j]>m:
12/23 22:43, 16F
→
12/23 22:43, , 17F
break;
12/23 22:43, 17F
→
12/23 22:44, , 18F
我又打錯了QQ
12/23 22:44, 18F
推
12/23 22:48, , 19F
不能用counting sort，題目沒給數字的上限，只說n
12/23 22:48, 19F
→
12/23 22:48, , 20F
個數字，這要用DP吧，用m*n的布林矩陣，[m,n]=[m,n-
12/23 22:48, 20F
→
12/23 22:48, , 21F
1]or[m-a_n,n-1]
12/23 22:48, 21F
→
12/23 22:50, , 22F
12/23 22:50, 22F
→
12/23 22:51, , 23F
阿對吼，所以真的整個想錯了，抱歉
12/23 22:51, 23F
→
12/23 23:16, , 24F
11題題目真的只有這樣
12/23 23:16, 24F
→
12/23 23:26, , 25F
11(a)感覺可以用decision tree，4個數，有4!個leaf
12/23 23:26, 25F
→
12/23 23:28, , 26F
樹高為log2(4!)，最少comparison次數為log_2(4!)>4
12/23 23:28, 26F
推
12/30 21:37, , 27F
11題真的怪 感覺要五次啊？
12/30 21:37, 27F
推
02/08 21:33, , 28F
這是不是subset sum problem?
02/08 21:33, 28F
‣ 更多 h9638512 的文章
文章代碼(AID): #1ONJAKA_ (Grad-ProbAsk)