武汉理工大学算法分析实验报告

1、学生学号实验课成绩学生实验报告书算法设计与分析计算机科学与技术学院李晓红软件工程zy1302班实验课程名称 开课学院 指导教师姓名 学生姓名 学生专业班级2015-2016 学年 第一学期部分内容来源于网络，有侵权请联系删除!实验课程名称：算法设计与分析实验项目名称分治与递归实验成绩实验者专业班级软件zy1302班组另U同组者实验日期2015年10月20日第一部分：实验分析与设计实验内容描述（问题域描述）1、利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时 进行时间复杂性分析；2、要求用递归的方法实现。二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验

2、步骤等，用硬件逻辑或 者算法描述）本次的解法使用的是三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。它从左到右遍历数组一次，维护一个指针 It使得alo.lt-1中的元素都小于v, 个指针gt使得agt+1.hi中的元素都大于v，个指针i使得alt.i-1中的元素都等于v，ai.gt中的元素都还未确定，如下图所示：3*way partitioning overviewpublic class Quick3waypublic static void sort(Comparable a, int Io,

3、int hi) if (lo >= hi) return;int It = lo, i = lo + 1, gt = hi;Comparable pivot = alo;while (i <= gt)int cmp = pareTo(pivot); if (cmp > 0)exch(a, i, gt-);else if (cmp < 0)exch(a, i+, lt+);elsei+;sort(a, lo, lt - 1);sort(a, gt + 1, hi);三、主要仪器设备及耗材PC机部分内容来源于网络，有侵权请联系删除!第二部分：实验调试与结果分析一

4、、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）1、2、3、调试方法描述：对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹; 实验数据："R", "B", "W", "W", "R", "W", "B", "R", "R", "W",实验现象:"B","R"ItaJigto1234518910110011RBW

5、WRW8RR州BR0111RBnrgR1211RWbyR1210RRBr KJ1310Rwj Q|1>n itE13gRB0kJ249Jn *R* DRw25gORWwk 1258RRWR LJKJ257口BRnpKRW267IDRRBRw371>n尸Ri?R381uRRw制387BBRRRRRwW3*way partitioning trace (array contents after each loop iteration4、实验过程中发现的问题：（1）边界问题：在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如： 什么时候跳出 while循环，递归什么时

6、候结束，是对指针的左半部分还是右半部分 排序等等；（2）程序的调试跳转：在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后， 会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准 确的定位程序。、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）1、实验结果:MF:Program FilesJavajdkl.8.0_66binjava 排序前：R> B,町 W, R, W, B> R, R, W, B, R 排序后：B, B, RR» Rj R, R» 叫 WJ W, WProcess finish

7、ed with exit code 02、时间复杂度：介于N和NIogN之间；3、空间复杂度：igN ；4、算法总结：三项切分的快速排序不是稳定的排序，是原地排序，它的运行效率由概率保证，同时取决 于输入元素的分布情况，对于包含大量重复元素的数组，它奖排序时间从线性对数级降低 到了线性级别，这非常的了不起。三、小结、建议及体会本次实验完成了三向切分的快速排序，其中不仅利用了分治法和递归，还对快速排序进行 了优化，使得对于存在大量重复元素的数组，能够表现更高的效率。在实验过程中，我遇到了 不少的困难，但通过自己在网上大量的浏览文献和资料，独立解决了所有问题，收获了不少。 在下次的实验中，我也会继

8、续努力的！实验课程名称：算法设计与分析实验项目名称动态规划算法实验成绩实验者专业班级软件zy1302班组另U同组者实验日期2015年12月1日第一部分：实验分析与设计实验内容描述（问题域描述）1、掌握动态规划算法求解问题的一般特征和步骤；2、使用动态规划法编程，求解 0/1背包问题；3、 问题描述：给定n种物品和一个背包，物品i的重量是 Wi,其价值为W,问如何选择装入 背包的物品，使得装入背包的物品的总价值最大？二. 实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述）0/1背包问题的特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即ci

9、v表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。则其状态转移方程便是：cim=maxci-1m,ci-1m-wi+pi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。我来解释 一下：“将前i件物品放入重量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为 v的背包中”，价值为ci-1m；如果放第i件物品，那么问题 就转化为“前i-1件物品放入剩下的重量为m-wi的背包中”，此时能获得的最大价值就是ci-1m-wi再加上通过放入第i件物品获

10、得的价值pi。算法设计如下：F0 - 0F0 - 0 for i 1 to N do for k 1 to VFik Fi-1kif（k >= Ci）then Fik max（Fik,Fi-1k-Ci+Wi）return FNV三、主要仪器设备及耗材PC机第二部分：实验调试与结果分析一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）1、调试方法：直接在方法入口断点调试，一步一步跟踪程序，弄明白程序的运行轨迹；2、实验数据：int m = 10;int n = 3; in t w = 3, 4, 5;in t p = 4, 5, 6;3、实验中遇到问题：（1

11、）刚开始对动态规划算法不熟悉，编码时出现很多的错误，花费了很多的时间;（2）没有深度理解此处为什么要使用动态规划算法，导致对问题的理解不深刻。二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）1、实验结果："F:Program FilesJavajdkl,8*0_66binjava 第0号背包：0第丄号背包：1第2号背包；1Process finished with exit code 02、时间复杂度：nm;3、空间复杂度：nm （可优化至 m）;4、算法总结：动态规划的基本思想：将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求

12、 最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一 步的结果，自底向上的求解。三、小结、建议及体会本次实验解决了 0/1背包问题，掌握动态规划算法求解问题的一般特征和步骤。在实验过 程中，我遇到了很多不懂的问题，但通过老师和同学们的帮助，和自己的努力，最终解决了所 有问题，收获颇丰。在今后的算法设计中，我会迎难而上！源代码:实验一：import java.util.Arrays;public class Quick3waypublic static void sort(Comparable a)sort(a, 0, a.length - 1);public sta

13、tic void sort(Comparable a, int Io, int hi) if (lo >= hi)return;in t lt = lo, i = lo + 1, gt = hi;Comparable pivot = alo;while (true)int cmp = pareTo(pivot);if (cmp > 0)exch(a, i, gt-);else if (cmp < 0)exch(a, i+, lt+);elsei+;if (i > gt)break;sort(a, lo, lt - 1);sort(a, gt + 1, hi)

14、;private static void exch(Comparable a, int i, int j) Comparable temp = ai;ai = ajaj = temp;public static void show(Comparable a)System.out.pri ntl n( Arrays.toStri ng(a);public static void main(String args)"W", "B",Stri nga = "R","B","W", "W&qu

15、ot;, "R","W", "B","R","R","R"System.out.pri ntln(”排序前：t");show(a);sort(a); /对数组a进行排序System.out.pri ntln(”排序后：t");show(a);实验二：package com.shaw n;public class PackageOlpublic in t pack(i nt m, int n, int w, int p)civ表示前i件物品恰放入一个重量为m

16、的背包可以获得的最大价值in t c = new in tn + 1m + 1;for (int i = 0; i < n + 1; i+)ci0 = 0;for (int j = 0; j < m + 1; j+)c0j = 0;for (int i = 1; i < n + 1; i+)for (int j = 1; j < m + 1; j+)时,II当物品为i件重量为j时，如果第i件的重量(wi-1)小于重量jcij为下列两种情况之一：II(1)物品i不放入背包中，所以 cij 为ci-1j 的值II(2)物品i放入背包中，则背包剩余重量为 j-wi-1, 所以

17、cij为ci-1j-wi-1的值加上当前物品i的价值if (wi - 1 <= j)if (ci - 1j < (ci - 1j - wi - 1 + pi - 1)cij = ci - 1j - wi - 1 + pi - 1;elsecij = ci - 1j;elsecij = ci - 1j;return c;II 逆推法求出最优解public int printPack(int c, int w, int m, int n)int x = new intn;II从最后一个状态记录c nm开始逆推for (int i = n; i > 0; i-)含了/如果cim 大于ci-1m ，说 明cim这个最优值中包wi-1(注意这里是i-1，因为c数组长度是n+1)if (cim > ci - 1m)xi - 1 = 1;m -= wi - 1;for (int j = 0; j