作者leexu3 (LEE)
看板Grad-ProbAsk
標題[理工] 請益 演算法兩題
時間Thu Jan 4 17:19:41 2018
請益各位大神～～
兩題 成大演算法
成大的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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1515057584.A.E75.html
1F：推 andy6666: 第一題用數學歸納法證明 01/05 13:29
2F：推 andy6666: the edit distance problem可以視為對於兩個要比較的字 01/05 13:32
3F：→ andy6666: 串A B找LCS 之後對於B有但A沒有的字元則新增 反之則刪 01/05 13:32
4F：→ andy6666: 除 01/05 13:32
5F：推 andy6666: 一樣的不處理 01/05 14:15
6F：推 pp891190007: A大 我也想問第一題 第一題數歸 1,2還可以求但n怎麼 01/05 15:20
7F：→ pp891190007: 證，而且還要寫code = = 01/05 15:21
8F：推 ShenJing: 我另回一篇，還請各位大大們指點一下我的想法 01/05 19:11
10F：→ andy6666: 2 顯然拿掉任何一個都可以用tromino拼出來 那如果延伸 01/05 22:57
11F：→ andy6666: 到4個 01/05 22:57
12F：→ andy6666: 假設一個空缺是在我圖上畫的那裡 那其他的部分我可以 01/05 22:58
13F：→ andy6666: 假定是由三個有缺的2*2的加上一個tromino來拼 01/05 22:58
14F：→ andy6666: 概念大概是這樣 以此做數學歸納 01/05 22:58
15F：→ andy6666: code的話看S大的回文吧 01/05 22:59
16F：推 andy6666: 然後第二題我搞錯意思了 抱歉誤導 01/05 23:02