算法设计与分析实验报告Word格式文档下载.docx
《算法设计与分析实验报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告Word格式文档下载.docx（16页珍藏版）》请在冰点文库上搜索。
{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）;
//前缀函数值,用于KMP算法
intGETNEXT（chart[],intb）
{intNEXT[10];
NEXT[0]=-1;
intj,k;
j=0;
k=-1;
while（j<
strlen（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;
n=strlen（t）;
\n*****KMP算法*****\n"
while（a<
=m-n）
while（s[a]==t[b]&
if（b==n）
b=GETNEXT（t,b）;
a=a-b;
if（b==-1）b++;
}//滑动距离函数,用于BM算法
intDIST（chart[],charc）
{inti=0,x=1;
intn;
while（x&
i!
=n-1）
if（t[i]==c）
x=0;
elsei++;
}
if（i!
n=n-1-i;
returnn;
}//BM算法
结果分析与体会：
glibc里的strstr函数用的是brute-force（naive）算法，它与其它算法的区别是strstr不对pattern（needle）进行预处理，所以用起来很方便。
理论复杂度O
（mn）,
实际上，平均复杂度为O（n）,
大部分情况下高度优化的算法性能要优于基于自动机的匹配算法，BF有一个重要性质是事先不用知道串的长度，而基于跳跃的算法是需要用字符串长度来判断结束位置的。
实验二：
最近对问题
2、实验目的：
（1）进一步掌握递归算法的设计思想以及递归程序的调试技术;
（2）理解这样一个观点:
分治与递归经常同时应用在算法设计之中。
（1）分别用蛮力法和分治法求解最近对问题;
（2）分析算法的时间性能,设计实验程序验证分析结论。
ClosestPair1.java
//蛮力算法
import
java.util.*;
public
class
ClosestPair1
{
static
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];
y=new
*输入这些点的横坐标和纵坐标分别存储在x[n]和y[n]
Please
enter
these
points,X-coordinate（请输入这些点,横坐标）:
"
for（int
i=0;
n;
i++）
x[i]=in.nextInt（）;
}
points,Y-coordinate（请输入这些点,纵坐标）:
y[i]=in.nextInt（）;
double
minDist=Double.POSITIVE_INFINITY;
d;
indexI=0;
indexJ=0;
*求解最近对距离存在minDist中
startTime=System.currentTimeMillis（）;
//startTime
n-1;
j=i+1;
j<
j++）
d=Math.sqrt（（x[i]-x[j]）*（x[i]-x[j]）+（y[i]-y[j]）*（y[i]-y[j]））;
if（d<
minDist）
minDist=d;
indexI=i;
indexJ=j;
endTime=System.currentTimeMillis（）;
//endTime
*打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间
The
closest
pair
is:
（"
+x[indexI]+"
"
+y[indexI]+"
）
and
+x[indexJ]+"
+y[indexJ]+"
distance
is
+minDist）;
Basic
Statements
take（基本语句用时）
+（endTime-startTime）+"
milliseconds!
ClosestPair2.java
//分治算法
ClosestPair2
*输入这些点的横坐标和纵坐标，存储在点数组S[n]中
points,X-coordinate
Y-coordinate.（请输入这些点，x坐标和y坐标）：
Point[]
S=new
Point[n];
//starttime
x=in.nextInt（）;
y=in.nextInt（）;
S[i]=new
Point（x,y）;
+S[i].getX（）+"
+S[i].getY（）+"
*求出这点的x坐标的中位数mid
minX=（int）Double.POSITIVE_INFINITY;
maxX=（int）Double.NEGATIVE_INFINITY;
if（S[i].getX（）<
minX）
minX=S[i].getX（）;
if（S[i].getX（）>
maxX）
maxX=S[i].getX（）;
mid=（minX+maxX）/2;
*以mid为界把S中的点分为两组分别存放在范型数组列表point1和point2中
ArrayList<
Point>
point1=new
（）;
point2=new
=mid）
point1.add（S[i]）;
else
point2.add（S[i]）;
*将范型数组列表转换为数组类型S1和S2
S1=new
Point[point1.size（）];
S2=new
Point[point2.size（）];
point1.toArray（S1）;
point2.toArray（S2）;
*将S1和S2中的点按x
坐标升序排列
sortX（S1）;
sortX（S2）;
*打印输出排序后S1和S2的点
System.out.print（"
in
S1
are:
S1.length;
+S1[i].getX（）+"
+S1[i].getY（）+"
System.out.println（）;
S2
S2.length;
+S2[i].getX（）+"
+S2[i].getY（）+"
*求S1中点的最近对及其距离并打印输出结果
minDist1=Double.POSITIVE_INFINITY;
indexI1=0;
indexJ1=0;
S1.length-1;
d=Math.sqrt（Math.pow（（S1[i].getX（）-S1[j].getX（））,2）+Math.pow（（S1[i].getY（）-S1[j].getY（））,2））;
minDist1）
minDist1=d;
indexI1=i;
indexJ1=j;
+"
+S1[indexI1].getX（）+"
+S1[indexI1].getY（）+"
+
and（"
+S1[indexJ1].getX（）+"
+S1[indexJ1].getY（）+"
and
the
+minDist1）;
*求S2中点的最近对及其距离并打印输出结果
minDist2=Double.POSITIVE_INFINITY;
indexI2=0;
indexJ2=0;
S2.length-1;
d=Math.sqrt（Math.pow（（S2[i].getX（）-S2[j].getX（））,2）+Math.pow（（S2[i].getY（）-S2[j].getY（））,2））;
minDist2）
minDist2=d;
indexI2=i;
indexJ2=j;
+S2[indexI2].getX（）+"
+S2[indexI2].getY（）+"
+S2[indexJ2].getX（）+"
+S2[indexJ2].getY（）+"
+minDist2）;
d1=Math.min（minDist1,minDist2）;
*求出S1和S2中点的横坐标离小于d1的所有点分别存在P1[]和P2[]中
pp1=new
pp2=new
if（（mid-S1[i].getX（））<
d1）
pp1.add（S1[i]）;
if（（S2[i].getX（）-mid）<
pp2.add（S2[i]）;
P1=new
Point[pp1.size（）];
P2=new
Point[pp2.size（）];
pp1.toArray（P1）;
pp2.toArray（P2）;
/**将P1和P2中的点按Y坐标升序排列
sortY（P1）;
sortY（P2）;
/
*求解P1和P2两者之间可能的最近对距离
d2=Double.POSITIVE_INFINITY;
P1.length;
j=0;
P2.length;
if（Math.abs（P1[i].getY（）-P2[j].getY（））<
temp=Math.sqrt（Math.pow（（P1[i].getX（）-P2[j].getX（））,2）+Math.pow（（P1[i].getX（）-P2[j].getX（））,2））;
if（temp<
d2）
d2=temp;
//endtime
P1
+P1[i].getX（）+"
+P1[i].getY（）+"
P2
+P2[i].getX（）+"
+P2[i].getY（）+"
d2="
+d2）;
minDist=Math.min（d1,d2）;
*设计按点Point的x坐标升序排列的函数sortX
sortX（Point[]
p）
p.length-1;
p.length-1-i;
if（p[j].getX（）>
p[j+1].getX（））
t=p[j].getX（）;
p[j].setX（p[j+1].getX（））;
p[j+1].setX（t）;
n=p[j].getY（）;
p[j].setY（p[j+1].getY（））;
p[j+1].setY（n）;
*设计按点Point的y坐标升序排列的函数sortY
sortY（Point[]
if（p[j].getY（）>
p[j+1].getY（））
t=p[j].getY（）;
p[j+1].setY（t）;
n=p[j].getX（）;
p[j+1].setX（n）;
*建立自己的类Point
Point
implements
Cloneable
Point（）
x=0;
y=0;
Point（int
x,int
y）
this.x=x;
this.y=y;
setX（int
x）
setY（int
getX（）
return
x;
getY（）
y;
private
实验结果与结论：
算法复杂度分析：
为提高算法效率，在算法中采用预排序技术，即在使用分治法之前，预先将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枚硬币问题
（1）深刻理解并掌握减治法的设计思想并能熟练运用；
（2）提高应用减治法设计算法的技能；
（3）理解这样一个观点：
建立正确的模型对于问题的求解是非常重要的。
（1）、设计减治算法实现8枚硬币问题；
（2）、设计实验程序，考察用减治技术设计的算法是否高效；
（3）、扩展算法，使之能处理n枚硬币中有1枚假币的问题。
#include<
stdio.h>
#include<
stdlib.h>
intFindmax
（floata[],intn,intm）//用天平比较1~3次即可
{floattemp=a[n];
intadr=n;
for（inti=n;
{
if（temp<
a[i]）
temp=a[i];
adr=i;
break;
}
returnadr;
intFindmin（floata[],int
升级会员 