算法设计与分析Chapter2Veron
73页1、1,递归与分治策略,张可佳,2,理解递归的概念 掌握设计有效算法的分治策略 通过下面的范例学习分治策略设计技巧 二分搜索技术; 大整数乘法; Strassen矩阵乘法; 合并排序和快速排序; 线性时间选择; 最接近点对问题;,学习要点,3,递归的概念,递归,递归的概念 直接或间接调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数,4,递归函数(阶乘函数),阶乘函数,5,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。,int fractorial (int n) If(n=0) return 1; return n*fractorial(n-1); ,递归函数(Fibonacci函数),Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55, 递归定义为,6,边界条件,递归方程,int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,整数划分问题,定义 将正整数n表示成一系列
2、正整数之和 n=n1+n2+nk, 其中n1n2nk1,k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。,7,例如正整数6有如下不同的划分: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。,整数划分问题,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,8,(1) q(n,1)=1,n1; 最大加数n1不大于1,任何正整数n只有一种划分形式,即,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此,q(1,m)=1,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。,整数划分问题,如果设p(n)为正整数n的划分数,则难以找到递归
3、关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,9,正整数n的划分数p(n)=q(n,n),整数划分问题,例子,10,q(6,3) = q(6,2) + q(3,3),= q(6,1) + q(4,2),+ 1 + q(3,2),= q(6,1) +,+ 1 +,1 + q(2,1),= q(6,1) + q(4,1) +,= 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7,q(4,1) + q(2,2),q(3,1) + q(1,2),+ 1 + q(3,1) + q(1,2),3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1,Hanoi塔问题,设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则: 规则1:每次只能移动1个圆盘; 规则2:任何时刻都不允许将较大的圆盘压在较小的
4、圆盘之上; 规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。,11,Hanoi塔问题,要将n个圆盘按规则从A移动到C,只需 将n1个较小圆盘按规则从A移动到B 将最大的圆盘从A移动到C 将n-1个较小圆盘从B移动到C n个圆盘的移动问题可以转换为 两次n-1个圆盘移动的问题一个单一圆盘移动,12,Hanoi塔问题,void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(A, B); hanoi(n-1, C, B, A); hanoi(n, A, B, C)表示将n个圆盘按规则从A移动到B,移动的过程中用C最辅助塔座 move(A, B)表示将A上剩余的单一圆盘从A移动到B,13,函数调用的处理过程,函数A调用函数B时 保存A的所有运行状态 将实参指针、返回地址等信息传递给B 为B中的变量分配存储区 将控制转移到B的入口 从函数B返回到函数A时 保存B的计算结果 释放分配给B的存储区 依照返回地址将控制转移到A,14,递归的处理过程,函数A调用自身 分层:A0, A1,
《算法设计与分析Chapter2Veron》由会员E****分享,可在线阅读,更多相关《算法设计与分析Chapter2Veron》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页