Java教程

算法第三章上机实验报告

本文主要是介绍算法第三章上机实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

1.2 算法描述

首先的想法是,从两个字符串的首位置开始比较。
(1)如果两个字符串的首位置字母相同,那么递归比较剩下的字符串
(2)如果两个字符串的首位置字母不相同,那么对首字母进行删除、插入、或者替换操作,再递归处理后面的部分。
这样的话会有大量重复计算,不如直接用动态规划,开一个新的数组记录子问题的最优解,一步步找到答案。

用op[2010][2010]来存储结果,op[i][j]表示a的子串(下标从0到i)转化为b的子串(下标从0到j)需要的操作次数,最后输出的答案就是op[lena][lenb]

1.3 问题求解:

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

op[i][0](i从0到lena)初始化为i,op[0][j](j从0到lenb)初始化为j。(因为当i或j行为0时,要想将a子串转化为b子串,只能全部增加或者全部删除)

初始化完毕之后:
(1)如果两个字符串的首位置字母相同,op[i][j]=op[i-1][j-1](不用进行额外操作,操作次数就是上一个子串的操作次数)
(2)如果两个字符串的首位置字母不相同:
删除:删除a子串的末尾,意味着op[i][j]=1+op[i-1][j]
插入:在a子串的末尾插入,意味着op[i][j]=1+op[i][j-1]
将一个字符改为另一个字符:意味着op[i][j]=1+op[i-1][j-1]
然后要找出这三种方案中的最小值,所以递归式如下:
image

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

标的维度:二维
填表范围:i从1到 lena(a字符串的长度),j从1到 lenb(b字符串的长度)
填表顺序:从左到右,从上到下填表。(因为填一个格子的时候要保证他的上面,左边,对角线的都填了)

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

时间复杂度:O(mn)(双重循环)
空间复杂度:O(mn)(额外开了个二维数组)

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

这道题一开始是不会的,想了很久都没想出来,后面上网看了别人解析。
我自己没想到的部分就是,当两个字母不等的时候,进行了三个操作之后可以先删除再+1,就是分为三种情况递归,然后选择操作数最小的那个。

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

首先,动态规划应该依赖于两个最重要的性质:最优子结构和重叠子问题。

判断一道题是否能用动态规划,首先判断它是否有最优子结构,就是说,他最终的问题的答案,是不是由一个个小问题的最优解逐步构造出的。然后要看是不是由重叠的子问题,这时候就需要用到一个备忘录记录之前已经计算过的数据,避免重复计算,保证了每个子问题只解一次。

其次,通过这段时间对动态规划的学习,我明白了动态规划算法最重要的就是填表和写递归式。要明确填表用何种方式填,填这个空的时候我需要旁边哪几个空的答案。递归式则需要我们根据题目建立递归关系,有了递归关系就可以愉快地写代码了!

这篇关于算法第三章上机实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!