pascal中级教程第八章动态规划

《pascal中级教程第八章动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章动态规划8.1字串距离源程序名blast.???（pas,c,cpp）可执行文件名blast.exe输入文件名blast.in输出文件名blast.out【问题描述】设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为”abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我扪定义字符串A1与B

2、1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。【输入】输入文件第一行为字符串A，第二行为字符串B。A、B均由小写字母组成且长度均不超过2000。第三行为一个整数K（1≤K≤100），表示空

3、格与其他字符的距离。【输出】输出文件仅一行包含一个整数，表示所求得字符串A、B的距离。【样例】blast.inblast.outcmc10snmn2【算法分析】字符串A和B的扩展串最大长度是A和B的长度之和。如字符串A为“abcbd”，字符串B为“bbcd”，它们的长度分别是la=5、lb=4，则它们的扩展串长度最大值为LA+LB=9，即A的扩展串的5个字符分别对应B的扩展串中的5个空格，相应B的扩展串的4个字符对应A的扩展串中的4个空格。例如下面是两个字符串的长度为9的扩展串：a□bc□b□d

4、□□b□□b□c□d而A和B的最短扩展串长度为la与lb的较大者，下面是A和B的长度最短的扩展串：abcbdb□bcd因此，两个字符串的等长扩展串的数量是非常大的，寻找最佳“匹配”（对应位置字符距离和最小）的任务十分繁重，用穷举法无法忍受，何况本题字符串长度达到2000，巨大的数据规模，势必启发我们必须寻求更有效的方法：动态规划。记为A串中A1到Ai的一个扩展串，为B串中B1到Bj的一个扩展串。这两个扩展串形成最佳匹配的条件是（1）长度一样；（2）

5、对应位置字符距离之和最小。首先分析扩展串与扩展串长度一样的构造方法。扩展串与扩展串可以从下列三种情况扩张成等长：（1）与为两个等长的扩展串，则在后加一空格，加字符Bj；（2）与为两个等长的扩展串，则在添加字符Ai，在

6、1,B2,…,Bj>后加一空格；（3）与为两个等长的扩展串，则在后添加字符Ai，在后添加字符Bj。其次，如何使扩展成等长的这两个扩展串为最佳匹配，即对应位置字符距离之和最小，其前提是上述三种扩展方法中，被扩展的三对等长的扩展串都应该是最佳匹配，以这三种扩展方法形成的等长扩展串(A1,A2,…,Ai>和也有三种不同情形，其中对应位置字符距离之和最小的是最佳匹配。为

7、了能量化上述的构造过程，引入记号g[i,j]为字符串A的子串A1,A2,…,Ai与字符串B的子串B1,B2,…,Bj的距离，也就是扩展串与扩展串是一个最佳匹配。则有下列状态转移方程：g[i,j]=Min{g[i-1,j]+k,g[i,j-1]+k,g[i-1,j-1]+}0≤i≤La0≤j≤Lb其中，k位字符与字符之间的距离；为字符ai与字符bi的距离。初始值：g[0,0]=0g[0,j]=j·kg[i,0]=i·k综上所述，本题的主要算法如下：（

8、1）数据结构vara,b:array[1..2000]ofbyte;{以ASCII码表示的字符串}g:array[0..2000,0..2000]oflongint;{各阶段的匹配距离}（2）读入字符串A、B，转换为ASCII码la:=0;lb:=0;whilenot(eoln(f))do{子串长度单元}begin{从文件中读入一行字符}read(f,c);inc(la);a[la]:=ord(c);end;readln(f);whilenot(eoln(f))dobeginread(f,c);