算法设计与分析实验报告

算法设计与分析实验报告教师：学号：姓名：实验一：串匹配问题实验目的：(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。三、实验要求：(1)实现BF算法;(2)实现BF算法的改进算法:KMP算法和BM算法;(3)对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。#includestdio.h#includeconio.h#includeiostream//BF算法intBF(chars[],chart[]){inti;inta;intb;intm,n;m=strlen(s);//主串长度n=strlen(t);//子串长度printf(\n*****BF*****算法\n);for(i=0;im;i++){b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf(查找成功!!\n\n);return0;}}printf(找不到%s\n\n,t);return0;}//前缀函数值,用于KMP算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[0]=-1;intj,k;j=0;k=-1;while(jstrlen(t)){if((k==-1)||(t[j]==t[k])){j++;k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}//KMP算法intKMP(chars[],chart[]){inta=0;intb=0;intm,n;m=strlen(s);//主串长度n=strlen(t);//子串长度printf(\n*****KMP算法*****\n);while(a=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf(查找成功!!\n\n);return0;}b=GETNEXT(t,b);a=a-b;if(b==-1)b++;}printf(找不到%s\n\n,t);return0;}//滑动距离函数,用于BM算法intDIST(chart[],charc){inti=0,x=1;intn;n=strlen(t);while(x&&i!=n-1){if(t[i]==c)x=0;elsei++;}if(i!=n-1)n=n-1-i;returnn;}//BM算法结果分析与体会：glibc里的strstr函数用的是brute-force(naive)算法，它与其它算法的区别是strstr不对pattern(needle)进行预处理，所以用起来很方便。理论复杂度O(mn),实际上，平均复杂度为O(n),大部分情况下高度优化的算法性能要优于基于自动机的匹配算法，BF有一个重要性质是事先不用知道串的长度，而基于跳跃的算法是需要用字符串长度来判断结束位置的。实验二：最近对问题二、实验目的：(1)进一步掌握递归算法的设计思想以及递归程序的调试技术;(2)理解这样一个观点:分治与递归经常同时应用在算法设计之中。三、实验要求：(1)分别用蛮力法和分治法求解最近对问题;(2)分析算法的时间性能,设计实验程序验证分析结论。ClosestPair1.java//蛮力算法importjava.util.*;publicclassClosestPair1{publicstaticvoidmain(String[]args){/***输入需要比较的点的对数存在变量n中*/Scannerin=newScanner(System.in);System.out.println(Howmanypairsofpointstocompare?(有多少对点需要比较?));intn=in.nextInt();int[]x=newint[n];int[]y=newint[n];/***输入这些点的横坐标和纵坐标分别存储在x[n]和y[n]*/System.out.println(Pleaseenterthesepoints,X-coordinate(请输入这些点,横坐标):);for(inti=0;in;i++){x[i]=in.nextInt();}System.out.println(Pleaseenterthesepoints,Y-coordinate(请输入这些点,纵坐标):);for(inti=0;in;i++){y[i]=in.nextInt();}doubleminDist=Double.POSITIVE_INFINITY;doubled;intindexI=0;intindexJ=0;/***求解最近对距离存在minDist中*/doublestartTime=System.currentTimeMillis();//startTimefor(inti=0;in-1;i++){for(intj=i+1;jn;j++){d=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));if(dminDist){minDist=d;indexI=i;indexJ=j;}}}doubleendTime=System.currentTimeMillis();//endTime/***打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间*/System.out.println(Theclosestpairis:(+x[indexI]+,+y[indexI]+)and(+x[indexJ]+,+y[indexJ]+));System.out.println(Theclosestdistanceis+minDist);System.out.println(BasicStatementstake(基本语句用时)+(endTime-startTime)+milliseconds!);}}ClosestPair2.java//分治算法importjava.util.*;publicclassClosestPair2{publicstaticvoidmain(String[]args){/***输入需要比较的点的对数存在变量n中*/Scannerin=newScanner(System.in);System.out.println(Howmanypairsofpointstocompare?(有多少对点需要比较?));intn=in.nextInt();/***输入这些点的横坐标和纵坐标，存储在点数组S[n]中*/System.out.println(Pleaseenterthesepoints,X-coordinateandY-coordinate.(请输入这些点，x坐标和y坐标)：);Point[]S=newPoint[n];doublestartTime=System.currentTimeMillis();//starttimefor(inti=0;in;i++){intx=in.nextInt();inty=in.nextInt();S[i]=newPoint(x,y);System.out.println((+S[i].getX()+,+S[i].getY()+));}/***求出这点的x坐标的中位数mid*/intminX=(int)Double.POSITIVE_INFINITY;intmaxX=(int)Double.NEGATIVE_INFINITY;for(inti=0;in;i++){if(S[i].getX()minX)minX=S[i].getX();if(S[i].getX()maxX)maxX=S[i].getX();}intmid=(minX+maxX)/2;/***以mid为界把S中的点分为两组分别存放在范型数组列表point1和point2中*/ArrayListPointpoint1=newArrayListPoint();ArrayListPointpoint2=newArrayListPoint();for(inti=0;in;i++){if(S[i].getX()=mid)point1.add(S[i]);elsepoint2.add(S[i]);}/***将范型数组列表转换为数组类型S1和S2*/Point[]S1=newPoint[point1.size()];Point[]S2=newPoint[point2.size()];point1.toArray(S1);point2.toArray(S2);/***将S1和S2中的点按x坐标升序排列*/sortX(S1);sortX(S2);/***打印输出排序后S1和S2的点*/System.out.print(ThepointsinS1are:);for(inti=0;iS1.length;i++)System.out.print((+S1[i].getX()+,+S1[i].getY()+));System.out.println();System.out.print(ThepointsinS2are:);for(inti=0;iS2.length;i++)System.out.print((+S2[i].getX()+,+S2[i].getY()+));System.out.println();/***求S1中点的最近对及其距离并打印输出结果*/doubleminDist1=Double.POSITIVE_INFINITY;intindexI1=0;intindexJ1=0;for(inti=0;iS1.length-1;i++){for(intj=i+1;jS1.length;j++){doubled=Math.sqrt(Math.pow((S1[i].getX()-S1[j].getX()),2)+Math.pow((S1[i].getY()-S1[j].getY()),2));if(dminDist1){minDist1=d;indexI1=i;indexJ1=j;}}}System.out.println(TheclosestpairinS1is:+(+S1[indexI1].getX()+,+S1[indexI1].getY()+)+and(+S1[indexJ1].getX()+,+S1[indexJ1].getY()+)+,andthedistanceis+minDist1);/***求S2中点的最近对及其距离并打印输出结果*/doubleminDist2=Double.POSITIVE_INFINITY;intindexI2=0;intindexJ2=0;for(inti=0;iS2.length-1;i++){for(intj=i+1;jS2.length;j++){doubled=Math.sqrt(Math.pow((S2[i].getX()-S2[j].getX()),2)+Math.pow((S2[i].getY()-S2[j].getY()),2));if(dminDist2){minDist2=d;indexI2=i;indexJ2=j;}}}System.out.println(TheclosestpairinS2is:+(+S2[indexI2].getX()+,+S2[indexI2].getY()+)+and(+S2[indexJ2].getX()+,+S2[indexJ2].getY()+)+,andthedistanceis+minDist2);doubled1=Math.min(minDist1,minDist2);/***求出S1和S2中点的横坐标离小于d1的所有点分别存在P1[]和P2[]中*/ArrayListPoin