毕业论文

打赏
当前位置: 毕业论文 > 数学论文 >

二分法的一些应用(2)

时间:2019-08-20 13:02来源:毕业论文
本文主要介绍了二分法的应用概念和原理,即用分治法的思想[11],采用递归技术[5-6],并给出相应的算法设计程序,结合具体问题,来将复杂问题一分为二


本文主要介绍了二分法的应用概念和原理,即用分治法的思想[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 ,所有的子问题都可解,则原问题的解就可以通过这些子问题的解求出来,那么这种分治法就是可行的.由分治法产生的子问题一般是原问题的较小模式,这就为使用递归技术提供了方便.在这种情况下,若反复使用分治手段,可以使原问题的规模不断缩小且子问题与原问题类型保持一致,最终使子问题缩小到很容易直接求出其解.这自然导致递归过程的产生.分治与递归形影不离,经常同时应用在算法设计之中,并由此产生许多高效算法. 二分法的一些应用(2):http://www.youerw.com/shuxue/lunwen_37992.html
------分隔线----------------------------
推荐内容