算法第3章上机实践报告

1、实践题目：

7-3 编辑距离问题（30 分）

2、问题描述：

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

输入格式:

第一行是字符串A，文件的第二行是字符串B。

提示：字符串长度不超过2000个字符。

输出格式:

输出编辑距离d(A,B)

输入样例:

在这里给出一组输入。例如：

fxpimu
xwrs

输出样例:

在这里给出相应的输出。例如：

3、算法描述：

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 string A,B;
 6 int n1,n2;
 7 int n[2002][2002];
 8 
 9 int main()
10 {
11     getline(cin,A);
12     getline(cin,B);
13     int a=A.length();
14     int b=B.length();
15     for(int i=1;i<=a;i++)
16     {
17         n[i][0]=i;
18     }
19     for(int j=1;j<=b;j++)
20     {
21         n[0][j]=j;
22     }
23     for(int i=1;i<=a;i++)
24     {
25         for(int j=1;j<=b;j++)
26         {
27             if(A[i-1]==B[j-1])
28             {
29                 n[i][j]=n[i-1][j-1];
30             }
31             else
32             {
33                 n[i][j]=min(min(n[i-1][j]+1,n[i][j-1]+1),n[i-1][j-1]+1);
34             }
35         }
36     }
37     cout<<n[a][b];
38     return 0;
39 }

View Code

通过i和j两个指针在A、B两个数组中滑动，依次比较AB数组是否对齐。最后在实际中就是看n[i-1][j]、n[i][j-1]、n[i-1][j-1]三种情况的最优解，同时需加一补足。

4、算法时间及空间复杂度分析（要有分析过程）：

代码中最多有两层for循环，时间复杂度为n（n^2）。

同时新建了二维数组来存放数据，空间复杂度也为n（n^2）。

5、心得体会（对本次实践收获及疑惑进行总结）：

此次实验更多地让我理解了在上手写代码前的思考，之前的一些题目我一般都是上手就开始写，一边写一边思考。但是在这道题上我只能先思考好了，将大概思路列出来，才能上手写代码。一开始我认为这个题目的主要问题在于如何判断什么时候使用删除、修改、添加的操作，实际上这道题是对于两个字符串不同的比较，重点在于对其长度不同的补足，以及最优化修改。同时，这道题让我发现min不能同时比较三个数据，只能比较两个数据，我在使用中大量报错才发现。