[理工] 請益 演算法兩題

看板Grad-ProbAsk作者 (LEE)時間8年前 (2018/01/04 17:19), 編輯推噓7(7推 0噓 9→)
留言16則, 3人參與, 8年前最新討論串1/1
請益各位大神～～ 兩題 成大演算法 成大的99年Checkboard https://imgur.com/a/rLdeR 1.寫不出code 雖然感覺很明顯對 ＝＝ 2.有找到反例 oxoo... xooo... oooo... ....... o=方格,x=挖掉的 成大103 https://imgur.com/a/iFpp4 Prove that "the longest increasing subsequence problem" can be reduced to "the edit distance problem" 兩個演算法我會 但不知道怎麼reduced 感覺就是有讀沒有通 想上來請益各位 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.255.120.145 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1515057584.A.E75.html
推
01/05 13:29, 8年前 , 1F
第一題用數學歸納法證明
01/05 13:29, 1F
推
01/05 13:32, 8年前 , 2F
the edit distance problem可以視為對於兩個要比較的字
01/05 13:32, 2F
→
01/05 13:32, 8年前 , 3F
串A B找LCS 之後對於B有但A沒有的字元則新增 反之則刪
01/05 13:32, 3F
→
01/05 13:32, 8年前 , 4F
除
01/05 13:32, 4F
推
01/05 14:15, 8年前 , 5F
一樣的不處理
01/05 14:15, 5F
推
01/05 15:20, 8年前 , 6F
A大 我也想問第一題 第一題數歸 1,2還可以求但n怎麼
01/05 15:20, 6F
→
01/05 15:21, 8年前 , 7F
證，而且還要寫code = =
01/05 15:21, 7F
推
01/05 19:11, 8年前 , 8F
我另回一篇，還請各位大大們指點一下我的想法
01/05 19:11, 8F
推
01/05 22:57, 8年前 , 9F
https://m.imgur.com/a/WJmvK 大致上是這樣證明 先從2*
01/05 22:57, 9F
→
01/05 22:57, 8年前 , 10F
2 顯然拿掉任何一個都可以用tromino拼出來 那如果延伸
01/05 22:57, 10F
→
01/05 22:57, 8年前 , 11F
到4個
01/05 22:57, 11F
→
01/05 22:58, 8年前 , 12F
假設一個空缺是在我圖上畫的那裡 那其他的部分我可以
01/05 22:58, 12F
→
01/05 22:58, 8年前 , 13F
假定是由三個有缺的2*2的加上一個tromino來拼
01/05 22:58, 13F
→
01/05 22:58, 8年前 , 14F
概念大概是這樣 以此做數學歸納
01/05 22:58, 14F
→
01/05 22:59, 8年前 , 15F
code的話看S大的回文吧
01/05 22:59, 15F
推
01/05 23:02, 8年前 , 16F
然後第二題我搞錯意思了 抱歉誤導
01/05 23:02, 16F
‣ 更多 leexu3 的文章
文章代碼(AID): #1QJV6mvr (Grad-ProbAsk)