资源描述：
《递归与分治法sch1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析算法设计与分析DesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithms主讲人主讲人徐徐云云Fall2010Fall2010,USTC,USTC第第11章章((补充补充))递归与分治法递归与分治法1.11.1递归设计技术递归设计技术1.21.2二分查找二分查找1.31.3大整数乘法大整数乘法1.41.4StrassenStrassen矩阵乘法矩阵乘法1.51.5导线和开关导线和开关1.1递归设计技术ò递归的概念和种类ò递归方法的三种应
2、用ò一个简单示例：n!ò递归算法的非递归实现ò递归算法设计举例2010-10-12算法设计与分析3递归的概念和种类ò递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。ò递归有两种直接递归：自己调用自己间接递归：A调用B，B调用A2010-10-12算法设计与分析4递归方法的三种应用ò以下三个方面常用到递归方法①递归定义如，自然数定义：-1是自然数；-一个自然数加1(后继)仍是自然数；注：“1是自然数”是递归的临界条件②递归的数据结构如，单链表节点是递归扩展的③问题的递归解
3、法如，汉诺塔问题的直观解法2010-10-12算法设计与分析5一个简单示例：n!⎧1n=0òn阶乘的定义：n!=⎨⎩n*(n−1)！n>0ò以求3！为例的计算过程Fact(3)Fact(3)逐层调用3*Fact(2)=6逐层返回Fact(2)Fact(2)2*Fact(1)=2Fact(1)112010-10-12算法设计与分析6递归算法的非递归实现ò示例：n!的递归和非递归算法Fact1(n)//递归程序Fact2(intn)//非递归程序{ifn=0return1;{p=1;elsereturnn*fact1(n-1);fori←1tondop←p*i;}r
4、eturnp;}òRemark：(1)递归算法易设计和分析，但执行效率较低，常要转化为非递归程序；(2)递归算法的非递归实现通常有三种实现方法：①利用栈消除递归②利用迭代法消除递归③末尾递归消除法2010-10-12算法设计与分析7递归算法的非递归实现ò思考题：Fibonacci数递归和非递归算法Fibonacci(n)⎧0n=0{//非递归算法⎪ifn=0orn=1thenFn=⎨1n=1⎪returnn;F+Fn≥2⎩n−1n−2s1=0;s2=1;fori←2tondoFibonacci(n){{//递归算法sum←s1+s2;ifn=0orn=1then
5、s1←s2;returnn;s2←sum;else}returnFibonacci(n-1)+Fibonacci(n-2);returnsum;}}2010-10-12算法设计与分析8递归算法设计举例:汉诺塔（1）ò汉诺塔（HanoiTower）问题：这是一个流传很久的游戏。1.有三根杆子A,B,C。A杆上有n只碟子2.每次移动一块碟子,小的只能叠在大的上面3.把所有碟子从A杆经C杆全部移到B杆上.Peg#1Peg#2Peg#32010-10-12算法设计与分析9递归算法设计举例:汉诺塔（2）ò递归求解：1.若只有一只碟子，直接将它从A杆移到B杆；2.把n-1只
6、碟子从A杆经B杆移动到C杆，将A杆上第n只碟子移到B杆；然后再将n-1只碟子从C杆经A杆移到B杆。2010-10-12算法设计与分析10递归算法设计举例:汉诺塔（3）ò递归算法Hanoi(n,A,B,C){//将从小到大的n个圆盘从A移到Bifn>0then{Hanoi(n-1,A,C,B);//将从小到大的n-1个圆盘从A移到CMove(n,A,B);//将第n大的圆盘从A移到BHanoi(n-1,C,B,A);//将从小到大的n-1个圆盘从C移到B}}ò算法分析¾正确性：用归纳法证明；¾时间复杂性：T(n)=1+2T(n-1)⇒O(2n)¾算法的最优性：为最
7、优的2010-10-12算法设计与分析11递归算法设计举例:再论Fib数（1）ò基于Fibonacci数递归定义的算法：T(n)=Ω((3/2)n)ò改进的算法：利用公式⎧0n=0⎪⎪1n=1Fn=⎨()2()2F+Fn≥2且为奇数⎪⎡⎤n/2⎡⎤n/2−12⎪()F+2FFn≥2且为偶数⎩⎡⎤n/2⎡⎤⎡⎤n/2n/2−1-算法：Fibonacci(intn)a←Fibonacci((n+1)/2);{ifn=0orn=1thenb←Fibonacci((n+1)/2-1);returnn;ifnmod2=0thenelse{returna*(a+2*b);e
8、lsereturna*a
