《序关系计数问题-编辑距离问题-最小m段问题-正则表达式匹配问题.doc》由会员分享，可在线阅读，更多相关《序关系计数问题-编辑距离问题-最小m段问题-正则表达式匹配问题.doc（15页珍藏版）》请在三一办公上搜索。
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; ifstre
10、am in(input.txt);ofstream out(output.txt);innm; int *data=new int n+1; for(int i=1;idatai; /*solveij代表从第一位到第i位数字分割成j段的最小子段和，此题要求的就是solvenm。*/int *solve=new int *n+1; /初始化二维数组for(int j=1;j=n;j+) solvej=new int m+1; solve11=data1; /初始化for(i=2;i=n;i+) for(j=1;ji) /分成的段数大于子段的个数break; else /处理一般情况 min=10
11、0000000; /min初始值为无穷大lastpart=datai; /第j个子段的和 for(int k=i-1;k=j-1;k-) /*考虑已将前k个数分成j-1段，并将后i-k个数作为第j段。 则k最小只能与段数j-1相等，最大为i-1。*/ t=solvekj-1lastpart?solvekj-1:lastpart; /* 取前j-1个子段和的最大值的最小值跟第j个子段和相比，取较大值。*/if(tmin) /更新最小值min=t; lastpart+=datak; /将第i段向左扩充一个数 solveij=min; outsolvenmendl; 3、运行截图(1)input.t
12、xt(2)output.txt (3)文件夹截图 四、算法实现题3-14 正则表达式匹配问题1、题目*问题描述：许多操作系统采用正则表达式实现文件匹配功能。一种简单的正则表达式由英文字母、数字及通配符“*”和“？”组成。“？”代表任意一个字符，“*”则可以代表任意多个字符。现要用正则表达式对部分文件进行操作。试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。所找出的正则表达式的长度还应是最短的。*算法设计：对于给定的待操作文件，炸出一个能匹配最多待操作文件的正则表达式。*数据输入：由文件input.txt提供输入数据。文件由n（1n250）行组成。
13、每行给出一个文件名。文件名由英文字母和数字组成，英文字母要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，“-”表示不操作。*结果输出：将计算出的最多文件匹配数和最优正则表达式输出到文件output.txt。文件第1行中的数是计算出的最多文件匹配数，第2行是最优正则表达式。 输入文件示例 输出文件实例 input.txt output.txt EXCHANGE + 3 EXTRA + *A* HARDWARE + MOUSE NETWORK 1、解题说明设当前考察的正则表达式为s，当前考察的文件为f。用match(i.j
14、)表示s1.i与f1.j的匹配情况。当s1.i能匹配f1.j时，match(i,j)=1，否则match(i,j)=0.递归关系如下： 2、程序代码/设当前考察的正则表达式为s,当前考察的文件为f。/用match(i,j)表示s1.i与f1.j的匹配情况。/当s1.i能匹配f1.i时，match(i,j)=1，否则match(i,j)=0。#include#includeusing namespace std;int maxmat; /最优正则表达式所能匹配的到操作文件数int minlen; /最优正则表达式的长度int currmat; /当前最优正则表达式所能匹配的操作文件数char m
15、inmat10;char s10;int p10;struct cfchar c;int f;cha1010;int n2;string f10; /f10用来存储输入的文件名称int match101010; /matchlenij表示s1.lenth与fi1.j的匹配情况。void save(char c,int len) /save对操作文件名中出现的字符按出现频率排序储存，以加快搜索进程for(int i=1;i=plen;i+) /pi表示操作文件名中出现的不同的字符的个数 if(chaleni.c=c) /chaleni表示当前考察的正则表达式长度为len时，操作文件名字出现频率第
16、i高的字符。chaleni.f+;chalen0=chaleni;int j=i;while(chalenj-1.fchalen0.f)chalenj=chalenj-1;j-;chalenj=chalen0;return;chalen+plen.c=c;chalenplen.f=1;bool check(int len) /计算当前匹配情况int i,j,t,k=0;currmat=0;for(i=1;i=n0;i+)memset(&matchleni,0,sizeof(matchleni); /mleni数组全部赋初值0if(len=1&s1=*)matchleni0=1;for(j=1;
17、j=fi.length();j+)switch(slen)case*:for(t=0;t=1;j-)if(matchlenij=1)k+;if(j=fi.length()currmat+;break;if(k=minlen)return 0;plen=0;for(i=1;i=n0;i+)for(j=1;j=fi.length()-1;j+)if(matchlenij=1)save(fij,len);return 1;bool ok(int len) /用于判定是否匹配非操作文件int i,j,t,k;for(k=1;k=len;k+)for(i=n0+1;i=n0+n1;i+) memset(
18、&matchki,0,sizeof(matchki);/mleni数组全部赋初值0 if(s1=*&k=1) matchki0=1; for(j=1;j=fi.length();j+) switch(sk) case*: for(t=0;t=j;t+) if(matchk-1it=1) matchkij=1; break; break; case?: matchkij=matchk-1ij-1; break; default: if(sk=fij-1) matchkij=matchk-1ij-1; break;for(i=n0+1;imaxmat|currmat=maxmat&lenminle
19、n)&ok(len)maxmat=currmat;minlen=len;for(int i=1;i=minlen;i+)minmati=si;len+;if(len=1|slen-1!=*)slen=?; if(check(len) search(len); slen=*; if(check(len) search(len);for(int i=1;i=plen-1;i+)slen=chalen-1i.c;if(check(len)search(len);void readin() /读入数据并初始化int m;cout输入文件数目：m; string k10,str;char chr;n0=0;n1=0;p0=0;cout输入文件名：0) cinstrchr;if(chr=+)f+n0=str;save(str0,0);else k+n1=str;m-;for(int i=1;i=n1;i+)fn0+i=ki;memset(match,0,sizeof(match);for(i=1;i=n0+n1;i+)match0i0=1;maxmat=0;minlen=255;int main()readin();search(0); for(int i=1;i=minlen;i+)coutminmati;coutendl;return 0;3、运行截图
