算法实 验 报 告 - 副本

《算法实 验 报 告 - 副本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称：算法设计与分析班级：实验成绩：实验名称：分治策略学号：批阅教师签字：实验编号：实验一姓名：实验日期：2014年10月1日指导教师：组号：实验时间：时分－时分一、实验目的该实验主要涉及了对分治法的应用，应用的前提是了解。我所理解的分治法策略是将规模较大的问题分解为多个规模小的子问题，要求这些子问题之间相互独立且要与原问题相同，这样才能保证分解是正确有意义的。再者，分解规模有一个阀值，在这种情况下最合适，找这个值因问题的不同而有所改变，没有一个固定值。除外，使用这种策略的主要实施手段是递归，本实验也是采用了这种方式。之所以要亲身试验，目的则为了加深对分治法的理解。只有看到使用的

2、具体细节，才能弥补理论知识的空缺。结合所学的编程语言，使得看到该策略更快计算出结果的优势。二、实验内容本实验简单来说就两个字，查找.设置两个大小相同且排好序的数组,通过比较,最终找到在这两个数组合并情况下的中位数.传统的做法是将两个数组逐一比较大小,进而查找.但是这种做法没有良好的利用两个数组已经排好序的前提,使得问题的规模成倍的增加,也造就了时间和空间的浪费.这就体现了分治法的优势.通过逐次缩小问题的规模(减小一半),最终找到结果.这样一来,使得问题的时间复杂度降至O(logn).如果n很大,就会进一步体现出该算法的改良优势.三、实验环境操作系统:windws7调试软件名称:VC版本号:6

3、.0上机地点:综合楼209机器台号:88四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。（1）分析利用你的想法解决该问题可能会有怎样的时空复杂度。时间复杂度:空间复杂度:（2）其它（你认为需要在此说明的）五、问题解决（1）根据对问题的分析，写出解决办法。问题一：该问题是针对两个已经排好序的数组，由于不确定数组的规模，所以需要对数组大小的任何可能值做出相应的解决方案，以提高该算法的可靠性。问题一解决：数组大小为1,2的时候比较特殊，为1的时候只需对这两个数进行比较，取较小的数为中位数即可；为2的时候就是该算法缩小规模的最后情况，这个时候，根据前一次缩小规模的两中位数大

4、小，大的取后一元素，小的取前一元素，二者相比，小的数就是最终的中位数。问题二：找中位数的时候，要使用到缩小问题规模的一个表达式，而因为数组大小奇偶的不同，表达式也应有所改变。问题二解决：数组大小为奇数，n=(n+1)/2；数组大小为偶数,(int)n=(n+1)/2.改善：其实，如果是这样，可以给；两个表达式都加上（int）这个取整运算。这样，也就不存在奇数偶数的差异。问题三：计算方式的不同，根据数学上对于中位数的定义，当数组为偶数是，中位数为最中间两个元素数值之和的一般。但是，在该问题的情况下，如果按同样的方式要求，也就是问题失去了查找的意义，因此有必要做出相应的改变。问题三解决：按照人们

5、的习惯，大家常在偶数个数的序列中，取中间的两个两个元素中较小的数作为中位数。（1）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。该算法的主要思想就是每次缩小问题规模的一半。传统做法需要对数进行一一比较，而数组是排好序的，这样就使得多次的比较是没有意义的。而该算法只需找到每个数组的最中间元素进行比较，得知结果，删除中位数较大数组的后半部分数和中位数较小的前半部分数，这两部分数的个数相同，大小则是合并数组的左右极端，删去后就减少了不必要的比较。逐次按照这种做法，最终会得到大小为2的两个数组。这样结果就很容易得出。

6、算法时间复杂度：算法空间复杂度：（2）针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。处理一：针对数组规模奇偶做出分类讨论，因为数组大小为奇数时有唯一确定的中位数，而偶数情况下，有两个最中间元素，需要做出取舍，根据习惯，保留较小数为中位数。处理二：在数学定义下，偶数个元素时，中位数为中间两元素之和的一半，而这样就失去了查找的意义，取前一个为所需结果。处理三：算法循环的最终规模为2，这个时候需要对最终结果做出响应。处理四：为了保证算法的稳定性，需要对数组大小为1的时候做出处理，即比较两数的大小，小的为中位数。（3）你在调试过程中发现了怎样的问题？又做了怎样的改进？问题：

7、我对奇数偶数做了分类讨论，主要是考虑到中位数的个数情况有差异，这样就增加了程序的冗余。改进：无论奇偶，都使用(int)n=(n+1)/2这个式子，奇数时，取整是不必要的。但这样很大程度缩小了程序的规模。六、实验结果总结回答以下问题：（1）对不同的输入，该算法都存在哪几类可能出现的情况，你的测试数据完全覆盖了你所想到的这些情况，测试结果如何？输入可能情况：1。输入非数字的符号解决：1.提示重输2.输入数个数不等