算法设计与分析实验报告.doc

《算法设计与分析实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、..算法设计与分析实验报告教师：学号：：word资料..实验一：串匹配问题实验目的：(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。三、实验要求：(1)实现BF算法;(2)实现BF算法的改进算法:KMP算法和BM算法;(3)对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。#include"stdio.h"#include"conio.h"#include

2、ostream>//BF算法intBF(chars[],chart[]){inti;inta;intb;intm,n;m=strlen(s);//主串长度n=strlen(t);//子串长度printf("*****BF*****算法");for(i=0;i

3、算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[0]=-1;intj,k;j=0;k=-1;while(j

4、

5、(t[j]==t[k])){j++;k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}//KMP算法intKMP(chars[],chart[])word资料..{inta=0;intb=0;intm,n;m=strlen(s);//主串长度n=strlen(t);//子串长度printf

6、("*****KMP算法*****");while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!");return0;}b=GETNEXT(t,b);a=a-b;if(b==-1)b++;}printf("找不到%s",t);return0;}//滑动距离函数,用于BM算法intDIST(chart[],charc){inti=0,x=1;intn;n=strlen(t);while(x&&i!=n-1){if(t[i]

7、==c)x=0;elsei++;}if(i!=n-1)n=n-1-i;returnn;}//BM算法word资料..结果分析与体会： glibc里的strstr函数用的是brute-force(naive)算法，它与其它算法的区别是strstr不对pattern(needle)进行预处理，所以用起来很方便。理论复杂度Oword资料..(mn), 实际上，平均复杂度为O(n), 大部分情况下高度优化的算法性能要优于基于自动机的匹配算法，BF有一个重要性质是事先不用知道串的长度，而基于跳跃的算法是需要用字符串长度来判断结束位置的。

8、word资料..实验二：最近对问题二、实验目的：(1)进一步掌握递归算法的设计思想以及递归程序的调试技术;(2)理解这样一个观点:分治与递归经常同时应用在算法设计之中。三、实验要求：(1)分别用蛮力法和分治法求解最近对问题;(2)分析算法的时间性能,设计实验程序验证分析结论。ClosestPair1.java                                         //蛮力算法  import java.util.*; public class ClosestPair1 {  public static

9、 void main(String[] args)  {   /**    *输入需要比较的点的对数存在变量n中    */   Scanner in=new Scanner(System.in);   System.out.println("How many pairs of points to compare?(有多少对点需要比较?)");   int n=in.nextInt();      int[] x=new int[n];   int[] y=new int[n];   /**    *输入这些点的横坐标和纵坐标

10、分别存储在x[n]和y[n]    */   System.out.println("Please enter these points,X-coordinate(请输入这些点,横坐标):");   for(int i=0;i