序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题.docx

1、序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题一、算法实现题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

2、 output.txt 3 131、解题说明 本题具有最优子结构特性，并有重叠子问题性质，因此可以采用动态规划来求解。 我们可以采用一个二维数组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的情形。则可以分为两种情

3、况：当原有i-1个数已有j个“”号相连，则此时x只能以“=”号与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行就可以了。 在写程序的时候，没必要真的用一个二维数组来

4、存储数组，可以用for循环来控制行数，而用A这个一维数组来存储上一行每列的数据，提高了算法的空间效率。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

5、,ord); outtotalendl; /输出到文件 return 0;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，计算出它们的编辑距

6、离d（A,B）。 *算法设计：对于给定的字符串A和字符串B，计算其编辑距离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,

7、b）=n.即dis0j=j；当两个字符串长度为1时，若a=b，则d(a,b)=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

8、可以递归的计算如下：disij=min(disi-1j-1+d(aibj),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

9、=0;i=a.length();i+) / 初始条件 disi0=i; for(i=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 st

10、d; 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;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+) f

11、or(j=1;ji) /分成的段数大于子段的个数 break; else /处理一般情况 min=100000000; /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

12、段向左扩充一个数 solveij=min; outsolvenmendl; 3、运行截图(1)input.txt(2)output.txt (3)文件夹截图 四、算法实现题3-14 正则表达式匹配问题1、题目*问题描述：许多操作系统采用正则表达式实现文件匹配功能。一种简单的正则表达式由英文字母、数字及通配符“*”和“？”组成。“？”代表任意一个字符，“*”则可以代表任意多个字符。现要用正则表达式对部分文件进行操作。试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。所找出的正则表达式的长度还应是最短的。*算法设计：对于给定的待操作文件，炸出一个能匹配

13、最多待操作文件的正则表达式。*数据输入：由文件input.txt提供输入数据。文件由n（1n250）行组成。每行给出一个文件名。文件名由英文字母和数字组成，英文字母要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，“-”表示不操作。*结果输出：将计算出的最多文件匹配数和最优正则表达式输出到文件output.txt。文件第1行中的数是计算出的最多文件匹配数，第2行是最优正则表达式。 输入文件示例 输出文件实例 input.txt output.txt EXCHANGE + 3 EXTRA + *A* HARDWARE +

14、MOUSE NETWORK 1、解题说明 设当前考察的正则表达式为s，当前考察的文件为f。用match(i.j)表示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 min

15、len; /最优正则表达式的长度int currmat; /当前最优正则表达式所能匹配的操作文件数char minmat10;char s10;int p10;struct cf char 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表示操作文件名中出现的不同的字符的

16、个数 if(chaleni.c=c) /chaleni表示当前考察的正则表达式长度为len时，操作文件名字出现频率第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(&matchle

17、ni,0,sizeof(matchleni); /mleni数组全部赋初值0 if(len=1&s1=*) matchleni0=1; for(j=1;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

18、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(&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

19、; default: if(sk=fij-1) matchkij=matchk-1ij-1; break; for(i=n0+1;imaxmat|currmat=maxmat&lenminlen)&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=ch

20、alen-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、运行截图