1、精選優(yōu)質文檔-傾情為你奉上 算法設計與分析 實驗報告 教師： 學號： 姓名： 實驗一：串匹配問題實驗目的： (1) 深刻理解并掌握蠻力法的設計思想; (2) 提高應用蠻力法設計算法的技能; (3) 理解這樣一個觀點: 用蠻力法設計的算法, 一般來說, 經過適度的努力后, 都可以對算法的第一個版本進行一定程度的改良, 改進其時間性能。3、 實驗要求： ( 1) 實現(xiàn) BF 算法; (2 ) 實現(xiàn) BF 算法的改進算法: KMP 算法和 BM 算法; (3 ) 對上述 3 個算法進行時間復雜性分析, 并設計實驗程序驗證分析結果。#include "stdio.h" #inclu

2、de "conio.h" #include <iostream> /BF算法 int BF(char s,char t) int i; int a; int b; int m,n; m=strlen(s); /主串長度 n=strlen(t); /子串長度 printf("n*BF*算法n"); for(i=0;i<m;i+) b=0; a=i; while(sa=tb&&b!=n) a+; b+; if(b=n) printf("查找成功!nn"); return 0; printf("找

3、不到%snn",t); return 0; /前綴函數值,用于KMP算法 int GETNEXT(char t,int b) int NEXT10; NEXT0=-1; int j,k; j=0; k=-1; while(j<strlen(t) if (k=-1)|(tj=tk) j+; k+; NEXTj=k; else k=NEXTk; b=NEXTb; return b; /KMP算法 int KMP(char s,char t) int a=0; int b=0; int m,n; m=strlen(s); /主串長度 n=strlen(t); /子串長度 printf

4、("n*KMP算法*n"); while(a<=m-n) while(sa=tb&&b!=n) a+; b+; if(b=n) printf("查找成功!nn"); return 0; b=GETNEXT(t,b); a=a-b; if(b=-1) b+; printf("找不到%snn",t); return 0; /滑動距離函數,用于BM算法 int DIST(char t,char c) int i=0,x=1; int n; n=strlen(t); while(x&&i!=n-1) if

5、(ti=c) x=0; else i+; if(i!=n-1) n=n-1-i; return n; /BM算法 結果分析與體會： glibc里的strstr函數用的是brute-force(naive)算法，它與其它算法的區(qū)別是strstr不對pattern(needle)進行預處理，所以用起來很方便。理論復雜度O(mn), 實際上，平均復雜度為O(n), 大部分情況下高度優(yōu)化的算法性能要優(yōu)于基于自動機的匹配算法，BF有一個重要性質是事先不用知道串的長度，而基于跳躍的算法是需要用字符串長度來判斷結束位置的。實驗二：最近對問題2、 實驗目的：( 1) 進一步掌握遞

6、歸算法的設計思想以及遞歸程序的調試技術; (2 ) 理解這樣一個觀點: 分治與遞歸經常同時應用在算法設計之中。3、 實驗要求：( 1) 分別用蠻力法和分治法求解最近對問題; (2 ) 分析算法的時間性能, 設計實驗程序驗證分析結論。ClosestPair1.java                            

7、;             /蠻力算法  import java.util.*; public class ClosestPair1   public static void main(String args)     /*    *輸入需要比較的點

8、的對數存在變量n中    */   Scanner in=new Scanner(System.in);   System.out.println("How many pairs of points to compare?(有多少對點需要比較?)");   int n=in.nextInt();     &#

9、160;int x=new intn;   int y=new intn;   /*    *輸入這些點的橫坐標和縱坐標分別存儲在xn和yn    */   System.out.println("Please enter these points,X-coordinate(請輸入這些點,橫坐標):");   

10、;for(int i=0;i<n;i+)       xi=in.nextInt();         System.out.println("Please enter these points,Y-coordinate(請輸入這些點,縱坐標):");   for(int i=0;i<n;i+)  

11、0;    yi=in.nextInt();         double minDist=Double.POSITIVE_INFINITY;   double d;   int indexI=0;   int indexJ=0;         /

12、*          *求解最近對距離存在minDist中          */         double startTime=System.currentTimeMillis();/startTime   for(int i=0;i<n-1;i+

13、)       for(int j=i+1;j<n;j+)           d=Math.sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);      if(d<minDist)           &

14、#160; minDist=d;       indexI=i;       indexJ=j;                       double endTime=System.currentTimeM

15、illis();/endTime   /*    *打印輸出最后求出的結果，最近的是哪兩個點，以及最近距離和程序用的時間    */   System.out.println("The closest pair is:("+xindexI+","+yindexI+") and ("+xindexJ+","+yindexJ+&qu

16、ot;)");   System.out.println("The closest distance is "+minDist);   System.out.println("Basic Statements take(基本語句用時) "+(endTime-startTime)+" milliseconds!");    ClosestPair2.

17、java                                        /分治算法 import java.util.*; public cla

18、ss ClosestPair2   public static void main(String args)     /*    *輸入需要比較的點的對數存在變量n中    */   Scanner in=new Scanner(System.in);   System.out.println("H

19、ow many pairs of points to compare?(有多少對點需要比較?)");   int n=in.nextInt();   /*    *輸入這些點的橫坐標和縱坐標，存儲在點數組Sn中    */   System.out.println("Please enter these po

20、ints,X-coordinate and Y-coordinate.(請輸入這些點，x坐標和y坐標)：");   Point S=new Pointn;      double startTime=System.currentTimeMillis();/starttime      for(int i=0;i<n;i+)    &

21、#160;  int x=in.nextInt();    int y=in.nextInt();    Si=new Point(x,y);    System.out.println("("+Si.getX()+","+Si.getY()+")");      /*   &#

22、160;*求出這點的x坐標的中位數mid    */   int minX=(int)Double.POSITIVE_INFINITY;   int maxX=(int)Double.NEGATIVE_INFINITY;   for(int i=0;i<n;i+)       if(Si.getX()<minX)   

23、0; minX=Si.getX();    if(Si.getX()>maxX)     maxX=Si.getX();         int mid=(minX+maxX)/2;   /*    *以mid為界把S中的點分為兩組分別存放在范型數組列表point1和point2中   

24、60;*/   ArrayList<Point> point1=new ArrayList<Point>();   ArrayList<Point> point2=new ArrayList<Point>();   for(int i=0;i<n;i+)       if(Si.getX()<=mid)  &

25、#160;  point1.add(Si);    else     point2.add(Si);      /*    *將范型數組列表轉換為數組類型S1和S2    */      Point S1=new Pointpoint1.size(); 

26、60;    Point S2=new Pointpoint2.size();      point1.toArray(S1);      point2.toArray(S2);   /*    *將S1和S2中的點按x 坐標升序排列    */   sortX(S1)

27、;   sortX(S2);   /*    *打印輸出排序后S1和S2的點    */   System.out.print("The points in S1 are:");   for(int i=0;i<S1.length;i+)    System.out.print(&q

28、uot;("+S1i.getX()+","+S1i.getY()+") ");   System.out.println();   System.out.print("The points in S2 are:");   for(int i=0;i<S2.length;i+)    System.out.print("(&

29、quot;+S2i.getX()+","+S2i.getY()+") ");   System.out.println();   /*    *求S1中點的最近對及其距離并打印輸出結果    */    double minDist1=Double.POSITIVE_INFINITY;   int indexI1=0;

30、   int indexJ1=0;   for(int i=0;i<S1.length-1;i+)         for(int j=i+1;j<S1.length;j+)             double d=Math.sqrt(Math.pow(S1i.ge

31、tX()-S1j.getX(),2)+Math.pow(S1i.getY()-S1j.getY(),2);       if(d<minDist1)                 minDist1=d;         indexI1=i;  

32、;       indexJ1=j;                           System.out.println("The closest pair in S1 is: &qu

33、ot;+"("+S1indexI1.getX()+","+S1indexI1.getY()+")"+    "and("+S1indexJ1.getX()+","+S1indexJ1.getY()+")"+",and the distance is "+minDist1);   /*    *求S2中點的最近

34、對及其距離并打印輸出結果    */    double minDist2=Double.POSITIVE_INFINITY; int indexI2=0;   int indexJ2=0;   for(int i=0;i<S2.length-1;i+)         for(int j=i+1;j&

35、lt;S2.length;j+)             double d=Math.sqrt(Math.pow(S2i.getX()-S2j.getX(),2)+Math.pow(S2i.getY()-S2j.getY(),2);       if(d<minDist2)         &

36、#160;       minDist2=d;         indexI2=i;         indexJ2=j;                   

37、        System.out.println("The closest pair in S2 is: "+"("+S2indexI2.getX()+","+S2indexI2.getY()+")"+    "and("+S2indexJ2.getX()+","+S2indexJ2.getY(

38、)+")"+",and the distance is "+minDist2);      double d1=Math.min(minDist1,minDist2);   /*    *求出S1和S2中點的橫坐標離小于d1的所有點分別存在P1和P2中    */    ArrayList<P

39、oint> pp1=new ArrayList<Point>();   ArrayList<Point> pp2=new ArrayList<Point>();   for(int i=0;i<S1.length;i+)       if(mid-S1i.getX()<d1)     pp1.add(S1i);&#

40、160;     for(int i=0;i<S2.length;i+)       if(S2i.getX()-mid)<d1)     pp2.add(S2i);      Point P1=new Pointpp1.size();      Point 

41、;P2=new Pointpp2.size();      pp1.toArray(P1);      pp2.toArray(P2);   /*將P1和P2中的點按Y坐標升序排列    */    sortY(P1);   sortY(P2);   / *求解P1和P2兩者之間可能的最近

42、對距離 */   double d2=Double.POSITIVE_INFINITY;   for(int i=0;i<P1.length;i+)       for(int j=0;j<P2.length;j+)     if(Math.abs(P1i.getY()-P2j.getY()<d1)     &

43、#160;     double temp=Math.sqrt(Math.pow(P1i.getX()-P2j.getX(),2)+Math.pow(P1i.getX()-P2j.getX(),2);      if(temp<d2)       d2=temp;           

44、0;             double endTime=System.currentTimeMillis();/endtime   /*    *打印輸出最后求出的結果，最近的是哪兩個點，以及最近距離和程序用的時間    */   System.out.print("The points

45、0;in P1 are:");   for(int i=0;i<P1.length;i+)    System.out.print("("+P1i.getX()+","+P1i.getY()+") ");   System.out.println();   System.out.print("The points in&#

46、160;P2 are:");   for(int i=0;i<P2.length;i+)    System.out.print("("+P2i.getX()+","+P2i.getY()+") ");   System.out.println();   System.out.println("d2="+d2);  

47、60; double minDist=Math.min(d1,d2);   System.out.println("The closest distance is "+minDist);      System.out.println("Basic Statements take(基本語句用時) "+(endTime-startTime)+" millise

48、conds!");      /*   *設計按點Point的x坐標升序排列的函數sortX   */  public static void sortX(Point p)     for(int i=0;i<p.length-1;i+)       for(int

49、0;j=0;j<p.length-1-i;j+)         if(pj.getX()>pj+1.getX()           int t=pj.getX();      pj.setX(pj+1.getX();      pj+1.setX(t);

50、            int n=pj.getY();      pj.setY(pj+1.getY();      pj+1.setY(n);                /*

51、0;  *設計按點Point的y坐標升序排列的函數sortY   */  public static void sortY(Point p)     for(int i=0;i<p.length-1;i+)       for(int j=0;j<p.length-1-i;j+)     

52、;    if(pj.getY()>pj+1.getY()           int t=pj.getY();      pj.setY(pj+1.getY();      pj+1.setY(t);         &#

53、160;  int n=pj.getX();      pj.setX(pj+1.getX();      pj+1.setX(n);                /*  *建立自己的類Point  */ class Point

54、 implements Cloneable   public Point()     x=0;   y=0;      public Point(int x,int y)     this.x=x;   this.y=y;     

55、0;public void setX(int x)     this.x=x;      public void setY(int y)     this.y=y;      public int getX()     return x;      public int getY()     return y;       private int x;  private int y; 實驗結果與結論：算法復雜度分析：為提高算法效率，在算法中采用預排序技術，即在使用分