- 1、本文档共57页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第2章 递归与分治策略
学习要点:
理解递归的概念。
掌握设计有效算法的分治策略。
通过范例学习分治策略设计技巧。
(1)二分有哪些信誉好的足球投注网站技术;
(2)大整数乘法;
(3)Strassen矩阵乘法;
(4)棋盘覆盖;
(5)合并排序和快速排序;
(6)线性时间选择;
(7)最接近点对问题;
(8)循环赛日程表。
将要求解的较大规模的问题分割成k个更小规模的子问题。
算法总体思想
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
算法总体思想
对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
算法总体思想
对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
n
T(n)
=
算法总体思想
对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
n
T(n)
=
将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
n
T(n)
=
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
分治法的设计思想:
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
2.1 递归的概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
2.1 递归的概念
例1 阶乘函数
阶乘函数可递归地定义为:
边界条件
递归方程
边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。
2.1 递归的概念
例2 Fibonacci数列
无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可以递归地定义为:
边界条件
递归方程
第n个Fibonacci数可递归地计算如下:
int fibonacci(int n)
{
if (n = 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
2.1 递归的概念
例3 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数。
Ackerman函数A(n,m)定义如下:
2.1 递归的概念
例3 Ackerman函数
前2例中的函数都可以找到相应的非递归方式定义:
本例中的Ackerman函数却无法找到非递归的定义。
2.1 递归的概念
例3 Ackerman函数
A(n,m)的自变量m的每一个值都定义了一个单变量函数:
M=0时,A(n,0)=n+2
M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和A(1,1)=2故A(n,1)=2*n
M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n 。
M=3时,类似的可以推出
M=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。
2.1 递归的概念
例3 Ackerman函数
定义单变量的Ackerman函数A(n)为,A(n)=A(n,n)。
定义其拟逆函数α(n)为:α(n)=min{k|A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。
α(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有α(n)≤4。但在理论上α(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。
2.1 递归的概念
例4 排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,r
您可能关注的文档
- 塑壳琴操作培训知识课案.ppt
- 真空断路器解题.ppt
- 第四章悬索结构091技术分析.ppt
- 塑料成型工艺第三节课案.ppt
- 超高真空技术技术分析.ppt
- 塑料件结构设计及选取课案.ppt
- 塑料模调试课案.ppt
- 塑料设计基础培训-模具篇_V1_TJI课案.ppt
- 真空获得和真空镀膜_张中月解题.ppt
- 养老地产商业项目书(含市调)解题.ppt
- 2024至2030年中国羚羊角类饮片行业深度调查与前景预测分析报告.docx
- 重庆市面向中国农业大学定向选调2024届大学毕业生2024年国家公务员考试考试大纲历年真题14笔试历.docx
- 重庆市面向西北工业大学定向选调2024届大学毕业生00笔试历年典型考题及解题思路附答案详解.docx
- 中国不动杆菌感染治疗药行业市场现状分析及竞争格局与投资发展研究报告2024-2029版.docx
- 2024至2030年全球与中国ETL软件市场现状及未来发展趋势.docx
- 初中八年级(初二)生物下册期末考试1含答案解析.docx
- 干簧式继电器项目申请报告.docx
- 2024至2030年中国左氧氟沙星片行业深度调查与前景预测分析报告.docx
- 菜籽项目申请报告.docx
- 2024至2030年中国八角钢行业深度调查与前景预测分析报告.docx
文档评论(0)