算法设计与分析实验报告

算法设计与分析 实验报告 教师 学号 姓名 实验一 串匹配问题 实验目的 1 深刻理解并掌握蛮力法的设计思想 2 提高应用蛮力法设计算法的技能 3 理解这样一个观点 用蛮力法设计的算法 一般来说 经过适度的努力 后 都可以对算法的第一个版本进行一定程度的改良 改进其时间性能 3 实验要求 1 实现 BF 算法 2 实现 BF 算法的改进算法 KMP 算法和 BM 算法 3 对上述 3 个算法进行时间复杂性分析 并设计实验程序验证 分析结果 include stdio h include conio h include 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 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 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 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 有一个重要性质是事先不用知道串的长度 而基于跳跃的算法是需要用字符 串长度来判断结束位置的 实验二 最近对问题 2 实验目的 1 进一步掌握递归算法的设计思想以及递归程序的调试技术 2 理解这样一个观点 分治与递归经常同时应用在算法设计之中 3 实验要求 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 maxX maxX S i getX int mid minX maxX 2 以 mid 为界把 S 中的点分为两组分别存放在范型数组列表 point1 和 point2 中 ArrayList point1 new ArrayList ArrayList point2 new ArrayList 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 pp1 new ArrayList ArrayList pp2 new ArrayList 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 p p2 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 jp 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 jp 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 枚硬币问题 2 实验目的 1 深刻理解并掌握减治法的设计思想并能熟练运用 2 提高应用减治法设计算法的技能 3 理解这样一个观点 建立正确的模型对于问题的求解是非常重要 的 3 实验要求 1 设计减治算法实现 8 枚硬币问题 2 设计实验程序 考察用减治技术设计的算法是否高效 3 扩展算法 使之能处理 n 枚硬币中有 1 枚假币的问题 include include 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