二分法的一些应用(2)
时间:2019-08-20 13:02 来源:毕业论文 作者:毕业论文 点击:次
本文主要介绍了二分法的应用概念和原理，即用分治法的思想[11]，采用递归技术[5-6]，并给出相应的算法设计程序，结合具体问题，来将复杂问题一分为二，从而简单方便的解决问题.关于二分法的一些应用非常广泛，如排除路障，求解近似解，快速数据查找等,经过详细的实际分析计算，运用一些数学MATLAB和计算机软件C语言辅助运算，结合分治和递归来说明解释和介绍二分法的一些应用.在此基础上又对二分法的低效的情况进行了分析，并提出一些改进方案，使得二分法更好的解决问题，造福人类生活. 1.与二分法相关的基本原理 1.1递归过程的设计和实现 1.1.1递归原理 递归算法[5]的主要表现形式为过程或函数在定义自身的同时对自身进行调用.采用递归策略的时候，一是寻找对问题进行分解的方法，二是所分解问题的出口，即设计递归出口. 在算法的递归调用过程中，进行递归进层（i→i+1层）系统需要做一下三件事；(1)将所有的实在参数、 返回地址等信息传递给被调用函数保存；(2)给下一层参数赋值(作为被调用函数的局部变量分配存储区)；(3)将程序转移到被调函数的入口.而从被调用函数返回调用函数之前，递归退层（i←i+1层）系统也应完成三件工作：(1)保存被调函数的计算结果；(2)恢复上层参数（释放被调函数的数据区)；(3)依照被调函数保存的返回地址， 将控制转移回调用函数. 递归算法流程图如下图1所示： 递归算法流程图 1.1.2递归算法分析 求解递归方程一般可采用3种方法，即替代方法，递归方法和主方法.这里主要介绍替代方法中的二路归并排序的递归算法分析，在二分法的应用中，此技术发挥了重要作用.将待排序的元素序列一分为二，得到长度基本相等的两个子序列，分别排序.如果子序列较长，还可继续细分，直到子序列的长度不超过1为止.当分解所得的子序列已排列有序时，将两个有序子序列合并成一个有序子序列，得到原问题的解.合并方法是比较两序列中的最小值，输出其中较小者，然后重复此过程，直到其中一个队列为空时，如果另一个队列还有元素没有输出，则将剩余元素依次输出. 1.2分治法思想以及应用原理 1.2.1分治法的思想 分治法的设计思想是，若一个大问题难以直接解决，则需要将它分成一些规模比较小的相同问题，然后各个击破，分而治之.如果原问题可分割成i个子问题，1<i<=n ，所有的子问题都可解，则原问题的解就可以通过这些子问题的解求出来，那么这种分治法就是可行的.由分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便.在这种情况下，若反复使用分治手段，可以使原问题的规模不断缩小且子问题与原问题类型保持一致，最终使子问题缩小到很容易直接求出其解.这自然导致递归过程的产生.分治与递归形影不离，经常同时应用在算法设计之中，并由此产生许多高效算法. (责任编辑：qin) |