序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题.docx
《序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题.docx》由会员分享，可在线阅读，更多相关《序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题.docx（20页珍藏版）》请在冰点文库上搜索。
序关系计数问题+编辑距离问题+最小m段问题+正则表达式匹配问题
一、算法实现题3-3序关系计数问题
*问题描述：
用关系“<”和“=”将3个数A，B和C依序排列时有13种不同的序关系：
A=B=C，A=B将n个数（1≤n≤50）依序排列时有多少种序关系。
*算法设计：
计算出将n个数（1≤n≤50）依序排列时有多少种序关系。
*数据输入：
由文件input.txt提供输入数据。
文件只有一行，提供一个数n。
*结果输出：
将找到的序关系数输出到文件output.txt的第1行。
输入文件示例输出文件示例
input.txtoutput.txt
313
1、解题说明
本题具有最优子结构特性，并有重叠子问题性质，因此可以采用动态规划来求解。
我们可以采用一个二维数组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对于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
#include
usingnamespacestd;
intorder（intn,int*ord）
{
inti,j,total=0;
ord[0]=1;//只有一个数时
for（i=1;i<=n-1;i++）//赋初值
ord[i]=0;
for（i=2;i<=n;i++）//2~n个数
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<return0;
}
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，计算其编辑距离d（A,B）。
*数据输入：
由文件input.txt提供输入数据。
文件的第1行是字符串A，文件的第2行是字符串B。
*结果输出：
将编辑距离d（A,B）输出到文件output.txt的第1行。
输入文件示例输出文件实例
input.txtoutput.txt
fxpimu5
xwrs
1、解题说明
输入两个字符串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[i-1][j]+1,dis[i][j-1]+1）。
初始化后，dis二维数组如下：
2、程序代码
#include
#include
#include
usingnamespacestd;
#defineMax20
intdis[Max][Max];
intmin（inta,intb,intc）//最小值函数
{
intd=（a>b?
b:
a）;
returnc>d?
d:
c;
}
intdistance（stringa,stringb）//编辑距离函数
{
inti,j;
intdisab;//存字符a[i]到字符b[j]的编辑距离
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++）
{
for（j=1;j<=b.length（）;j++）
{
if（a[i-1]==b[j-1]）//比较a的第i个字符与b的第j个字符是否相同
disab=0;
else
disab=1;
dis[i][j]=min（dis[i-1][j-1]+disab,dis[i-1][j]+1,dis[i][j-1]+1）;//递归关系式
}
}
returndis[a.length（）][b.length（）];
}
intmain（）
{
ifstreamin（"input.txt"）;
ofstreamout（"output.txt"）;
stringstr1,str2;
in>>str1>>str2;//从文件读入
out<return0;
}
3、运行截图
1）程序所在文件
2）输入文件
3）输出文件
三、算法实现题3-11最小m段和问题
给定n个整数组成的序列，计算该序列的最优m段分割，使m段子序列的最大值达到最小。
由文件input.txt提供输入数据。
文件的第一行有两个正整数n和m。
n是序列的长度，m是分割的段数。
接下来的一行中有n个整数。
输出文件的第一行是计算出的m段子序列的和的最大值的最小值。
输入文件示例输出文件示例
input.txtoutput.txt
1110
10
1、解题说明
首先理解题意，所要求的是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
#include
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（tmin=t;
lastpart+=data[k];//将第i段向左扩充一个数
}
solve[i][j]=min;
}
}
}
out<}
3、运行截图
（1）input.txt
（2）output.txt
（3）文件夹截图
四、算法实现题3-14正则表达式匹配问题
1、题目
*问题描述：
许多操作系统采用正则表达式实现文件匹配功能。
一种简单的正则表达式由英文字母、数字及通配符“*”和“？
”组成。
“？
”代表任意一个字符，“*”则可以代表任意多个字符。
现要用正则表达式对部分文件进行操作。
试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。
所找出的正则表达式的长度还应是最短的。
*算法设计：
对于给定的待操作文件，炸出一个能匹配最多待操作文件的正则表达式。
*数据输入：
由文件input.txt提供输入数据。
文件由n（1≤n≤250）行组成。
每行给出一个文件名。
文件名由英文字母和数字组成，英文字母要区分大小写，文件名长度不超过8个字符。
文件名后是一个空格符和一个字符“+”或“-”。
“+”表示要对该行给出的文件进行操作，“-”表示不操作。
*结果输出：
将计算出的最多文件匹配数和最优正则表达式输出到文件output.txt。
文件第1行中的数是计算出的最多文件匹配数，第2行是最优正则表达式。
输入文件示例输出文件实例
input.txtoutput.txt
EXCHANGE+3
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.
递归关系如下：
2、程序代码
//设当前考察的正则表达式为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
#include
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][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]数组全部赋初值0
if（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=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]数组全部赋初值0
if（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][j-1];
break;}
}
for（i=n[0]+1;i<=n[0]+n[1];i++）
if（match[len][i][f[i].length（）]==1）
return0;
return1;
}
voidsearch（intlen）
{
if（（currmat>maxmat||currmat==maxmat&&len{
maxmat=currmat;
minlen=len;
for（inti=1;i<=minlen;i++）
minmat[i]=s[i];
}
len++;
if（len==1||s[len-1]!
='*'）
{
s[len]='?
';
if（check（len））
search（len）;
s[len]='*';
if（check（len））
search（len）;
}
for（inti=1;i<=p[len-1];i++）
{
s[len]=cha[len-1][i].c;
if（check（len））
search（len）;
}
}
voidreadin（）//读入数据并初始化
{
intm;
cout<<"输入文件数目：
"<cin>>m;
stringk[10],str;
charchr;
n[0]=0;n[1]=0;p[0]=0;
cout<<"输入文件名：
"<while（m>0）
{
cin>>str>>chr;
if（chr=='+'）
{
f[++n[0]]=str;
save（str[0],0）;
}
elsek[++n[1]]=str;
m--;
}
for（inti=1;i<=n[1];i++）
f[n[0]+i]=k[i];
memset（match,0,sizeof（match））;
for（i=1;i<=n[0]+n[1];i++）
match[0][i][0]=1;
maxmat=0;
minlen=255;
}
intmain（）
{
readin（）;
search（0）;
for（inti=1;i<=minlen;i++）
cout<cout<return0;
}
3、运行截图
升级会员 