第2章 递归与分治_作业答案讲解
- 格式:ppt
- 大小:206.50 KB
- 文档页数:25
递归和分治法摘要:1.递归和分治法的定义2.递归和分治法的区别3.递归和分治法的应用实例4.递归和分治法的优缺点正文:递归和分治法是计算机科学中常用的两种算法设计技巧。
它们在解决问题时都采用了将问题分解成更小子问题的思路,但在具体实现上却有所不同。
下面,我们来详细了解一下递归和分治法。
1.递归和分治法的定义递归法是指在算法中调用自身来解决问题的方法。
递归函数在执行过程中,会将原问题分解成规模更小的相似子问题,然后通过调用自身的方式,解决这些子问题,最后将子问题的解合并,得到原问题的解。
分治法是指将一个大问题分解成若干个规模较小的相似子问题,然后分别解决这些子问题,最后将子问题的解合并,得到原问题的解。
分治法在解决问题时,通常需要设计一个主函数(master function)和一个子函数(subfunction)。
主函数负责将问题分解,子函数负责解决子问题。
2.递归和分治法的区别递归法和分治法在解决问题时都采用了将问题分解成更小子问题的思路,但它们在实现上存在以下区别:(1)函数调用方式不同:递归法是通过调用自身来解决问题,而分治法是通过调用不同的子函数来解决问题。
(2)递归法必须有递归出口,即必须有一个基线条件,而分治法不一定需要。
3.递归和分治法的应用实例递归法应用广泛,例如斐波那契数列、汉诺塔问题、八皇后问题等。
分治法也有很多实际应用,例如快速排序、归并排序、大整数乘法等。
4.递归和分治法的优缺点递归法的优点是代码简单易懂,但缺点是容易产生大量的重复计算,导致时间复杂度较高。
分治法的优点是时间复杂度较低,但缺点是代码实现相对复杂,需要设计主函数和子函数。
总之,递归和分治法都是解决问题的有效方法,具体应用需要根据问题的特点来选择。
算法分析(第二章):递归与分治法一、递归的概念知识再现:等比数列求和公式:1、定义:直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系:由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。
在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中,并由此产生许多高效算法。
3、递推方程:(1)定义:设序列01,....na a a简记为{na},把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解:给定关于序列{n a}的递推方程和若干初值,计算n a。
4、应用:阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点:优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进:1、迭代法:(1)不断用递推方程的右部替代左部(2)每一次替换,随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例:-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−(1)=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−(1)2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代:(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解(关于k 的函数)转换成关于n 的函数4、举例:---------------二分归并排序---------------()2(/2)1W n W n n W =+−(1)=0(1)换元:假设2kn =,递推方程如下()2(/2)1W n W n n W =+−(1)=0 → 1(2)2(2)21k k k W W W−=+−(0)=0(2)迭代求解:12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+(3)解的正确性—归纳验证: 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−(1)=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法:数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程,则()---------------快速排序--------------------->>>平均工作量:假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简,然后迭代(1)差消化简:利用两个方程相减,将右边的项尽可能消去,以达到降阶的目的。
递归和分治法摘要:一、递归和分治法简介1.递归2.分治法二、递归和分治法的应用1.递归在编程中的应用2.分治法在编程中的应用三、递归和分治法的优缺点1.递归的优缺点2.分治法的优缺点四、递归和分治法在实际问题中的应用案例1.递归在实际问题中的应用案例2.分治法在实际问题中的应用案例五、递归和分治法在我国教育领域的应用1.递归在我国教育领域的应用2.分治法在我国教育领域的应用六、递归和分治法在未来的发展前景1.递归在未来的发展前景2.分治法在未来的发展前景正文:递归和分治法是计算机科学中两种解决问题的方法,它们都具有广泛的应用。
递归是一种函数调用自身的技术,通常用于解决具有相似子问题的复杂问题。
分治法是一种将大问题分解成小问题,然后逐个解决小问题的方法,最后将小问题的解合并得到大问题的解。
递归在编程中有广泛的应用,例如计算阶乘、快速排序等。
递归的优点是可以简洁地表示复杂问题,但缺点是可能会导致栈溢出,因此需要合理设计递归函数。
分治法在编程中也有广泛的应用,例如归并排序、大整数乘法等。
分治法的优点是可以有效地处理大规模问题,但缺点是可能会导致过多的子问题,增加计算复杂度。
在实际问题中,递归和分治法都有许多应用案例。
例如,在图像处理中,快速傅里叶变换(FFT)算法利用了递归和分治法来高效地计算离散傅里叶变换。
在我国教育领域,递归和分治法被广泛应用于计算机科学教育,帮助学生理解和掌握基本的算法思想。
未来,递归和分治法仍将在计算机科学领域发挥重要作用。
随着科技的进步,递归和分治法将应用于更复杂的问题,如人工智能、大数据处理等领域。
算法分析(第二章):递归与分治法一、递归的概念知识再现:等比数列求和公式:1、定义:直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系:由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。
在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中,并由此产生许多高效算法。
3、递推方程:(1)定义:设序列01,....na a a简记为{na},把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解:给定关于序列{n a}的递推方程和若干初值,计算n a。
4、应用:阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点:优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进:1、迭代法:(1)不断用递推方程的右部替代左部(2)每一次替换,随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例:-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−(1)=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−(1)2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代:(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解(关于k 的函数)转换成关于n 的函数4、举例:---------------二分归并排序---------------()2(/2)1W n W n n W =+−(1)=0(1)换元:假设2kn =,递推方程如下()2(/2)1W n W n n W =+−(1)=0 → 1(2)2(2)21k k k W W W−=+−(0)=0(2)迭代求解:12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+(3)解的正确性—归纳验证: 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−(1)=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法:数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程,则()---------------快速排序--------------------->>>平均工作量:假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简,然后迭代(1)差消化简:利用两个方程相减,将右边的项尽可能消去,以达到降阶的目的。
计算机算法设计与分析第4版(王晓东著)课后答
案下载
计算机算法设计与分析第4版内容简介
第1章算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。
全书以算法设计策略为知识单元,系统介绍计算机算法的设计方法与分析技巧。
主要内容包括:算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。
书中既涉及经典与实用算法及实例分析,又包括算法热点领域追踪。
为突出教材的`可读性和可用性,章首增加了学习要点提示,章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。
分治算法是一种算法设计思想,其主要思想是将一个复杂的问题分解为两个或更多相同或相似的子问题,直到子问题简单到可以直接解决。
然后,再将子问题的解合并,形成原问题的解。
这种算法设计思想常用于数据结构和算法设计中,如排序算法(如快速排序和归并排序)、二叉树操作等。
递归与分治的关系
递归是一种编程或函数自我调用的方法,递归函数会不断地调用自身,直到满足某个终止条件。
分治算法常常使用递归作为其实现手段,通过递归调用来实现问题的分解和解的合并。
这种情况下,递归就成为了实现分治的一种手段。
虽然分治算法常常依赖于递归来实现,但并不是所有的递归算法都是分治算法。
分治算法的关键在于解决问题的方式:它把一个问题分解为若干个独立的子问题,然后对子问题求解,最后合并子问题的解来得到原问题的解。
而递归只是一种函数自我调用的编程技巧,其并没有明确规定问题需要如何被分解和求解。
示例:归并排序
归并排序就是一个典型的分治算法。
归并排序首先将一个待排序的序列分解为两个或更多的子序列,然后对每个子序列进行排序,最后将排序后的子序列合并为一个有序序列。