学生学号实验课成绩学生实验报告书实验课程名称算法设计与分析开课学院计算机科学与技术学院指导教师姓名晓红学生姓名学生专业班级软件工程zy1302班2015 -- 2016 学年第一学期实验课程名称：算法设计与分析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 = a[lo];while (i <= gt){int cmp = a[i].compareTo(pivot);if (cmp > 0)exch(a, i, gt--);else if (cmp < 0)第二部分：实验调试与结果分析一、调试过程（包括调试法描述、实验数据记录，实验现象记录，实验过程发现的问题等）1、调试法描述：对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹；2、实验数据："R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"；3、实验现象：4、实验过程中发现的问题：（1）边界问题：在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如：什么时候跳出while循环，递归什么时候结束，是对指针的左半部分还是右半部分排序等等；（2）程序的调试跳转：在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后，会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准确的定位程序。
二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）1、实验结果：2、时间复杂度：介于N和NlogN之间；3、空间复杂度：lgN；4、算法总结：三项切分的快速排序不是稳定的排序，是原地排序，它的运行效率由概率保证，同时取决于输入元素的分布情况，对于包含大量重复元素的数组，它奖排序时间从线性对数级降低到了线性级别，这非常的了不起。
三、小结、建议及体会本次实验完成了三向切分的快速排序，其中不仅利用了分治法和递归，还对快速排序进行了优化，使得对于存在大量重复元素的数组，能够表现更高的效率。
在实验过程中，我遇到了不少的困难，但通过自己在网上大量的浏览文献和资料，独立解决了所有问题，收获了不少。
在下次的实验中，我也会继续努力的！实验课程名称：算法设计与分析第二部分：实验调试与结果分析一、调试过程（包括调试法描述、实验数据记录，实验现象记录，实验过程发现的问题等）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、算法总结：动态规划的基本思想：将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。
通常用来求最优解，且最优解的局部也是最优的。
求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。
三、小结、建议及体会源代码：实验一：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 = a[lo];while (true){int cmp = a[i].compareTo(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);}private static void exch(Comparable[] a, int i, int j) {Comparable temp = a[i];a[i] = a[j];a[j] = 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 .shawn;public class Package01{public int[][] pack(int m, int n, int w[], int p[]){//c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值int c[][] = new int[n + 1][m + 1];for (int i = 0; i < n + 1; i++)c[i][0] = 0;for (int j = 0; j < m + 1; j++)c[0][j] = 0;for (int i = 1; i < n + 1; i++){for (int j = 1; j < m + 1; j++){//当物品为i件重量为j时，如果第i件的重量(w[i-1])小于重量j时，c[i][j]为下列两种情况之一：//(1)物品i不放入背包中，所以c[i][j]为c[i-1][j]的值//(2)物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值if (w[i - 1] <= j){if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];elsec[i][j] = c[i - 1][j];}elsec[i][j] = c[i - 1][j];}}return c;}// 逆推法求出最优解public int[] printPack(int c[][], int w[], int m, int n){int x[] = new int[n];//从最后一个状态记录c[n][m]开始逆推for (int i = n; i > 0; i--){//如果c[i][m]大于c[i-1][m]，说明c[i][m]这个最优值中包含了w[i-1](注意这里是i-1，因为c数组长度是n+1)if (c[i][m] > c[i - 1][m]){x[i - 1] = 1;m -= w[i - 1];}}for (int j = 0; j < n; j++)System.out.println("第" + j + "号背包：" + x[j]);return x;}public static void main(String args[]){int m = 10; // 背包容量int n = 3; // 物品数量int w[] = {3, 4, 5}; // 物品重量int p[] = {4, 5, 6}; // 物品价值Package01 pack = new Package01();int c[][] = pack.pack(m, n, w, p);pack.printPack(c, w, m, n);}}。