算法实验报告副本.doc

实 验 报 告课程名称：算法设计与分析班级： 实验成绩：实验名称：分治策略学号：批阅教师签字：实验编号：实验一姓名：实验日期：2014 年 10 月 1 日指导教师：组号：实验时间： 时 分 时 分一、实验目的该实验主要涉及了对分治法的应用，应用的前提是了解。我所理解的分治法策略是将规模较大的问题分解为多个规模小的子问题，要求这些子问题之间相互独立且要与原问题相同，这样才能保证分解是正确有意义的。再者，分解规模有一个阀值，在这种情况下最合适，找这个值因问题的不同而有所改变，没有一个固定值。除外，使用这种策略的主要实施手段是递归，本实验也是采用了这种方式。之所以要亲身试验，目的则为了加深对分治法的理解。只有看到使用的具体细节，才能弥补理论知识的空缺。结合所学的编程语言，使得看到该策略更快计算出结果的优势。二、实验内容本实验简单来说就两个字，查找.设置两个大小相同且排好序的数组,通过比较,最终找到在这两个数组合并情况下的中位数.传统的做法是将两个数组逐一比较大小,进而查找.但是这种做法没有良好的利用两个数组已经排好序的前提,使得问题的规模成倍的增加,也造就了时间和空间的浪费.这就体现了分治法的优势.通过逐次缩小问题的规模(减小一半),最终找到结果.这样一来,使得问题的时间复杂度降至O (log n).如果n很大,就会进一步体现出该算法的改良优势.三、实验环境操作系统:windws 7调试软件名称:VC版本号:6.0上机地点:综合楼209机器台号:88四、问题分析（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。时间复杂度:空间复杂度:（3） 其它（你认为需要在此说明的）五、问题解决（1） 根据对问题的分析，写出解决办法。 问题一：该问题是针对两个已经排好序的数组，由于不确定数组的规模，所以需要对数组大小的任何可能值做出相应的解决方案，以提高该算法的可靠性。 问题一解决：数组大小为1,2的时候比较特殊，为1的时候只需对这两个数进行比较，取较小的数为中位数即可；为2的时候就是该算法缩小规模的最后情况，这个时候，根据前一次缩小规模的两中位数大小，大的取后一元素，小的取前一元素，二者相比，小的数就是最终的中位数。问题二：找中位数的时候，要使用到缩小问题规模的一个表达式，而因为数组大小奇偶的不同，表达式也应有所改变。问题二解决：数组大小为奇数，n=(n+1)/2； 数组大小为偶数,(int)n=(n+1)/2. 改善：其实，如果是这样，可以给；两个表达式都加上（int）这个取整运算。这样，也就不存在奇数偶数的差异。问题三：计算方式的不同，根据数学上对于中位数的定义，当数组为偶数是，中位数为最中间两个元素数值之和的一般。但是，在该问题的情况下，如果按同样的方式要求，也就是问题失去了查找的意义，因此有必要做出相应的改变。问题三解决：按照人们的习惯，大家常在偶数个数的序列中，取中间的两个两个元素中较小的数作为中位数。（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。 该算法的主要思想就是每次缩小问题规模的一半。 传统做法需要对数进行一一比较，而数组是排好序的，这样就使得多次的比较是没有意义的。而该算法只需找到每个数组的最中间元素进行比较，得知结果，删除中位数较大数组的后半部分数和中位数较小的前半部分数，这两部分数的个数相同，大小则是合并数组的左右极端，删去后就减少了不必要的比较。逐次按照这种做法，最终会得到大小为2的两个数组。这样结果就很容易得出。算法时间复杂度：算法空间复杂度：（3） 针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。处理一：针对数组规模奇偶做出分类讨论，因为数组大小为奇数时有唯一确定的中位数，而偶数情况下，有两个最中间元素，需要做出取舍，根据习惯，保留较小数为中位数。处理二：在数学定义下，偶数个元素时，中位数为中间两元素之和的一半，而这样就失去了查找的意义，取前一个为所需结果。处理三：算法循环的最终规模为2，这个时候需要对最终结果做出响应。处理四：为了保证算法的稳定性，需要对数组大小为1的时候做出处理，即比较两数的大小，小的为中位数。（4） 你在调试过程中发现了怎样的问题？又做了怎样的改进？问题：我对奇数偶数做了分类讨论，主要是考虑到中位数的个数情况有差异，这样就增加了程序的冗余。改进：无论奇偶，都使用(int)n=(n+1)/2这个式子，奇数时，取整是不必要的。但这样很大程度缩小了程序的规模。六、实验结果总结回答以下问题：（1） 对不同的输入，该算法都存在哪几类可能出现的情况，你的测试数据完全覆盖了你所想到的这些情况，测试结果如何？ 输入可能情况：1。输入非数字的符号 解决：1.提示重输 2.输入数个数不等于n 2.提示重输 3.不能检索数的类型 3.提示重输 （2） 算法实现的复杂度在问题规模很大时可以接受吗？ 该算法空间复杂度要求（3） 如果不用分治方法还能想到其他的解决方式吗？和分治相比会有更好的效率吗？ 还可以将两个数组一一对比，进而合并，在合并之后找中位数。 相比于分治法，该方法要进行规模为n*n的比较次数，当n较大时，就比分治法（复杂度为n*log N）的效率低的多。（4） 所选用的数据结构合适吗？ 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中据元素之间的关系。而本实验，我所采用的数据结构很简单，就是单纯的创建了两个大小为n的地址空间，来用于存放待输入的n个数，所以，应该是一种链式存储。该算法不存在什么地址的复杂指向，因此该结构是合适的。（5） 叙述通过实验你对分治方法的理解及你认为的分治法的优缺点。 分治法的理解：该算法就是将一个复杂的问题分解为两个或多个相同或相似的问题，进而再进行分解，直到达到一个阀值使得能够简单解决，最后把问题合并就是复杂问题的解。根据这种思想，经常采用递归策略。分治法优点： 1.算法思路简单，易于实现，效率也不差。 分治法缺点： 1分治法对于每次出现的子问题都要求解，导致再次碰到同样的问题反复求解，增长了时间复杂度，效率较低。 2.该算法要求较高。要求子问题与原问题有相同的结构性质。而多数问题不具备，分解后都会有所变化。六、附录（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。 想法：我觉得分治法用于解决查找问题的实用性很高。但同时该算法的要求是很高的，要求两个数组排好序且大小相等，这在现实中很难满足。因此我觉得有必要使得问题正常化。多种情况下，是规模不等，个数不确定的乱序数组。因此，我们也有必要了解解决问题的常规办法。 应该根据问题的实际情况，向特殊化靠拢。最终借助分治法的优势进行高效率的解决。（2） 实验参考的资料和网址参考书： 计算机算法设计与分析（电子工业出版社） C+ Primer plus（人民邮电出版社）网址：/icl2002/algorithm/algorithm/technique/divide_and_conquer/chapter1.html （分治法的基本思想）