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

学生学号实验课成绩或族理）大字学生实验报告书实验课程名称 开课学院 指导教师姓名 学生姓名 学生专业班级算法设计与分析计算机科学与技术学院李晓红软件工程zy1302班2015-2016学年第一学期部分内容来源于网络，有侵权请联系删除!实验课程名称：算法设计与分析实验项目名称分治与递归实验成绩实验者专业班级软彳zy1302班组别同组者实验日期2015年10月20日第一部分：实验分析与设计一.实验内容描述（问题域描述）1、利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析；2、要求用递归的方法实现。二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）本次的解法使用的是三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。它从左到右遍历数组一次，维护一个指针lt使得alo.lt-1中的元素都小于v,一个指针gt使得agt+1.hi中的元素都大于v,一个指针i使彳导alt.i-1中的元素都等于v,ai.gt中的元素都还未确定，如下图所示：3-waypartitioningoverviewpublicclassQuick3waypublicstaticvoidsort(Comparable口a,intlo,inthi)if(lo=hi)return;intlt=lo,i=lo+1,gt=hi;Comparablepivot=alo;while(i0)exch(a,i,gt-);elseif(cmpB,叫*R,%BR,R?%B,R排序后:BB,RR,RR,R,%*WProcessfinishedwithexitcode02、3、4、时间复杂度：介于N和NlogN之间；空间复杂度：lgN ；算法总结：三项切分的快速排序不是稳定的排序，是原地排序，它的运行效率由概率保证，同时取决 于输入元素的分布情况，对于包含大量重复元素的数组，它奖排序时间从线性对数级降低 到了线性级别，这非常的了不起。三、小结、建议及体会本次实验完成了三向切分的快速排序，其中不仅利用了分治法和递归，还对快速排序进行了优化，使得对于存在大量重复元素的数组，能够表现更高的效率。在实验过程中，我遇到了不少的困难，但通过自己在网上大量的浏览文献和资料，独立解决了所有问题，收获了不少。在下次的实验中，我也会继续努力的！实验课程名称：算法设计与分析实验项目名称动态规划算法实验成绩实验者专业班级软彳zy1302班组别同组者实验日期2015年12月1日第一部分：实验分析与设计二.实验内容描述（问题域描述）1、掌握动态规划算法求解问题的一般特征和步骤；2、使用动态规划法编程，求解0/1背包问题；3、问题描述：给定n种物品和一个背包，物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品，使得装入背包的物品的总价值最大？二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）0/1背包问题的特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即civ表示前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件物品获得的价值pi。算法设计如下：F口-0F购一0fori1toNdofork1toVF皿k-Fi-1kif（k=Ci）thenFik-max（Fik,Fi-1k-Ci+Wi）returnFNV三、主要仪器设备及耗材PC机1、调试方法：直接在方法入口断点调试，一步一步跟踪程序，弄明白程序的运行轨迹；2、实验数据：intm=10;intn=3;int口w=3,4,5;int口p=4,5,6;3、实验中遇到问题：（1） 刚开始对动态规划算法不熟悉，编码时出现很多的错误，花费了很多的时间;（2） 没有深度理解此处为什么要使用动态规划算法，导致对问题的理解不深刻。实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）1、实验结果:F:ProgramFilesJavajdkl,8,0_66binjava第0号背包：0-第T号背包;1第2号背包;1Processfinishedwithexitcode02、时间复杂度：nm;3、空间复杂度：nm（可优化至m）;4、算法总结：动态规划的基本思想：将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。三、小结、建议及体会本次实验解决了0/1背包问题，掌握动态规划算法求解问题的一般特征和步骤。在实验过程中，我遇到了很多不懂的问题，但通过老师和同学们的帮助，和自己的努力，最终解决了所将问题，收获颇丰。在今后的算法设计中，我会迎难而上！源代码:实验一：importjava.util.Arrays;publicclassQuick3waypublicstaticvoidsort(Comparable口a)sort(a,0,a.length-1);publicstaticvoidsort(Comparable口a,intlo,inthi)if(lo=hi)return;intlt=lo,i=lo+1,gt=hi;Comparablepivot=alo;while(true)intcmp=ai.compareTo(pivot);if(cmp0)exch(a,i,gt-);elseif(cmpgt)break;sort(a,lo,lt-1);sort(a,gt+1,hi);privatestaticvoidexch(Comparable口a,inti,intj)Comparabletemp=ai;ai=ajaj=temp;publicstaticvoidshow(Comparable口a)System.out.println(Arrays.toString(a);publicstaticvoidmain(String口args)String口a = R,B, W,W, R, W, B, R, R, W, B,R;System.out.println( show(a);sort(a); /System.out.println( show(a);排序前:t)；对数组a进行排序 排序后:t)；实验二：packagecom.shawn;publicclassPackageOlpublicint口口pack(intm,intn,intw口，intp)可iv表示前i件物品恰放入一个重量为m的背包可以获得的最大价值intc叩=newintn+1m+1;for(inti=0;in+1;i+)ci0=0;for(intj=0;jm+1;j+)c颂=0;for(inti=1;in+1;i+)for(intj=1;jm+1;j+)/当物品为i件重量为j时，如果第i件的重量(wi-1)小于重量j时,cij为下列两种情况之一：物品i不放入背包中，所以c皿为ci-1j的值/(2)物品i放入背包中，则背包剩余重量为j-wi-1,所以cij为ci-1j-wi-1的值加上当前物品i的价值if(wi-1=j)if(ci-1朋0;i-)/如果cim大于ci-1m,说明cim这个最优值中包含了wi-1(注意这里是i-1,因为c数组长度是n+1)if(c皿mci-1m)xi-1=1;m-=wi-1;for(intj=0;jn;j+)System.out.println(第+j+号背包：+xj);returnx;publicstaticvoidmain(Stringargs口)intm=10;背包容量intn=3;物品数量intw=3,4,5;物品重量intp=4,5,6;/物品价值Package01pack=newPackage01();intc叩=pack.pack(m,n,w,p);pack.printPack(c,w,m,n);