算法设计与分析
实验报告
教师：
学号：
姓名：
实验一：串匹配问题
实验目的： (1) 深刻理解并掌握蛮力法的设计思想;
(2) 提高应用蛮力法设计算法的技能;
(3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。
三、实验要求： ( 1) 实现 BF 算法;
(2 ) 实现 BF 算法的改进算法: KMP 算法和 BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证分析结果。
#include "stdio.h"
#include "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(s[a]==t[b]&&b!=n)
{
a++; b++; }
if(b==n)
{ printf("查找成功!!\n\n"); return 0;
}
}
printf("找不到%s\n\n",t); return 0; }
//前缀函数值,用于KMP算法
int GETNEXT(char t[],int b)
{ int NEXT[10]; NEXT[0]=-1;
int j,k; j=0; k=-1; while(j<strlen(t))
{
if ((k==-1)||(t[j]==t[k]))
{
j++;
k++;
NEXT[j]=k; }
else k=NEXT[k];
}
b=NEXT[b];
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("\n*****KMP算法*****\n");
while(a<=m-n)
{
while(s[a]==t[b]&&b!=n)
{
a++;
b++; }
if(b==n)
{
printf("查找成功!!\n\n");
return 0;
}
b=GETNEXT(t,b);
a=a-b;
if(b==-1) b++;
}
printf("找不到%s\n\n",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(t[i]==c)
x=0;
else i++;
}
if(i!=n-1)
n=n-1-i;
return n; } //BM算法
结果分析与体会： glibc里的strstr函数用的是brute-force(naive)算法，它与其它算法的区别是strstr不对pattern(needle)进行预处理，所以用起来很方便。理论复杂度O
(mn), 实际上，平均复杂度为O(n), 大部分情况下高度优化的算法性能要优于基于自动机的匹配算法，BF有一个重要性质是事先不用知道串的长度，而基于跳跃的算法是需要用字符串长度来判断结束位置的。
实验二：最近对问题
二、实验目的：( 1) 进一步掌握递归算法的设计思想以及递归程序的调试技术;
(2 ) 理解这样一个观点: 分治与递归经常同时应用在算法设计之中。
三、实验要求：( 1) 分别用蛮力法和分治法求解最近对问题;
(2 ) 分析算法的时间性能, 设计实验程序验证分析结论。
ClosestPair1.java //蛮力算法
import java.util.*; public class ClosestPair1 {
public 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]; int[] y=new int[n]; /**
*输入这些点的横坐标和纵坐标分别存储在x[n]和y[n] */
System.out.println("Please enter these points,X-coordinate(请输入这些点,横坐标):"); for(int i=0;i<n;i++) {
x[i]=in.nextInt(); }
System.out.println("Please enter these points,Y-coordinate(请输入这些点,纵坐标):"); for(int i=0;i<n;i++) {
y[i]=in.nextInt(); }
double minDist=Double.POSITIVE_INFINITY; double d; int indexI=0; int indexJ=0; /**
*求解最近对距离存在minDist中 */
double startTime=System.currentTimeMillis();//startTime for(int i=0;i<n-1;i++) {
for(int j=i+1;j<n;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; } } }
double endTime=System.currentTimeMillis();//endTime /**
*打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间 */
System.out.println("The
closest
pair
is:("+x[indexI]+","+y[indexI]+")
and
("+x[indexJ]+","+y[indexJ]+")");
System.out.println("The closest distance is "+minDist);
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!"); }
}
ClosestPair2.java //分治算法
import java.util.*; public class ClosestPair2 {
public 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(); /**
*输入这些点的横坐标和纵坐标，存储在点数组S[n]中 */
System.out.println("Please enter these points,X-coordinate and Y-coordinate.(请输入这些点，x坐标和y坐标)：");
Point[] S=new Point[n];
double startTime=System.currentTimeMillis();//starttime
for(int i=0;i<n;i++) {
int x=in.nextInt(); int y=in.nextInt(); S[i]=new Point(x,y);
System.out.println("("+S[i].getX()+","+S[i].getY()+")"); } /**
*求出这点的x坐标的中位数mid */
int minX=(int)Double.POSITIVE_INFINITY; int maxX=(int)Double.NEGATIVE_INFINITY; for(int i=0;i<n;i++) {
if(S[i].getX()<minX) minX=S[i].getX(); if(S[i].getX()>maxX) maxX=S[i].getX(); }
int mid=(minX+maxX)/2; /**
*以mid为界把S中的点分为两组分别存放在范型数组列表point1和point2中 */
ArrayList<Point> point1=new ArrayList<Point>(); ArrayList<Point> point2=new ArrayList<Point>(); for(int i=0;i<n;i++) {
if(S[i].getX()<=mid) point1.add(S[i]); else
point2.add(S[i]); } /**
*将范型数组列表转换为数组类型S1和S2 */
Point[] S1=new Point[point1.size()]; Point[] S2=new Point[point2.size()]; point1.toArray(S1); point2.toArray(S2); /**
*将S1和S2中的点按x 坐标升序排列 */ sortX(S1); sortX(S2); /**
*打印输出排序后S1和S2的点 */
System.out.print("The points in S1 are:"); for(int i=0;i<S1.length;i++)
System.out.print("("+S1[i].getX()+","+S1[i].getY()+") "); System.out.println();
System.out.print("The points in S2 are:"); for(int i=0;i<S2.length;i++)
System.out.print("("+S2[i].getX()+","+S2[i].getY()+") "); System.out.println(); /**
*求S1中点的最近对及其距离并打印输出结果 */
double minDist1=Double.POSITIVE_INFINITY; int indexI1=0; 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((S1[i].getX()-S1[j].getX()),2)+Math.pow((S1[i].getY()-S1[j].getY()),2)); if(d<minDist1) {
minDist1=d; indexI1=i; indexJ1=j; } } }
System.out.println("The closest pair in S1 is: "+"("+S1[indexI1].getX()+","+S1[indexI1].getY()+")"+ "and("+S1[indexJ1].getX()+","+S1[indexJ1].getY()+")"+",and the distance is "+minDist1); /**
*求S2中点的最近对及其距离并打印输出结果 */
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<S2.length;j++) { double
d=Math.sqrt(Math.pow((S2[i].getX()-S2[j].getX()),2)+Math.pow((S2[i].getY()-S2[j].getY()),2)); if(d<minDist2) {
minDist2=d; indexI2=i; indexJ2=j; } } }
System.out.println("The closest pair in S2 is: "+"("+S2[indexI2].getX()+","+S2[indexI2].getY()+")"+ "and("+S2[indexJ2].getX()+","+S2[indexJ2].getY()+")"+",and the distance is "+minDist2);
double d1=Math.min(minDist1,minDist2); /**
*求出S1和S2中点的横坐标离小于d1的所有点分别存在P1[]和P2[]中 */
ArrayList<Point> pp1=new ArrayList<Point>(); ArrayList<Point> pp2=new ArrayList<Point>(); for(int i=0;i<S1.length;i++) {
if((mid-S1[i].getX())<d1) pp1.add(S1[i]); }
for(int i=0;i<S2.length;i++) {
if((S2[i].getX()-mid)<d1) pp2.add(S2[i]); }
Point[] P1=new Point[pp1.size()]; Point[] P2=new Point[pp2.size()]; pp1.toArray(P1); pp2.toArray(P2);
/**将P1和P2中的点按Y坐标升序排列 */ sortY(P1); sortY(P2);
/ *求解P1和P2两者之间可能的最近对距离 */
double d2=Double.POSITIVE_INFINITY; for(int i=0;i<P1.length;i++)
{
for(int j=0;j<P2.length;j++)
{
if(Math.abs(P1[i].getY()-P2[j].getY())<d1)
{
double 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;
}
}
}
double endTime=System.currentTimeMillis();//endtime /**
*打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间 */
System.out.print("The points in P1 are:"); for(int i=0;i<P1.length;i++)
System.out.print("("+P1[i].getX()+","+P1[i].getY()+") "); System.out.println();
System.out.print("The points in P2 are:"); for(int i=0;i<P2.length;i++)
System.out.print("("+P2[i].getX()+","+P2[i].getY()+") "); System.out.println();
System.out.println("d2="+d2); double minDist=Math.min(d1,d2);
System.out.println("The closest distance is "+minDist);
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!"); } /**
*设计按点Point的x坐标升序排列的函数sortX */
public static void sortX(Point[] p) {
for(int i=0;i<p.length-1;i++) {
for(int j=0;j<p.length-1-i;j++) {
if(p[j].getX()>p[j+1].getX()) {
int t=p[j].getX();
p[j].setX(p[j+1].getX()); p[j+1].setX(t);
int n=p[j].getY(); p[j].setY(p[j+1].getY()); p[j+1].setY(n); } } } } /**
*设计按点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++) {
if(p[j].getY()>p[j+1].getY()) {
int t=p[j].getY(); p[j].setY(p[j+1].getY()); p[j+1].setY(t);
int n=p[j].getX(); p[j].setX(p[j+1].getX()); p[j+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; }
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枚硬币问题
二、实验目的： （1） 深刻理解并掌握减治法的设计思想并能熟练运用；
（2） 提高应用减治法设计算法的技能；
（3） 理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。
三、实验要求： （1）、设计减治算法实现8枚硬币问题；
（2）、设计实验程序，考察用减治技术设计的算法是否高效；
（3）、扩展算法，使之能处理n枚硬币中有1枚假币的问题。
#include<stdio.h> #include<stdlib.h>
int Findmax
(float a[],int n,int m)//用天平比较1~3次即可
{ float temp = a[n];
int adr=n;
for(int i=n;i<m;i++)
{
if(temp < a[i]）
{
temp = a[i];
adr = i;
break; }
}
return adr; }
int Findmin (float a[],int n,int m)//用天平比较1~3次即可
{ float temp = a[n];
int adr=n;
for(int i=n;i<m;i++)
{
if(temp > a[i])
{
temp = a[i];
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 <8;i++)
{
if(i<4)
left0 +=a[i];
else
right0 +=a[i]; } //此处用天枰比较一次即可
if(left0 < right0)//若Weight（1234）< Weight（5678）
{
for(i = 0;i <4;i++)
{
if(i<2)
left1+=a[i];
else
right1+=a[i];
}
if(left1 != right1)//若Weight（12）！= Weight（34）,则说明假币在前四个当中，而且假币Weight(假)< Weight(真)
{
adr = Findmin (a,0,4);//找到其中最轻的便是假的 }
else//若Weight（12）== Weight（34）,则说明假币在后四个当中，而且假币Weight(假)> Weight(真)
{ adr = Findmax (a,4,8);//找到其中最重的便是假的 }
}
else//若Weight（1234）> Weight（5678）
{ for(i = 0;i <4;i++)
{
if(i<2)
left1+=a[i];
else
right1+=a[i];
}
if(left1 != right1)//若Weight（12）！= Weight（34）,则说明假币在前四个当中，而且假币Weight(假)> Weight(真)
{ adr = Findmax (a,0,4);//找到其中最重的便是假的 }
else//若Weight（12）== Weight（34）,则说明假币在后四个当中，而且假币Weight(假)< Weight(真)
{ adr = Findmin (a,4,8);//找到其中最轻的便是假的 } }
return adr; }
int main( )
{ int i=1;
float a[8] = {0};
printf("请输入8枚硬币的重量：");
for(i = 0;i < 8;i++)
{ scanf("%f",&a[i]) }
printf("假币的位置为：%d \n",Devide(a)+1); system("pause");
return 0; }
结果分析与体会：通过硬币问题，
让我更加理解了减治法的使用，让我对减治法有了更深的理解，对于以
后的编程思想有了更深的研究。