编辑距离问题实验报告

《算法设计与分析》上机实验报告专业软件工程班级软件1101学号04113035学生姓名付添完成日期2013-10-241.上机题目及实验环境1.1上机题目：编辑距离问题1.2实验环境：CPU：intel内存：4G操作系统：windowsxp软件平台：MicrosoftVisualC++2.算法设计与分析对于本问题，大体思路为：把求解编辑距离分为字符串A从0个字符逐渐增加到全部字符分别想要变为字符串B该如何变化以及变化的最短距离。具体步骤如下:1从文件中读出字符串存入str1与str2中,d[][]用来村每一步需要变化的次数。取str1，str2长度分别为n,m.2分两种情况即A的长度为0而B不为0还有A不为0B为0，最后的编辑距离分别为m和n。一般情况，d矩阵为d[n][m]，假定我们从d[0][0]开始一直进行以下操作到了d[i][j]的位置，如果A比B长执行删除操作需要一步，如果是A比B短执行插入字符操作，更改字符操作说明一样长，然后如果将要比较的字符不相等对d[i][j-1]d[i-1][j]d[i-1][j-1]所存数进行比较，其中最小的即为当前长度和样式的字符串A变为B的编辑距离，如果相等直接让的d[i][j]=d[i-1][j-1]依次这样计算到最后的d[n][m]中所存的数即为最终的编辑距离。3.核心代码这是是比较上三角找出最小值的函数intMin(intx,inty,intz){return(xy?x:y)z?(xy?x:y):z;//返回最小值}n=strlen(str1);m=strlen(str2);for(i=0;i=n;i++)//当一个字符串为0另一个字符串每添加一个字符需要一次d[i][0]=i;for(j=0;i=m;j++)//当一个字符串为0另一个字符串每添加一个字符需要一次d[0][j]=j;for(i=1;i=n;i++){for(j=1;j=m;j++){if(str1[i-1]!=str2[j-1])d[i][j]=Min(d[i][j-1],d[i-1][j],d[i-1][j-1])+1;//找出上三角中最小的值elsed[i][j]=d[i-1][j-1];//与上一次需要的操作次数一样}}4.运行与调试图一图1：字符串相等时的运行结果图2：一般情况的运行结果图3：一个字符串为空的运行结果5.结果分析和小结（1）对结果的分析。分析结果可以采用图或者表的形式给出。这是一个错误的输出。因为定义的二维数组太小。老师上课强调d横坐标与纵坐标要分别比两个字符串大一，比如字符串长度分别为6,5，则矩阵大小最小为d[7][6].在写代码时因为这个错误输出有问题。（2）本次上机实验的收获、心得体会。上机可以督促我自己写代码每次上机前我都会先把代码大致写好，上机是运行并检查错误，这样不仅提高我的写代码能力，同时对算法这门课也有了更深刻的认识。老师检查运行结果可以发现我们的问题所在。对我们学习提供很大帮助。这次的上机实验，使我对动态规划法有了更进一步的认识，编程的时候也有了更多的思路，解决问题的时候，可以将带求解的问题分为若干子问题求解。以后再解答问题时我也尽量使用算法效率高的。附录（C/C++源代码）#includestdio.h#includestdlib.h#includestring.h#defineMAX100intMin(intx,inty,intz){return(xy?x:y)z?(xy?x:y):z;//返回最小值}voidmain(){charstr1[MAX];charstr2[MAX];inti,j,n,m,way;intd[MAX+1][MAX+1];FILE*fp;fp=fopen(input.txt,r);printf(选择输入方式\n\n0：从文件输入\n1:从键盘输入\n);scanf(%d,&way);switch(way){case0:fscanf(fp,%s,str1);printf(文件中的字符串1%s\n,&str1);fscanf(fp,%s,str2);printf(文件中的字符串2%s\n,&str2);fclose(fp);break;case1:printf(请输入字符串1\n);scanf(%s,&str1);printf(请输入字符串2\n);scanf(%s,&str2);break;}n=strlen(str1);m=strlen(str2)for(i=0;i=n;i++)//当一个字符串为0另一个字符串每添加一个字符需要一次d[i][0]=i;for(i=0;i=m;i++)//当一个字符串为0另一个字符串每添加一个字符需要一次d[0][i]=i;for(i=1;in;i++){for(j=1;jm;j++){if(str1[i-1]!=str2[j-1])d[i][j]=Min(d[i][j-1],d[i-1][j],d[i-1][j-1])+1;//找出上三角中最小的值elsed[i][j]=d[i-1][j-1];//与上一次需要的操作次数一样}}printf(最小编辑距离为：\n%d\n,d[n][m]);fp=fopen(output.txt,w);fprintf(fp,%d,d[n][m]);fclose(fp);}