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

一、算法实现题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个数（1≤n≤50）依序排列时有多少种序关系。 *算法设计：计算出将n个数（1≤n≤50）依序排列时有多少种序关系。 *数据输入：由文件input.txt提供输入数据。文件只有一行，提供一个数n。 *结果输出：将找到的序关系数输出到文件output.txt的第1行。 输入文件示例 输出文件示例 input.txt output.txt 3 13 1、解题说明 本题具有最优子结构特性，并有重叠子问题性质，因此可以采用动态规划来求解。 我们可以采用一个二维数组A[i,j]来表示用j个“”号来连接i个数时产生的不同序关系数。因此， 1）当ji-1的时候，即“”号的个数多于需要的符号总数时，定义边界条件A[i,j]=0； 2）当没有“”号的时候，即全部为“=”号，序关系排列只有一种，即A[i,0]=1,i=1~n。 3）一般情况时，当用j个“”号来连接i个数的时候，则有如下形式：S1S2……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、程序代码 #includeiostream #includefstream using namespace std; int order(int n,int *ord) { int i,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]; //求和 return total; } int main() { int n,total=0; ifstream in(input.txt); //输入文件 ofstream out(output.txt); //输出文件 inn; //从文件读入 int *ord=new int[n]; total=order(n,ord); outtotalendl; //输出到文件 return 0; } 3、运行截图 1）程序所在文件夹有input.txt，运行完成后产生了output.txt 2）设定输入为3 3）运行程序后，打开ouput.txt，输出结果为13。 二、算法实现题3-5 编辑距离问题 *问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符B。 这里所说的字符操作包括： 删除一个字符 插入一个字符 将一个字符改为另一个字符 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A,B）。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离 d（