中南大学算法实验报告综述.docx

算法分析与设计 实验报告 学 院：　信息科学与工程学院 专业班级：　 i got7 指导老师： 　　 　 学 号： 　　 i got7 姓 名： 　　　 鸟宝宝 a. 合并排序 合并排序是分治法的应用，把需要排序的数组A[1 - n]，一分为二A[1 -n/2]和A[n/2+1 - n]，然后在对每一个子数组递归排序，接着再把这两个子数组合并成一个有序的数组。 算法描述： 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾 关键代码： private static void Sort(int[] a, int left, int right) { if(left=right) return; int mid = (left + right) / 2; Sort(a, left, mid); Sort(a, mid + 1, right); merge(a, left, mid, right); } private static void merge(int[] a, int left, int mid, int right) { int[] tmp = new int[a.length]; int r1 = mid + 1; int tIndex = left; int cIndex=left; // 逐个归并 while(left =mid r1 = right) { if (a[left] = a[r1]) tmp[tIndex++] = a[left++]; else tmp[tIndex++] = a[r1++]; } // 将左边剩余的归并 while (left =mid) { tmp[tIndex++] = a[left++]; } // 将右边剩余的归并 while ( r1 = right ) { tmp[tIndex++] = a[r1++]; } System.out.print( 第+(++number)+次排序: ); //从临时数组拷贝到原数组 while(cIndex=right){ a[cIndex]=tmp[cIndex]; //输出中间归并排序结果 System.out.print(a[cIndex]+ ); cIndex++; } System.out.println(); } 运行结果截屏： 算法分析：合并排序满足分治法的基本公式 T(n)=2T(n/2)+f(n) 其中2T(n/2)是2个子问题求解，即对两个子数组排序； 而f(n)是将子问题合起来求原始问题的解的代价，即将两个有序的子数组合并为一个有序的数组。在最终的合并阶段，键值的比较的代价，在最坏的情况下是n-1 ，（比如每个数组的第i号轮流被放入数组），根据主定理，T(n)=O(nlogn)。 b. 0-1背包问题 问题描述：在0 / 1背包问题中，需对容量为W 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品j 的重量为wj ，价值为vi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 有3中方法可解： 动态规划法： 递推式： K(w,