课课前前思思考考题题你认为以下三个公式有区别吗？你认为以下三个公式有区别吗？2第九章递归思想与相应算法320032002014.11.242014.11.24相传，在古代印度名为Bramah的庙中，僧人们整天把三根柱子上的金盘倒来倒去，原来他们想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。在盘子的移动过程中，要求恪守下述规则：每次只允许移动一只盘，且大盘不得摞在小盘上面。请你帮助他们制定移盘的步骤！3印度神庙僧侣的金盘任务有人可能会觉得这个问题很简单，而实际上，如果真的动手进行数学推算就会发现：即便一秒钟移动一只盘子，按照上述规则，要将64只盘子从一个柱子移至另一个柱子上，需要大约5800亿年！这个僧侣移盘问题，通常被称为汉诺(Hanoi)塔问题。解决这个问题最经典的算法就是递归。4任务递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。递归算法不涉及高深数学知识，不过初学者要建立起递归概念并不十分容易。9.1递归及其实现递归及其实现5为了帮助我们思考和表述递归算法的思路，使算法更直为了帮助我们思考和表述递归算法的思路，使算法更直观和清晰，我们定义两个结点：观和清晰，我们定义两个结点：或结点或结点和和与结点。与结点。1、或结点、或结点A为为“或结点或结点”，A依不同条件会有两种不同的取值依不同条件会有两种不同的取值,B或或C。结点用。结点用表示。表示。6辅助递归算法设计的工具如果有多于如果有多于2种取值，可用下图：种取值，可用下图： 条件为条件为 Z1 , Z2 , ,Zn ,Z1 , Z2 , ,Zn , A A 取值为取值为 B B 或或 C, C, 或或 G G72、与结点、与结点与结点与结点要涂黑，相关要涂黑，相关联的联的B与与C之间要用之间要用弧线连起来。弧线连起来。A为为与结点与结点，A的最终取值为的最终取值为C结点的值，结点的值，但为了求得但为了求得C的值，得先求出的值，得先求出B结点的值结点的值,C是是B的函数。的函数。8与结点与结点可能有多个相关联的点，这时可描述为下图可能有多个相关联的点，这时可描述为下图A结点的值最终为结点的值最终为D的值，但为了求的值，但为了求D需先求需先求B和和C。先求左边的点才能求最右边的点的值先求左边的点才能求最右边的点的值，约，约定最右边定最右边D点的值就是点的值就是A结点的值。结点的值。9例：试编写一个函数fact(n)，求解阶乘 n !10下面分别使用“枚举”、“递推”、“递归”等三种不同的算法思想来实现该函数，请注意对比不同方法的代码内容。什么样的程序是递归程序？设fact(n)是一个求 n !的函数11/ 使用枚举思想，求解正整数的阶乘#include using namespace std;int fact(int n) int m = 1; for (int i=1; i=n; i+) m = m * i; return m;int main() cout fact(3) = fact(3) endl; return 0; 设fact(n)是一个求 n !的函数12/ 使用递推思想，求解正整数的阶乘#include using namespace std;int fact(int n) int m10; / / / / 假设假设求求10以内整数的阶乘以内整数的阶乘 m1 = 1; / / 递推的起始值递推的起始值 for (int i=2; i=n; i+) mi = mi-1 * i; return mn;/ / 返回递推的终值返回递推的终值int main() cout fact(3) = fact(3) endl; return 0; 设fact(n)是一个求 n !的函数13/ 使用递归算法，求解正整数的阶乘#include using namespace std;int fact(int n) if (n = 1)/ / 递归的终止条件递归的终止条件 return 1;/ / 直接返回结果直接返回结果 return n * fact(n-1); / n * (n-1)! / / 自己调用自己：递归自己调用自己：递归int main() cout fact(3) = fact(3) 1时，时，A的取值即的取值即C的值，而的值，而C的值即的值即E的值，的值，为了求得为了求得E的值，需要先求出的值，需要先求出D的值。的值。D值值fact(n-1)乘以乘以n即为即为E的值。的值。17递归算法的出发点不是在初始条件上，而是在求解目标上，即从所求的未知项出发，逐次调用本身直到递归边界（即初始条件）的求解过程。就本例而言，大家或许会认为使用递归算法没有必要，费力不讨好。但有许多实际问题往往不可能或很难找到显而易见的递推关系，这时，递归算法就表现出明显的优越性。我们将通过不同类型的示例问题来说明：递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，可读性强，易于理解。许多看来相当复杂或难以下手的问题，如果能够使用递归算法，就会变得易于处理。18199.2 9.2 递递 归归 算算 法法 举举 例例 方阵填充方阵填充20 数字旋转方阵数字旋转方阵1201918171622132313015322333629144233435281352425262712678910112112019181716221323130153223336291442334352813524252627126789101122 用与或图来分析算法思路（流程） size=0 size=1 size1return pbeginbegin=number 填一圈数字； 准备好下一个 number; Fill(number,begin,size-2)Fill(number,begin,size)23 D1120191817162213231301532233362914A142334352813C15242526271267891011 B1 24填写填写SIZE*SIZESIZE*SIZE大小方阵的步骤大小方阵的步骤: :（1）填写外围一圈数字（2）填写内部小方阵（边长为SIZE-2）“（1 1）填写外围一圈数字）填写外围一圈数字”的步骤的步骤: :1.1 填写左上角1.2 填写左边（从上至下）1.3 填写下边（从左至右）1.4 填写右边（从下至上）1.5 填写上边（从右至左）25 令令 size size 表示方阵的尺寸，初始时表示方阵的尺寸，初始时size=Nsize=N h h 表示行表示行 v v 表示列表示列 begin begin 表示每层的起始位置值表示每层的起始位置值 number number 表示当前要填表示当前要填的数字26 先填第一层的第一个数先填第一层的第一个数number(=1)该数的位置该数的位置:行行:h=begin;(begin=0)列列:v=begin;(begin=0)将第一个数将第一个数number放入数组中放入数组中phv=number; 27让 number = number + 1 ( = 2 ) 自上而下，填 A1 h :0 1begin=0; size=6 1 2h=begin; v=begin; 2 3for(i=0; isize-1;i+) 3 4 h+; 4 5 p h v =number; 5 6 number+; 28从左至右，填B1 begin=0 ; number=7; size=6 h=5 ; v=begin; for( i=0 ; isize-1 ; i+ ) v+ ; phv=number; number+; h=5 7 8 9 10 11 v : 1 2 3 4 529自下而上，填C1 v=5begin=0; number=12; h: 0 16h=5 ; v= 5; size=6; 1 15for(i=0; isize-1;i+) 2 14 h- ; 3 13 p h v =number; 4 12 number+; 30从右至左，填从右至左，填D1begin=0;number=17;size=6注意注意h=begin;v=5; for(i=0;isize-2;i+) v- ; phv=number; number+; h= 0 20 19 18 17 v : 1 2 3 431 D1120191817162213231301532233362914A142334352813C15242526271267891011 B1 32 D22132313022333629A223343528C224252627 B2 33 D23336A23435C2 B2 34 D33336C3A33435B3 35 1 24 23 22 21 20 19 2 25 40 39 38 37 18 7*7 3 26 41 48 38 36 17 4 27 42 49 46 35 16 5*5 5 28 43 44 45 34 15 6 29 30 31 32 33 14 3*3 7 8 9 10 11 12 13 1*1SIZE SIZE 是奇数时是奇数时36源代码略379.2 9.2 递递 归归 算算 法法 举举 例例 组合数计算组合数计算38我们画出我们画出与或图与或图来阐述求解思路：来阐述求解思路：39源代码40#include using namespace std;int C(int m, int n) if (m0 | n0 | mn) return 0; if (m = n) return 1; if (n = 1) return m; return C(m-1, n)+C(m-1, n-1);int main() cout C(6,2) = C(6, 2) =yzyBC不做事不做事DEF分区处理分区处理sort(z,m-1)sort(m+1,y)STEP 1. STEP 1. 比比arrayzarrayz小的元素交换到数组左边，大的元素交换到数组右边小的元素交换到数组左边，大的元素交换到数组右边STEP 2. STEP 2. 将将arrayzarrayz元素放到新位置上，下标是元素放到新位置上，下标是 m m45分区处理：分区处理：k1、让、让k=aza2、将、将k放在放在amzmy3、使、使az,az+1,am-1=am4、使、使am=y，则什么也不做。这是直接可，则什么也不做。这是直接可解结点。解结点。C结点是在结点是在z45253515750动画演示动画演示下面举例说明排序过程下面举例说明排序过程图图1a数组中有数组中有7个元素待排序个元素待排序1让让k=az=a0=55 52 26 61 17 73 34 40 01 12 23 34 45 56 6zy图图15 5k512进入直到型循环进入直到型循环执行（执行（1）ay=a6=4不满足当循环条件，不满足当循环条件，y不动。不动。执行（执行（2）zy，做两件事：，做两件事：az=ay，即，即a0=a6=4，z=z+1=0+1=1，见，见图图24 42 26 61 17 73 34 40 01 12 23 34 45 56 6zy图图25 5k52执行（执行（3）图）图2中的中的a154 42 26 61 17 73 34 40 01 12 23 34 45 56 6zy图图35 5k53执行（执行（4）ay=az，即，即a6=a2=6，见，见图图4。这时。这时z!=y还得执行直到型循环的循环体。还得执行直到型循环的循环体。4 42 26 61 17 73 36 60 01 12 23 34 45 56 6zy图图45 5k54执行（执行（1）ay=a6=6，6k满足当循环的条件，满足当循环的条件，y=y-1=6-1=5见见图图5，之后退出当循环，因为，之后退出当循环，因为ay=3k(k=5)4 42 26 61 17 73 36 60 01 12 23 34 45 56 6zy图图55 5k55执行（执行（