算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第4章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第4章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章递归和分治4.1递归4.2树和图中的递归问题4.3分治法的基本思想4.4归并排序和快速排序4.5若干最优化问题4.6大数乘法和Strassen矩阵乘法4.1递归递归的基本概念递归算法的效率分析汉诺塔问题幂集和全排列4.1.1递归的基本概念在计算公式中直接或间接调用自身的函数称为递归函数在计算代码中直接或间接调用自身的算法称为递归算法AlgorithmFact(n:int)beginif(n=0)thenreturn1;elsereturnn*Fact(n-1);end4.1.1递归的基本概念在计算公式中直接或间接调用自身的函数称为递归函

2、数在计算代码中直接或间接调用自身的算法称为递归算法AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);end4.1.1递归的基本概念Fib(4)AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);endFib(4)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)AlgorithmFib(n:int)beginif(n≤1)thenreturn1;el

3、sereturnFib(n-1)+Fib(n-2);endFib(4)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);endFib(2)Fib(3)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)Fib(3)=Fib(2)+Fib(1)AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2

4、);endFib(2)Fib(3)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)Fib(3)=Fib(2)+Fib(1)t=Fib(1)=1AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);endFib(2)Fib(2)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)Fib(3)=Fib(2)+Fib(1)t=Fib(1)=1Fib(2)=Fib(1)+Fib(0)=2t=t+2=3AlgorithmFib(n:int

5、)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);endFib(2)Fib(2)4.1.1递归的基本概念Fib(4)=Fib(3)+Fib(2)Fib(3)=Fib(2)+Fib(1)t=Fib(1)=1Fib(2)=Fib(1)+Fib(0)=2t=t+2=3Fib(2)=Fib(1)+Fib(0)=2t=t+2=5AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);endFib(2)4.1.1递

6、归的基本概念Fib(4)=5AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);end4.1.2递归算法的效率分析t(1)=t(0)=1t(n)=t(n1)+t(n2)+1AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);end4.1.2递归算法的效率分析t(1)=t(0)=1t(n)=t(n1)+t(n2)+1=t(n−2)+t(n−3)+1+t(n−2

7、)+1=2t(n−2)+t(n−3)+1+1=2(t(n−3)+t(n−4)+1)+t(n−3)+1+1=3t(n−3)+t(n−4)+1+1+2=……=(n−1)t(1)+t(0)+1+(1+2+…+n−2)=2+n(n−1)/2AlgorithmFib(n:int)beginif(n≤1)thenreturn1;elsereturnFib(n-1)+Fib(n-2);end4.1.2递归算法的效率分析确定问题的规模度量参数；确定算法的基本结构和主要操作步骤；针对算法主要操作的执行次数，建立其递归关系的表达式；展开递归表达式，以此来确定算法

8、的时间复杂度。4.1.3汉诺塔问题有A、B、C三个塔座，开始时A塔座上从下到上依次叠放了大、中、小3个圆盘，现要将这3个圆盘移到塔座B上，并仍按原顺序排列。圆盘可以