0%

夏令营7.16总结

今天,我们主要是学习了两个方面的内容,分别是负二进制数,部分背包问题的补充(可见另一篇文章),最长公共子序列,以及有关调试方面的经验。

最长公共子序列:昨天学习了部分背包分体,就意味着我们已经进入到动态规划的学习当中了。

【题目】给定A,B两个字符串,若字符串C既是A的子序列,有时B的子序列,那么C最长为多少?(当A(B)去掉某一些字符,变成另一个字符串C,那么C就是A(B)的子序列)

【输入】

abxycz

xabycz

【输出】

(abycz)

【思路1】假如我们先在采用寻找子问题的方式,来解决这一个问题。如图,首先我们定位在A串的第一个字母a,这一个字母是可选可不选。若果不选,那么任务就变成了,求红色框内的最长公共子序列。那么如果是选,那就要寻找与它(a)相匹配的字母(位置必须大于等于它(a)的位置,且是离它(a)最近),那么任务就变成了,求蓝色框内的最长公共子序列。由于每一个字母都要找与之相匹配的字母,所以最好要预处理。

他不见了。

但是,如果这么办,明显不符和我们的思维常理(虽然这是可行的),这需要从后面向前推,很麻烦。其实,我们换个方向,道理还是一样的。如图:

他不见了。

【思路2】思路1的方法固然简单,单边起来较复杂,这就在于它要预处理,字母与字母的匹配问题,非常麻烦。

其实,我们可以用数组F[i][j]来表示A串1-i,B串1-j的最长公共子序列。如图,现在i=4(a[i]=’y’),j=3(b[j]=’b’),现在a[i]≠a[j],那么如思路一一样,子问题就成了红色框的(以’b’来说),以及蓝色框的(以’a’来说),即F[i-1][j],F[i][j-1]。

他不见了。

如果两个字母相等的话,除了上面几种情况以外,还有一种情况,那就是都被选上了,即F[i-1][j-1]+1的情况(如图黄色区域)。

他不见了。

总的来说,就是

【表格法】细心的同学不知有没有发现,这有点像表格,如图,蓝色的格子等于上一格,左边那一格的最大值,,而红色的格子等于上边,左边,坐上边+1的最大值。

他不见了。

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <fstream>
#include <string>
using namespace std;

ifstream fin("longest common subsequence.in");
ofstream fout("longest common subsequence.out");

#define maxn 1000

string x,y;
int F[maxn][maxn];

int main() {
fin >> x;
fin >> y;

x='#'+x;
y='$'+y;//再接下来的动态规划是,F[0]是边界,若字符串再以下标0为起点,会有所不便

for (int i=1; i!=x.size(); i++)
for (int j=1; j!=y.size(); j++){
F[i][j]=max(F[i-1][j],F[i][j-1]);//这是不相等的情况下

if (x[i]==y[j]) F[i][j]=max(F[i][j],F[i-1][j-1]+1); //这是相等的情况下
}

fout << F[x.size()-1][y.size()-1];//别忘了要减1
return 0;
}

调试:调试,是我每次编程最为头痛的事了,仅次于算法分析,但是,老师讲了调试的有关经验后,让我收益匪浅。

首先,编程技巧可以减少调试的用时,主要有一下几种:

① 二分查找定位错误点

② 静态查错是很重要的方法

③ 用文件输入输出

④ 调试时的盲点

  1. 读入(偶尔有输出)数据时的错误。

  2. “复制+粘贴”的错误。

  3. 下标变量出错。

而调试时,最有效的,就是打印中间信息法。其中,这也有几点技巧:

① 调试语句的位置最好明显一些,以便事后关闭。

② 打印一些相关的数据,给出适当的提示信息,可以比较清楚地查看信息。

③ 在输出前面应用一些if()条件,可以更加有选择性地输出特定的信息,做到精确调试。

④ 善于使用自己的调试函数。

⑤ 阅读XXX.out文件可以在集成中的多窗口中(如:freepascal或dev-cpp等),也可单独的notpad中。

⑥ 提交程序要注意“关闭”调试信息。

当然,最有效的,当然是用GDB了。在此,我就不在这详谈。

【感受】这两天,学习了不少内容,空闲时间需要好好消化一下,可以尝试坐一坐相关的题目(最好由易至难),这样,就更有效率了。

Thank you so much.