二分法的一些应用
时间:2019-08-20 13:02 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：二分法在数学、计算机和生活等领域有着很多重要的应用.本文主要介绍二分法的分治思想以及所采用的递归技术原理,给出了算法设计程序和时间复杂度，例举了二分法排序和查找、求解近似解问题以及解决故障查找的实例，因此二分法可以提高搜索效率，求解方程根的近似解，将生活问题化繁为简.但由于客观事物内部的复杂性,坚持二分法就会忽略原有的全面基础.本文最后对二分法作了一些改进,使其查找效率更高,结果更加接近真实结果.38906 毕业论文关键词：分治法；递归技术；二分法；应用 Some Applications of Dichotomy Abstract: The dichotomy has many important applications in mathematics, computer and other areas of life. This paper mainly introduces the principle of pide and conquer and recursion technique using dichotomy, then gives the algorithm design program and the time complexity of the algorithm. Through examples, the approximate solution of the dichotomy find fault, find the problem, we can know the dichotomy search can be improved efficiency, fast approximate solution and to simplify the problems of life. But because of the complexity of objective things inside, and adhere to the dichotomy will ignore the comprehensive existing. This paper makes some improvement on the dichotomy, the search efficiency is higher, the more close to the real results. Key words：Divide and conquer ;Recursive technique; The dichotomy; Application 目 录 摘 要 1 引言 2 1.与二分法相关的基本原理 3 1.1 递归过程的设计与实现 3 1.1.1递归原理 3 1.1.2递归算法分析 4 1.2分治法思想以及应用原理 4 1.2.1分治法的思想 4 1.2.2分治法的实现和应用 4 1.2.3 分治法的一般递归算法设计 5 2.二分法的一些应用实例 6 2.1二分法在计算机方面的应用 6 2.2二分法在数学领域的应用 9 2.3二分法在生活领域的一些应用 11 3. 二分法的算法改进 13 3.1对二分法时间复杂度的改进 13 3.2对二分查找算法的改进 14 4.结束语 15 参考文献 17 致谢 18 二分法的一些应用引言 二分法是数学、计算机乃至生活各个方面的一个至关重要的求近似解[3]和查找[9]以及解决实际问题的方法，它对数学解题的精确度和计算机查找速率的提高具有十分重要的理论意义.即是现代信息技术与函数、方程等知识的有机结合，也是分治法思想的集中体现，现在二分法的一些重要应用给人们的生活和工作以及社会科学的发展带来了重大贡献，它将原问题分解为若干个相互独立，规模小，与原问题相似的子问题，其次对子问题进行求解.这样就很容易得出若干个子问题的解，如果不能，那么将继续分解子问题，直到能够快速求解为止，最后合并问题，将已求的各子问题的解，合并为原问题的解.二分法也称为折半查找[5]，即采用分治法思想，将含有n个元素的数组一分为二，两组个数大致一样，取a[n/2]与被查找的x作比较，如果两者相等则找到x，算法终止.如果x<a[n/2]，那么就把右半部分舍弃，在左半部分继续查找即可（假设这组元素是升序排列的），若x>a[n/2]，则我们只要在数组a的右半部继续搜索x. 二分法一直以来是人们比较关注的算法，人们不断对其进行探究分析，其中有很多文献里都对此进行了详细的研究和理论分析.在文献[5][6]中详细介绍了分治法、递归算法以及二分法的基本原理和思想，关于二分算法和时间复杂度也做了详细描述和分析.对于二分法的一些应用，在文献[1][3][4]中详细介绍了故障排除，快速查找，近似解问题以及在物理实验中的具体事例.二分法同时也具有一些不可避免的缺点，比如数组快速查只能对有序数列进行查找.人们也在进行反思和改进，在文献[2]中，主要针对二分法的一些不足加以改善并进行算法的分析研究，提出了更加完善的二分算法的改进. (责任编辑：qin) |