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

一、算法实现题3-3序关系计数问题问题描述：用关系“〈”和“二”将3个数A,B和C依序排列时有13种不同的序关系：A=B=C，A=B<C，A<B=C，A<B<C，A<C<B，A=C<B，B<A=C，B<A<C，B<C<A，B=C<A，C<A=B，C<A<B，C<B<A将n个数(1WnW50)依序排列时有多少种序关系。算法设计：计算出将n个数(1WnW50)依序排列时有多少种序关系。数据输入：由文件input.txt提供输入数据。文件只有一行，提供一个数n。结果输出：将找到的序关系数输出到文件output.txt的第1行。输入文件示例 输出文件示例input.txt output.txt3 131、解题说明本题具有最优子结构特性，并有重叠子问题性质，因此可以采用动态规划来求解。我们可以采用一个二维数组A[i,j]来表示用j个“〈”号来连接i个数时产生的不同序关系数。因此，1)当j>i-1的时候，即“〈”号的个数多于需要的符号总数时，定义边界条件A[i,j]=0；2)当没有“<”号的时候，即全部为“二”号，序关系排列只有一种，即A[i,0]=1,i=1~n。3)一般情况时，当用j个“〈”号来连接i个数的时候，则有如下形式：S1<S2<……<Sj+1,即Sk(1<k<j)1中的各个数字之间用“〈”号相连，但不一定直接相邻，彼此之间可能有其它数用“=”号和它们分别相连。对于A[i,j],考虑在i-1个数的基础上增加一个数x的情形。则可以分为两种情况：当原有i-1个数已有j个“〈”号相连，则此时x只能以“二”号与i-1个数字相连，并且有j+1种位置选择。原有排序为A[i-1,j],此时共有(j+1)*A[i-1,j]种不同的排列。当原有i-1个数已有j-1个“〈”号相连，则此时x只能以“〈”号与i-1个数字相连，同样有j+1种位置选择。原有排序为A[i-1,j-1],此时共有(j+1)*A[i-1,j-1]种不同的排列。因此A[i,j]的递归表达式为：A[i,j]=(j+1)*(A[i-1,j]+A[i-1,j-1])这种表达式已经经过了简化，因此计算A[i,j]的时候只用到第i-1行中的2个数字，只需保存第i-1行就可以了。在写程序的时候，没必要真的用一个二维数组来存储数组，可以用for循环来控制行数，而用A这个一维数组来存储上一行每列的数据，提高了算法的空间效率。2、程序代码#include<iostream>#include<fstream>usingnamespacestd;

intorder(intn,int*ord){inti,j,total=0;〃只有一个数时〃赋初值〃只有一个数时〃赋初值//2-n个数for(i=1;i<=n-1;i++)ord[i]=0;for(i=2;i<=n;i++)for(j=i-1;j>=1;j--)//j表示〈号的个数,j取1~(i-1)ord[j]=(j+1)*(ord[j-1]+ord[j]); //递推公式for(j=0;j<=n-1;j++)total+=ord[j]; 〃求和returntotal;)intmain(){intn,total=0;ifstreamin("input.txt"); //输入文件ofstreamout("output.txt");//输出文件in>>n; 〃从文件读入int*ord=newint[n];total=order(n,ord);out<<total<<endl; 〃输出到文件return0;)3、运行截图txt1)程序所在文件夹有input.txt，运行完成后产生了output.txtDebug,,input.txt□output.txt[eg序关惑诿荷题,[p蠡序关熟诿问题Jsp□序关茎计数问题,neb□序关茎计数问题,optD序关茎计数问题,plg2)设定输入为33）运行程序后，打开ouput.txt,输出结果为13。output.txt-记事本文件时编辑旧格式②直看M帮曲而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，计算其编辑距离d（A,B）。*数据输入：由文件input.txt提供输入数据。文件的第1行是字符串A，文件的第2行是字符串B。*结果输出：将编辑距离d（A,B）输出到文件output.txt的第1行。输入文件示例 输出文件实例input.txt output.txtfxpimu 5xwrs1、解题说明输入两个字符串a和b，定义二维数组来保存编辑距离，即dis[i][j]=d（a[0:i-1],b[0:j-1]）。考虑两种特殊情况，若字符串a长度为m，b为空串，则d（a,b）=m，即dis[i][0]=i;若字符串b长度为m，a为空串，则d（a,b）=n.即dis[0][j]=j；当两个字符串长度为1时，若a==b，则d（a,b）=0;若a!=b，则d（a,b）=1。考虑一般情况，从字符串a[0:i]到字符串b[0:j]的变换，可以分为三种情况:1）a[0:i-1]到字符串b[0:j-1]已经转换好，那么只需考虑两个字符a[i]和b[j]，则在原来的基础上只需要d（a[i]，b[j]）次操作，即dis[i-1][j-1]+d（a[i]，b[j]）;2）a[0:i-1]到字符串b[0:j]已经转换好,则需删除a[i],需要在原来基础上加1，即dis[i-1][j]+1;3）a[0:i]到字符串b[0:j-1]已经转换好,则需删除b[j],需要在原来基础上加1，即dis[i][j-1]+1;综上所述，三种情况中取最小值，dis[i][j]可以递归的计算如下：dis[i][j]=min(dis[i-1][j-1]+d(a[i]b[j]),dis[iT][j]+1,dis[i][jT]+1)。初始化后，dis二维数组如下：01012001211223344556&345634562、程序代码#include<iostream>#include<string>#include<fstream>usingnamespacestd;#defineMax20intdis[Max][Max];intmin(inta,intb,intc) 〃最小值函数{intd=(a>b?b:a);returnc>d?d:c;)intdistance(stringa,stringb){inti,j;intdistance(stringa,stringb){inti,j;intdisab;for(i=0;i<=a.length();i++)dis[i][0]=i;for(i=0;i<=b.length();i++)dis[0][i]=i;for(i=1;i<=a.length();i++){//编辑距离函数//存字符a[i]到字符b[j]的编辑距离//初始条件//初始条件for(j=1;j<=b.length();j++){if(a[i-1]==b[j-1])〃比较a的第i个字符与b的第j个字符是否相同disab=0;elsedisab=1;dis[i][j]=min(dis[i-1][j-1]+disab,dis[i-1][j]+1,dis[i][j-11+1);//递归关系式))returndis[a.length()][b.length()];)intmain(){ifstreamin("input.txt");ofstreamout("output.txt");stringstr1,str2;in>>str1>>str2; 〃从文件读入out<<distance(str1,str2)<<endl;//输出到文件return0;)3、运行截图1)程序所在文件名称DebugI।input.txt।।output.txt㈣编福静问题呼p露精5第问题,d印_编辑5瞳问题，neb_编辑5巨离问题，p1g2)输入文件3）输出文件output.txt-本文件的编辑(日格式(O)查看M朝跖两三、算法实现题3-11最小m段和问题给定n个整数组成的序列，计算该序列的最优m段分割，使m段子序列的最大值达到最小。由文件input.txt提供输入数据。文件的第一行有两个正整数n和m。n是序列的长度，m是分割的段数。接下来的一行中有n个整数。输出文件的第一行是计算出的m段子序列的和的最大值的最小值。输入文件示例 输出文件示例input.txt output.txt11 10101、解题说明首先理解题意，所要求的是m段子序列的和的最大值的最小值。也就是将n个整数分为m段，并且计算每段的和，求出这m段和的最大值；不同的划分方法会求出不同的最大值，求所有划分方法得到的最大值当中的最小值。用动态规划来解这个题，n个整数划分为m段，solve[i][j]表示前i个整数划分为j段子序列的和的最大值的最小值，min为当前最小值，lastpart为第j段子序列的和。初始条件是整数个数i和分成的段数j都等于1，则solve[1][1]=data[1]；当j>i的时候，划分不存在；考虑一般情况，i个整数划分为j段，则solve[i][j]=minmax(solve[k][j-1],lastpart)。其中，j-1<=k<=i-1,lastpart=data[k+1]+data[k+2]+…+data[i]。2、程序代码#include<iostream>#include<fstream>usingnamespacestd;voidmain(){intn,m,t,min,lastpart;ifstreamin("input.txt");ofstreamout("output.txt");in>>n>>m;int*data=newint[n+1];for(inti=1;i<=n;i++)in>>data[i];/*solve[i][j]代表从第一位到第i位数字分割成j段的最小子段和，此题要求的就是solve[n][m]。*/int**solve=newint*[n+1];〃初始化二维数组for(intj=1;j<=n;j++){solve[j]=newint[m+1];)solve[1][1]=data[1];〃初始化for(i=2;i<=n;i++){for(j=1;j<=m;j++){if(j==1)〃只分成一段{solve[i][j]=solve[i-1][1]+data[i];)elseif(j>i)〃分成的段数大于子段的个数break;else 〃处理一般情况{min=100000000;//min初始值为无穷大lastpart=data[i];〃第j个子段的和for(intk=i-1;k>=j-1;k--)/*考虑已将前k个数分成j-1段，并将后i-k个数作为第j段。则k最小只能与段数j-1相等，最大为i-1。*/{t=solve[k][j-1]>lastpart?solve[k][j-1]:lastpart;/*取前j-1个子段和的最大值的最小值踉第j个子段和相比，取较大值。*/if(t<min) 〃更新最小值min=t;lastpart+=data[k];〃将第i段向左扩充一个数)solve[i][j]=min;)))out<<solve[n][m]<<endl;)3、运行截图(1)input.txt⑵output.txt⑶文件夹截图2013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&22013/11/1&2,,input.txtII output.txt画最小m段和问题,卬口露最小m段和问题,dsp露最小m段和问题,dsw最小m段和问题,neb最小m箴□问题,opt最小m段和问题,plg四、算法实现题3-14正则表达式匹配问题1、题目问题描述：许多操作系统采用正则表达式实现文件匹配功能。一种简单的正则表达式由英文字母、数字及通配符“*”和“？”组成。“？”代表任意一个字符，“*”则可以代表任意多个字符。现要用正则表达式对部分文件进行操作。试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。所找出的正则表达式的长度还应是最短的。算法设计：对于给定的待操作文件，炸出一个能匹配最多待操作文件的正则表达式。数据输入：由文件input.txt提供输入数据。文件由n(1WnW250)行组成。每行给出一个文件名。文件名由英文字母和数字组成，英文字母要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，“-”表示不操作。结果输出：将计算出的最多文件匹配数和最优正则表达式输出到文件output.txt。文件第1行中的数是计算出的最多文件匹配数，第2行是最优正则表达式。输入文件示例input.txtEXCHANGE+输出文件实例输入文件示例input.txtEXCHANGE+EXTRA+ *A*HARDWARE+MOUSE-NETWORK-1、解题说明设当前考察的正则表达式为s,当前考察的文件为f。用match(i.j)表示s[1..i]与f[1..j]的匹配情况。当s[1..i]能匹配f[1..j]时，match(i,j)=1，否则match(i,j)=0.递归关系如下：[।match(i-1-1)—1 §[门=?1ymalchC—1仃-1)=1 疝钉=/口"|match"/)…J2、程序代码〃设当前考察的正则表达式为s,当前考察的文件为f。〃用match(i,j)表示s[1..i]与f[1..j]的匹配情况。〃当s[1..i]能匹配f[1..i]时，match(i,j)=1，否则match(i,j)=0。#include<iostream>#include<string>usingnamespacestd;intmaxmat;〃最优正则表达式所能匹配的到操作文件数intminlen;〃最优正则表达式的长度intcurrmat;〃当前最优正则表达式所能匹配的操作文件数charminmat[10];chars[10];intp[10];structcf{charc;intf;}cha[10][10];intn[2];stringf[10];//f[10]用来存储输入的文件名称intmatch[10][10][10];〃match[len][i][j]表示s[1..lenth]与f[i][1..j]的匹配情况。voidsave(charc,intlen)//save对操作文件名中出现的字符按出现频率排序储存，以加快搜索进程{for(inti=1;i<=p[len];i++)〃p[i]表示操作文件名中出现的不同的字符的个数if(cha[len][i].c==c)//cha[len][i]表示当前考察的正则表达式长度为 len时，操作文件名字出现频率第i高的字符。{cha[len][i].f++;cha[len][0]=cha[len][i];intj=i;while(cha[len][j-1].f<cha[len][0].f){cha[len][j]=cha[len][j-1];j--;)cha[len][j]=cha[len][0];return;)cha[len][++p[len]].c=c;cha[len][p[len]].f=1;)boolcheck(intlen)〃计算当前匹配情况{inti,j,t,k=0;currmat=0;for(i=1;i<=n[0];i++){memset(&match[len][i],0,sizeof(match[len][i]));//m[len][i]数组全部赋初值0if(len==1&&s[1]==，*，)match[len][i][0]=1;for(j=1;j<=f[i].length();j++)switch(s[len]){case'*':for(t=0;t<=j;t++)if(match[len-1][i][t]==1){match[len][i][j]=1;break;)break;case?:match[len][i][j]=match[len-1][i][j-1];break;default:if(s[len]==f[i][j-1])match[len][i][j]=match[len-1][i][j-1];break;}for(j=f[i].length();j>=1;j--)if(match[len][i][j]==1){k++;if(j==f[i].length())currmat++;break;}}if(k<maxmat||k==maxmat&&len>=minlen)return0;p[len]=0;for(i=1;i<=n[0];i++)for(j=1;j<=f[i].length()-1;j++)if(match[len][i][j]==1)save(f[i][j],len);return1;}boolok(intlen)〃用于判定是否匹配非操作文件{inti,j,t,k;for(k=1;k<=len;k++)for(i=n[0]+1;i<=n[0]+n[1];i++){memset(&match[k][i],0,sizeof(match[k][i]));〃m[len][i]数组全部赋初值0if(s[1]==，*，&&k==1)match[k][i][0]=1;for(j=1;j<=f[i].length();j++)switch(s[k]){case'*':for(t=0;t<=j;t++)if(match[k-1][i][t]==1){match[k][i][j]=1;break;)break;case?:match[k][i][j]=match[k-1][i][j-1];break;default:if(s[k]==f[i][j-1])match[k][i][j]=match[k-1][i]