资源描述：
《第2章_递归与分治策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章递归与分治策略2021/7/27算法设计与分析2第2章递归与分治策略学习要点理解递归的概念掌握设计有效算法的分治策略：分治法的基本思想通过范例学习分治策略的算法分析及设计技巧二分搜索技术、大整数的乘法、Strassen矩阵乘法合并排序和快速排序2021/7/27算法设计与分析32.1递归的概念问题1：什么是递归?直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。举例：输出n个自然数。Print_1(intn){inti;for(i=1;i<=n;i++)printf(“%d”,i);printf(“”);return;}非递归算法Print_2(intn)
2、{if(n==0)return;else{Print_2(n-1);printf(“%d”,n);}return;}递归算法2021/7/27算法设计与分析4举例2-1：阶乘函数可递归定义为：其中：n=0时，n!=1为边界条件（基础步）n>0时，n!=n(n-1)!为递归方程（归纳步）说明：边界条件与递归方程是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。递归函数的内部执行过程递归函数内部执行过程如下：（1）运行开始时，为递归调用建立一个工作栈，其结构包括实参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的实参和局部变量的当前值以及调用后的返回地址
3、压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的实参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行2021/7/27算法设计与分析6举例2-2：Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,…，被称为Fibonacci数列。它可以递归定义为：边界条件递归方程intFibonacci(intn){if(n<=1)return1;returnFibonacci(n-1)+Fibonacci(n-2);}2021/7/27算法设计与分析7分析以上两例中的函数也可以用如下非递归方式定义：但是并非所有递归函数都能用非递归方式定义，例如Ackerma
4、n函数就不能用非递归方式定义。2021/7/27算法设计与分析8举例2-3：Ackerman函数(了解)当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n,m)定义如下，n,m是两个独立的整变量，其中n,m均≥0：2021/7/27算法设计与分析9分析A(n,m)的自变量m的每一个值都定义了一个单变量函数：m=0时，A(n,0)=n+2。m=1时，A(n,1)=2n。m=2时，A(n,2)=2n。m=3时，类似的可以推出m=4时，A(n,4)的增长速度非常快，以至于没有合适的数学式子来表示这一函数。2021/7/27算法设计与分析10举例2-6：Ha
5、noi塔问题问题定义：设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：（1）每次只能移动1个圆盘；（2）任何时刻都不允许将较大的圆盘压在较小的圆盘之上；（3）在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。2021/7/27算法设计与分析11塔座a塔座b塔座c321特例：三阶Hanoi塔问题分析：起始塔座a上有三个圆盘，所以该问题被称为三阶Hanoi塔问题。需要完成：Hanoi(3,a,c,b)；其
6、中，参数1表示一共需要移动几个圆盘；参数2表示起始塔座；参数3表示中间塔座；参数4表示目的塔座。2021/7/27算法设计与分析12分析简单解法：将A、B、C、A构成一个顺时针循环。在移动盘子的过程中，若是奇数次移动，则将最小的盘子移到顺时针方向的下一塔座上；若是偶数次移动，则保持最小盘子不动，而在其他两个塔座之间，将较小的盘子移到另一塔座上。塔座a塔座b塔座c3212021/7/27算法设计与分析13分析递归思路：当n=1时，只要将编号1的盘子从A移到B即可；当n>1时，要以C为辅助，此时设法将n-1个较小的盘子从A移到C，将剩下的最大盘子从A移到B，最后，再设法将n-1个较小的盘子从C移到
7、B。这样，n个盘子的移动就可以分解为两次n-1个盘子的移动。2021/7/27算法设计与分析14三阶Hanoi塔问题塔座a塔座b塔座c321分析：完成Hanoi(3,a,c,b)的工作可以分解成如下三个步骤：Hanoi(2,a,b,c)、MOVE(a,3,b)和Hanoi(2,c,a,b)。需要先完成：Hanoi(2,a,b,c)；该工作又可分解成：①Hanoi(1,a,c,b)；②MOVE(a,
