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

学生学号 实验课成绩学 生 实 验 报 告 书实验课程名称算法设计与分析开 课 学 院计算机科学与技术学院指导教师姓名李晓红学 生 姓 名学生专业班级软件工程zy1302班2015-2016学年第一学期实验课程名称： 算法设计与分析 实验项目名称分治与递归实验成绩实 验 者专业班级软件zy1302班组 别同 组 者实验日期2015年10月20日第一部分：实验分析与设计1 实验内容描述（问题域描述）1、 利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析；2、 要求用递归的方法实现。二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）本次的解法使用的是“三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。它从左到右遍历数组一次，维护一个指针lt使得alo.lt-1中的元素都小于v，一个指针gt使得agt+1.hi中的元素都大于v，一个指针i使得alt.i-1中的元素都等于v，ai.gt中的元素都还未确定，如下图所示：public class Quick3way public static void sort(Comparable a, int lo, int hi) if (lo = hi) return; int lt = lo, i = lo + 1, gt = hi; Comparable pivot = alo; while (i 0) exch(a, i, gt-); else if (cmp = Ci) then Fik max(Fik,Fi-1k-Ci+Wi) return FNV三、主要仪器设备及耗材PC机第二部分：实验调试与结果分析一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）1、 调试方法：直接在方法入口断点调试，一步一步跟踪程序，弄明白程序的运行轨迹；2、 实验数据：int m = 10;int n = 3;int w = 3, 4, 5;int p = 4, 5, 6;3、 实验中遇到问题：（1） 刚开始对动态规划算法不熟悉，编码时出现很多的错误，花费了很多的时间；（2） 没有深度理解此处为什么要使用动态规划算法，导致对问题的理解不深刻。二、 实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）1、 实验结果：2、时间复杂度：nm；3、空间复杂度：nm（可优化至m）；4、 算法总结：动态规划的基本思想：将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。三、小结、建议及体会本次实验解决了0/1背包问题，掌握动态规划算法求解问题的一般特征和步骤。在实验过程中，我遇到了很多不懂的问题，但通过老师和同学们的帮助，和自己的努力，最终解决了所有问题，收获颇丰。在今后的算法设计中，我会迎难而上！源代码：实验一：import java.util.Arrays;public class Quick3way public static void sort(Comparable a) sort(a, 0, a.length - 1); public static void sort(Comparable a, int lo, int hi) if (lo = hi) return; int 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 gt) break; sort(a, lo, lt - 1); sort(a, gt + 1, hi); private static void exch(Comparable a, int i, int j) Comparable temp = ai; ai = aj; aj = temp; public static void show(Comparable a) System.out.println(Arrays.toString(a); public static void main(String args) String a = R, B, W, W, R, W, B, R, R, W, B, R; System.out.println(排序前：t); show(a); sort(a); / 对数组a进行排序 System.out.println(排序后：t); show(a); 实验二：package com.shawn;public class Package01 public int pack(int m, int n, int w, int p) /civ表示前i件物品恰放入一个重量为m的背包可以获得的最大价值 int c = new intn + 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+) /当物品为i件重量为j时，如果第i件的重量(wi-1)小于重量j时，cij为下列两种情况之一： /(1)物品i不放入背包中，所以cij为ci-1j的值 /(2)物品i放入背包中，则背包剩余重量为j-wi-1,所以cij为ci-1j-wi-1的值加上当前物品i的价值 if (wi - 1 = j) if (ci - 1j 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 n; j+) System.out.println(第 + j + 号背包： + xj); return x; public static void main(String args) int m = 10; / 背包容量 int n = 3; / 物品数