《序关系计数问题-编辑距离问题-最小m段问题-正则表达式匹配问题(DOC)(DOC 15页)》由会员分享，可在线阅读，更多相关《序关系计数问题-编辑距离问题-最小m段问题-正则表达式匹配问题(DOC)(DOC 15页)（18页珍藏版）》请在金锄头文库上搜索。
1、一、算法实现题3-3 序关系计数问题*问题描述：用关系“”和“=”将3个数A，B和C依序排列时有13种不同的序关系：A=B=C，A=BC，AB=C，ABC，ACB，A=CB，BA=C，BAC，BCA，B=CA，CA=B，CAB，CBA将n个数（1n50）依序排列时有多少种序关系。*算法设计：计算出将n个数（1n50）依序排列时有多少种序关系。*数据输入：由文件input.txt提供输入数据。文件只有一行，提供一个数n。*结果输出：将找到的序关系数输出到文件output.txt的第1行。 输入文件示例 输出文件示例 input.txt output.txt 3 131、解题说明 本题具有最优子结
2、构特性，并有重叠子问题性质，因此可以采用动态规划来求解。 我们可以采用一个二维数组Ai,j来表示用j个“i-1的时候，即“”号的个数多于需要的符号总数时，定义边界条件Ai,j=0；2）当没有“”号的时候，即全部为“=”号，序关系排列只有一种，即Ai,0=1,i=1n。3）一般情况时，当用j个“”号来连接i个数的时候，则有如下形式：S1S2Sj+1,即Sk（1kj+1）中的各个数字之间用“”号相连，但不一定直接相邻，彼此之间可能有其它数用“=”号和它们分别相连。对于Ai,j，考虑在i-1个数的基础上增加一个数x的情形。则可以分为两种情况：当原有i-1个数已有j个“”号相连，则此时x只能以“=”号
3、与i-1个数字相连，并且有j+1种位置选择。原有排序为Ai-1,j,此时共有(j+1)* Ai-1,j种不同的排列。当原有i-1个数已有j-1个“”号相连，则此时x只能以“”号与i-1个数字相连，同样有j+1种位置选择。原有排序为Ai-1,j-1，此时共有(j+1)* Ai-1,j-1种不同的排列。因此Ai,j的递归表达式为：Ai,j=(j+1)*( Ai-1,j+ Ai-1,j-1)这种表达式已经经过了简化，因此计算Ai,j的时候只用到第i-1行中的2个数字，只需保存第i-1行就可以了。 在写程序的时候，没必要真的用一个二维数组来存储数组，可以用for循环来控制行数，而用A这个一维数组来存储
4、上一行每列的数据，提高了算法的空间效率。2、程序代码#include#includeusing namespace std;int order(int n,int *ord)int i,j,total=0; ord0=1; /只有一个数时for(i=1;i=n-1;i+) /赋初值ordi=0;for(i=2;i=1;j-) /j表示号的个数,j取1(i-1)ordj=(j+1)*(ordj-1+ordj); /递推公式for(j=0;jn; /从文件读入 int *ord=new intn; total=order(n,ord); outtotalendl; /输出到文件 return 0;
5、3、运行截图 1）程序所在文件夹有input.txt，运行完成后产生了output.txt 2）设定输入为3 3）运行程序后，打开ouput.txt，输出结果为13。二、算法实现题3-5 编辑距离问题*问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符B。这里所说的字符操作包括：（1） 删除一个字符（2） 插入一个字符（3） 将一个字符改为另一个字符将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A,B）。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d（A,B）。 *算法设计：对于给定的字符串A和字符串B，计算其编辑距离
6、d(A,B)。 *数据输入：由文件input.txt提供输入数据。文件的第1行是字符串A，文件的第2行是字符串B。*结果输出：将编辑距离d（A,B）输出到文件output.txt的第1行。 输入文件示例 输出文件实例 input.txt output.txt fxpimu 5 xwrs 1、解题说明输入两个字符串a和b，定义二维数组来保存编辑距离，即disij=d(a0:i-1,b0:j-1)。 考虑两种特殊情况，若字符串a长度为m，b为空串，则d（a,b）=m，即disi0=i;若字符串b长度为m，a为空串，则d（a,b）=n.即dis0j=j；当两个字符串长度为1时，若a=b，则d(a,b
7、)=0;若a!=b,则d(a,b)=1。考虑一般情况，从字符串a0:i到字符串b0:j的变换，可以分为三种情况:1)a0:i-1到字符串b0:j-1已经转换好，那么只需考虑两个字符ai和bj，则在原来的基础上只需要d(ai，bj)次操作，即disi-1j-1+ d(ai，bj);2)a0:i-1到字符串b0:j已经转换好,则需删除ai,需要在原来基础上加1，即disi-1j+1;3) a0:i到字符串b0:j-1已经转换好,则需删除bj,需要在原来基础上加1，即disij-1+1;综上所述，三种情况中取最小值，disij可以递归的计算如下：disij=min(disi-1j-1+d(aibj)
8、,disi-1j+1,disij-1+1)。初始化后，dis二维数组如下：2、程序代码#include#include#includeusing namespace std;#define Max 20int disMaxMax;int min(int a,int b,int c) /最小值函数 int d=(ab? b:a);return cd? d:c;int distance(string a,string b) /编辑距离函数int i,j;int disab; /存字符ai到字符bj的编辑距离for(i=0;i=a.length();i+) / 初始条件disi0=i; for(i=
9、0;i=b.length();i+) / 初始条件dis0i=i;for(i=1;i=a.length();i+) for(j=1;jstr1str2; /从文件读入outdistance(str1,str2)i的时候，划分不存在；考虑一般情况，i个整数划分为j段，则solveij=minmax(solvekj-1,lastpart)。其中，j-1=k=i-1 ,lastpart=datak+1+datak+2+datai。2、程序代码#include #includeusing namespace std; void main() int n,m,t,min,lastpart; ifstream in(input.txt);ofstream out(output.txt);innm; int *data=new int n+1; for(int i=1;id
