作者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/cn.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