《【2017年整理】算法设计与分析实验报告》由会员分享，可在线阅读，更多相关《【2017年整理】算法设计与分析实验报告（12页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析实验报告教师： 学号：姓名： 实验一：串匹配问题实验目的： (1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法 , 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。3、实验要求： ( 1) 实现 BF 算法; (2 ) 实现 BF 算法的改进算法 : KMP 算法和 BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证分析结果。#include stdio.h #include conio.h#include /BF 算法 i
2、nt 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;imaxX) maxX=Si.getX(); int mid=(minX+maxX)/2; /* *以 mid 为界把 S 中的点分为两组分别存放在范型数组列表 point1 和 point2 中 */ ArrayList point1=new ArrayList(); ArrayList point2=new ArrayList(); for(int i=0;i p
3、p1=new ArrayList(); ArrayList pp2=new ArrayList();for(int i=0;ipj+1.getX() int t=pj.getX(); pj.setX(pj+1.getX(); pj+1.setX(t); int n=pj.getY(); pj.setY(pj+1.getY(); pj+1.setY(n); /* *设计按点 Point 的 y 坐标升序排列的函数 sortY */ public static void sortY(Point p) for(int i=0;ipj+1.getY() int t=pj.getY(); pj.setY
4、(pj+1.getY(); pj+1.setY(t); int n=pj.getX(); pj.setX(pj+1.getX(); pj+1.setX(n); /* *建立自己的类 Point */ class Point implements Cloneable public Point() x=0; y=0; public Point(int x,int y) this.x=x; this.y=y; public void setX(int x) this.x=x; public void setY(int y) this.y=y; public int getX() return x;
5、public int getY() return y; private int x; private int y; 实验结果与结论：算法复杂度分析：为提高算法效率，在算法中采用预排序技术，即在使用分治法之前，预先将 S 中的 n 个点依其 y 坐标排序好。经过预排序处理后的算法所需的计算时间 T(n)满足递归方程：当 n 小于 4 时，T(n)=O(1)；当 n 大于等于 4 时，T(n)=2T(n/2)+O(n)。由此易知，T(n)=O(nlogn)。预排序所需的计算时间显然为 O(nlogn)。因此，整个算法所需的计算时间为 O(nlogn)。在渐近的意义下，此算法已是最优算法。实验三：8
6、 枚硬币问题2、实验目的： （1） 深刻理解并掌握减治法的设计思想并能熟练运用； （2） 提高应用减治法设计算法的技能； （3） 理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。3、实验要求： （1） 、设计减治算法实现 8 枚硬币问题； （2） 、设计实验程序，考察用减治技术设计的算法是否高效； （3） 、扩展算法，使之能处理 n 枚硬币中有 1 枚假币的问题。#include #include int Findmax(float a,int n,int m)/用天平比较 13 次即可 float temp = an; int adr=n; for(int i=n;i ai) t
7、emp = ai;break; return adr; int Devide (float a) float left0 = 0.0; float right0 = 0.0; float left1 = 0.0; float right1 = 0.0; int adr = 0; int i,j; /先比较前四个和后四个硬币 for(i = 0;i Weight(真) adr = Findmax (a,4,8);/找到其中最重的便是假的 else/若 Weight（1234） Weight（5678） for(i = 0;i Weight(真) adr = Findmax (a,0,4);/找到
8、其中最重的便是假的 else/若 Weight（12）= Weight（34）,则说明假币在后四个当中，而且假币 Weight(假) Weight(真) adr = Findmin (a,4,8);/找到其中最轻的便是假的 return adr; int main( ) int i=1; float a8 = 0; printf(请输入 8 枚硬币的重量：); for(i = 0;i 8;i+) scanf(%f,&ai) printf(假币的位置为：%d n,Devide(a)+1); system(pause); return 0; 结果分析与体会：通过硬币问题，让我更加理解了减治法的使用，让我对减治法有了更深的理解，对于以后的编程思想有了更深的研究。
