算法第三章上机实践报告

1. 实践报告任选一题进行分析。内容包括：

1.1 问题描述

7-4 编辑距离问题 (25 分)

设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

结尾无空行

输出样例:

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

5

结尾无空行

(本题主要意思是有增删改三种只针对一个字符的操作，输出由字符串A转变到字符串B需要的最小的总操作次数)

1.2 算法描述

本题主要意思是有增删改三种只针对一个字符的操作，输出由字符串A转变到字符串B需要的最小的总操作次数。由题意可得，字符串A到字符串B的最小总操作次数可以由字符A中的前n-1个字符转变到字符串B的前m-1个字符的最小总操作次数决定，以此类推，我们可以发现编辑距离问题最优解包含着其子问题的最优解，所以该问题可用动态规划算法求解。

用填表法进行分析：

a[i][j]表示的意思是A字符串中前i个字符转变成B字符串中的前j个字符所需要的最小操作次数。

当A为空字符时，a[0][j]=j；

当B为空字符时，a[i][0]=i；

所以把空字符加入表格中的行和列，得到一个初始化的表格，再进行表格填写。

我们可以发现a[2][2]中填的数依赖于它上边的数a[1][2]（a[i-1][j]）和它左边的数a[2][1]（a[i][j-1]）以及左上的数a[1][1]（a[i-1][j-1]），取上边的数+1和左边+1（即再做一次追加的操作）和左上+1（即修改最后一个字符）的数中的最小值,a[2][2]=min(a[1][2],a[2][1],a[1][1])+1。a[2][1]中填的数依赖于a[1][0]，因为此时字符串最后一个字符相等，所以a[2][1]=a[1][0]。可以发现其他空格也是这种规律，填成下表：

1.3 问题求解：

1.1.1 根据最优子结构性质，列出递归方程式:

a[i][j]= 

0   ,   i=j=0;

 a[i-1][j-1]  ,A[i]==B[j]

min(a[i-1][j-1],min(a[i-1][j],a[i][j-1]))+1    ，A[i]!=B[j]

1.1.2 给出填表法中表的维度、填表范围和填表顺序。

涉及到两个字符串之间的转换，要求表的维度是二维；因为每个空格都依赖于其左上、左边、上面的三个空格，所以表格要全填，填表顺序按循环是从左到右从上到下，填到最后的空格a[i][j]就是最终的答案。

1.1.3 分析该算法的时间和空间复杂度

填表的的代码如下：

for(i=0;i<=len1;i++)a[i][0]=i;

for(j=0;j<=len2;j++)a[0][j]=j;

for(i=1;i<=len1;i++)

{

for(j=1;j<=len2;j++)

{

if(s1[i-1]==s2[j-1])a[i][j]=a[i-1][j-1];

else a[i][j]=min(a[i-1][j-1],min(a[i-1][j],a[i][j-1]))+1;

}

}

该算法要用到二重循环，所以时间复杂度为O（n^2）,要用到一个二维辅助数组，所以空间复杂度为S（n^2）.

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

通过这次实验，我懂得了不止要会写代码，还要将细节考虑清楚，能讲清楚自己的思路。同时做题的时候要先整理思路，写出递归方程和边界条件来作为代码的依据。

2. 你对动态规划算法的理解和体会

通过这次实践，我对动态规划有了更深的理解，也懂得了动态规划解题的方便。在做题的时候,因为动态规划与前面所学的分治法有点像但是不同点是动态规划是自底向上，分治法是从上到下，没区分清楚导致做题的时候总往分治法那边偏离。多做了几题动态规划后发现，动态规划中问题的最优解与子问题的最优解的依赖关系是不同于分治法的。最后运用填表法做题时要充分结合依赖关系来判断表的维度、填表的范围、填表顺序等，才能更好地做题。