程序设计基础w10－chap09－1－20141124－第09章－递归－[方阵-组合-快排

1、课前思考题课前思考题你认为以下三个公式有区别吗？你认为以下三个公式有区别吗？整理课件2第九章递归思想与相应算法32003200整理课件相传，在古代印度名为Bramah的庙中，僧人们整天把三根柱子上的金盘倒来倒去，原来他们想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。在盘子的移动过程中，要求恪守下述规则：每次只允许移动一只盘，且大盘不得摞在小盘上面。请你帮助他们制定移盘的步骤！3印度神庙僧侣的金盘任务整理课件有人可能会觉得这个问题很简单，而实际上，如果真的动手进行数学推算就会发现：即便一秒钟移动一只盘子，按照上述规则，要将64只盘子从一个柱子移至另一个柱子上，需要大约5800亿年！

2、这个僧侣移盘问题，通常被称为汉诺(Hanoi)塔问题。解决这个问题最经典的算法就是递归。4任务 整理课件递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。递归算法不涉及高深数学知识，不过初学者要建立起递归概念并不十分容易。 递归及其实现递归及其实现5整理课件为了帮助我们思考和表述递归算法的思路，使算法更为了帮助我们思考和表述递归算法的思路，使算法更直观和清晰，我们定义两个结点：直观和清晰，我们定义两个结点：或结点或结点和和与结点。与结点。1、或结点、或结点,BZ trueCZfalseA（真）（假） A 条条件件 Z 条条件件!Z B C A为为“或结点或

3、结点”，A依不同条件会有两种不同的取值依不同条件会有两种不同的取值, B 或或C。结点用。结点用 表示。表示。 6辅助递归算法设计的工具整理课件如果有多于如果有多于 2 种取值，可用下图：种取值，可用下图： Z1 Z2 Zn B C G A 条件为条件为 Z1 , Z2 , ,Zn ,Z1 , Z2 , ,Zn , A A 取值为取值为 B B 或或 C, C, 或或 G G7整理课件2、与结点、与结点与结点与结点要涂黑，相关要涂黑，相关联的联的 B 与与 C 之间要用之间要用弧线连起来。弧线连起来。A 为为与结点与结点，A 的最终取值为的最终取值为 C 结点的值，结点的值，但为了求得但为了求

4、得 C 的值，得先求出的值，得先求出 B 结点的值结点的值, C 是是B 的函数。的函数。ABC8整理课件与结点与结点可能有多个相关联的点，这时可描述为下图可能有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。先求左边的点才能求最右边的点的值先求左边的点才能求最右边的点的值，约，约定最右边定最右边 D 点的值就是点的值就是 A 结点的值。结点的值。ABDC9整理课件例：试编写一个函数fact(n)，求解阶乘 n !10下面分别使用“枚举”、“递推”、“递归”等三种不同的算法思想来实现该函数，请注意对比不同方法的

5、代码内容。什么样的程序是递归程序？整理课件设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 m

6、10; / / / / 假设假设求求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

7、;/ / 直接返回结果直接返回结果 return n * fact(n-1); / n * (n-1)! / / 自己调用自己：递归自己调用自己：递归int main() cout fact(3) = fact(3) 1Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE2116整理课件对于对于fact(n)的递归实现，它的的递归实现，它的与或图与或图如下：如下：A 为为或结点或结点；B 为直接可解结点，值为为直接可解结点，值为1；C 为为与结点与结点，当当 n1 时，时，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，的值，为了求得

8、为了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即为即为 E 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)17整理课件递归算法的出发点不是在初始条件上，而是在求解目标上，即从所求的未知项出发，逐次调用本身直到递归边界（即初始条件）的求解过程。就本例而言，大家或许会认为使用递归算法没有必要，费力不讨好。但有许多实际问题往往不可能或很难找到显而易见的递推关系，这时，递归算法就表现出明显的优越性。我们将通过不同类型的示例问题来说明：递归算法比较符合人的思维方式，逻辑性强，可将

9、问题描述得简单扼要，可读性强，易于理解。许多看来相当复杂或难以下手的问题，如果能够使用递归算法，就会变得易于处理。18整理课件19整理课件9.2 9.2 递递 归归 算算 法法 举举 例例 方阵填充方阵填充20整理课件21整理课件22整理课件Fill( number,begin,size)23整理课件24整理课件25整理课件26整理课件27整理课件28整理课件29整理课件30整理课件31整理课件32整理课件33整理课件34整理课件35整理课件SIZE SIZE 是奇数时是奇数时36整理课件源代码略37整理课件9.2 9.2 递递 归归 算算 法法 举举 例例 组合数计算组合数计算38整理课件我

10、们画出我们画出与或图与或图来阐述求解思路：来阐述求解思路：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) endl; return 0;整理课件整理课件9.2 9.2 递递 归归 算算 法法 举举 例例 快速排序快速排序42整理课件“与或图与或图”对应的快速排序思

11、路对应的快速排序思路：1、将待排序的数据放入数组、将待排序的数据放入数组 a 中，下标从中，下标从 z 到到 y ；2、令、令sort( z ,y )为将数组元素从下标为为将数组元素从下标为 z 到下标为到下标为 y 的的 y z + 1 个元素从小到大排序。个元素从小到大排序。3、取、取 a z 放变量放变量 k 中，通过分区处理，为中，通过分区处理，为 k 选择应选择应该排定的该排定的位置位置 将比将比 k 大的数放右边，比大的数放右边，比 k 小小的数放左边的数放左边。当。当 k 到达最终位置后，由到达最终位置后，由 k 划分左划分左右两个集合。然后再右两个集合。然后再用同样的思路处理用

12、同样的思路处理左集合与左集合与右集合右集合。43整理课件44整理课件我们画出与或图来阐述快速排序的思路：我们画出与或图来阐述快速排序的思路：函数函数sortsort有两个参数（有两个参数（z z和和y y），分别表示数组中一个片段的），分别表示数组中一个片段的起始与终止下标值。起始与终止下标值。STEP 1. STEP 1. 比比arrayzarrayz小的元素交换到数组左边，大的元素交换到数组右边小的元素交换到数组左边，大的元素交换到数组右边STEP 2. STEP 2. 将将arrayzarrayz元素放到新位置上，下标是元素放到新位置上，下标是 m m45整理课件分区处理：分区处理： k

13、1、让、让 k=a z a 2、将、将 k 放在放在 a m z m y3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，则什么也不做。这是直接可，则什么也不做。这是直接可解结点。解结点。C 结点是在结点是在 z y 情况下情况下 A 结点的解。结点的解。C 是一个是一个与结与结点点。要对。要对 C 求解需分解为三步。依次为：求解需分解为三步。依次为：46整理课件1、先解、先解 D 结点，结点，D 结点是一个直接可解结点，功能是结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是进行所谓的分区处理，规定这一步要做的事情是（1）将）将

14、a z 中的元素放到它应该在的位置上，比如中的元素放到它应该在的位置上，比如 m 位置。这时位置。这时 a m a z ；（2）让下标从）让下标从 z 到到 m-1 的数组元素小于等的数组元素小于等于于a m ；（3）让下标从）让下标从 m+1 到到 y 的数组元素大于的数组元素大于a m ； 比如比如: a 数组中数组中 a z = 5，经分组处理后，经分组处理后，5 送至送至 a 4 。5 到位后，其左边到位后，其左边 a 0 a 3 的值都小于的值都小于 5；其右边其右边 a 5 , a 6 都都大于大于 5。47整理课件2、再解、再解 E 结点，这时要处理的是结点，这时要处理的是 a

15、0 a 3 ；3、再解、再解 F 结点，处理结点，处理a 5 , a 6 。下面按照这种思路构思一个快速排序的程序框图下面按照这种思路构思一个快速排序的程序框图。48整理课件 ll r r l= ll; r = r r ; k = a r r a y l; T F d o w h ile (l = k ) (1 ) r = r-1 ; l r (2 ) T F a r r a y l= a r r a y r ; l= l+ 1 w h ile (l r )& & (a r r a y l = k ) (3 ) l= l+ 1 ; l r ; (4 ) T F a r r a

16、y r = a r r a y l; w h ile (l!= r ); a r r a y l= k ; fo r (i= ll; i45253515750动画演示动画演示整理课件下面举例说明排序过程下面举例说明排序过程图图1 a数组中有数组中有7个元素待排序个元素待排序1 让让 k = a z = a 0 = 5zy图图 1k51整理课件2 进入直到型循环进入直到型循环 执行（执行（1）ay=a6=4 不满足当循环条件，不满足当循环条件，y不动。不动。 执行（执行（2）zy，做两件事：，做两件事： a z = a y ，即，即a 0 = a 6 = 4， z = z +1 = 0+1 =

17、1，见，见图图2zy 图图 2k52整理课件 执行（执行（3）图）图2中的中的a1 5zy图图 3k53整理课件 执行（执行（4）ay=az，即，即a6=a2=6，见，见图图4。这时。这时 z != y 还得执行直到型循环的循环体。还得执行直到型循环的循环体。zy图图 4k54整理课件 执行（执行（1）ay=a6=6，6k满足当循环的条件，满足当循环的条件，y = y-1 = 6-1 = 5见见图图5，之后退出当循环，因为，之后退出当循环，因为 a y = 3k (k=5)zy图图 5k55整理课件 执行（执行（2）a z =a y ，并让，并让 z = z+1=3，见，见图图6 zy图图 6

18、k56整理课件 执行（执行（3）由于）由于a3=1k，退出循环。见，退出循环。见图图7 zy图图 7k57整理课件 执行（执行（4）az=ay，a5=7。见。见图图8 这时仍然这时仍然 zk，让，让 y = y-1 = 4。见。见图图9zy图图 9k59整理课件 之后，之后，z = y，退出直到型循环，做，退出直到型循环，做 a z = k，z = 4， a 4 = 5，这是，这是 5 的最终位置，的最终位置，5 将整个数据分成左右将整个数据分成左右两个集合，见两个集合，见图图10。zy图图 10左左右右k60整理课件用上述思路去排左边的部分用上述思路去排左边的部分从从 z = 0 到到 y

19、= 3，见，见图图11。让。让 k = a z = a 0 = 4，然后，然后进到直到型循环，进到直到型循环， 执行（执行（1）a y = 1k，不满足当循环的条件，不满足当循环的条件，y不动。不动。 执行（执行（2）a z = a y ，z = z+1 = 1, 见见图图12zy图图 12zy图图 11k61整理课件 执行（执行（3）a z k，z=z+1=2，a2k，z=z+1=3，这时，这时z=y，不会执行（，不会执行（4），同时退出直到型循环，见），同时退出直到型循环，见图图13。然后做然后做 a z =k，即，即a 3 =4，见图，见图14，左边也排好了。，左边也排好了。图图 14z

20、y图图 13zykk62整理课件4、用上述思路去排右边的部分，见、用上述思路去排右边的部分，见图图15，让，让k = a z = a 5 = 7，进入直到型循环；，进入直到型循环； 执行（执行（1）a y = 6k，y不动不动 执行（执行（2）a z = a y =6，z = z+1=5+1=6，见，见图图16图图 16zy图图 15zyk63整理课件这时这时 z = y，不再执行（，不再执行（3）（）（4），退出直到型循环后，），退出直到型循环后，做做 a z = k，见图，见图17。图图 17zyk64整理课件在有了递归调用函数之后，主程序很容易写，主程在有了递归调用函数之后，主程序很容易

21、写，主程序中应包含序中应包含1、 定义整型变量：数组定义整型变量：数组 a10 ，i ；2、 用循环结构输入待排序的数，将其放入用循环结构输入待排序的数，将其放入 a 数组；数组；3、 调用调用 sort 函数，使用三个实际参数函数，使用三个实际参数a将数组将数组 a 当实参；当实参；0数组下标下界；数组下标下界；9数组下标上界；数组下标上界；4、 输出排序结果输出排序结果下面给出参考程序（分两页）下面给出参考程序（分两页）65整理课件/ */ * 程程 序：序：6_6.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月28日日 */ * 主要功能：快

22、速排序主要功能：快速排序 */ *#include / coutusing namespace std;void sort(int array , int zz, int yy) /被调用函数，数组被调用函数，数组array,zz,yy为形参为形参int z,y,i,k; /定义变量定义变量 if ( zzyy ) /如果如果 zz yy ,则做下列则做下列 7 件事件事: / 7 件事开始件事开始z = zz; y = yy; k = array z ; /第第1件事件事do /第第2件事件事(开始开始) while( z=k) y-; /2.1,右边的元素右边的元素=k,让让 y 往中间移

23、往中间移 if( z y ) /2.2,右边的元素右边的元素k,让让 array z = array y ; /array y 送给送给 array z ， z = z+1; /同时让同时让 z 往中间移往中间移 while( z y) & (arrayz = k) z+; /2.3,左边的元素左边的元素=k,让让 z 往中间移往中间移 if ( z k, 让让 array z array y = array z ; /送给送给array y while( z != y ) ; /第第2件事件事(结束结束)66整理课件array z = k; /第第3件事件事,k已排到位已排到位for

24、(i = zz ;i = yy ;i+) /第第4件事，输出件事，输出 coutai=arrayi; ;cout endl; /第第5件事，换行件事，换行sort( array, zz ,z-1 ); /第第6件事，排左边部分件事，排左边部分sort( array ,z+1, yy); /第第7件事，排右边部分件事，排右边部分 /7件事结束件事结束 /函数体结束函数体结束int main() /主函数开始主函数开始int a10,i; /整型变量整型变量cout 请输入请输入10个整数个整数n; /提示信息提示信息for (i = 0; i a i ;sort(a,0,9);/调用调用sort

25、函数函数,实参为数组实参为数组a和和0，9cout 排序结果为排序结果为:; /提示信息提示信息for (i =0; i10 ;i+ ) cout a i ;/输出排序结果输出排序结果cout endl; return 0;/主函数结束主函数结束 67整理课件/ */ * 程程 序：序：6_6.cpp * / * 作作 者：者：wuwh * / * 编制时间：编制时间：2002年年10月月28日日 * / * 主要功能：快速排序主要功能：快速排序 * / *68整理课件#include /cout using namespace;void sort(int array , int zz, in

26、t yy)/被调用函数，数组被调用函数，数组array,zz,yy为形参为形参 /函数体开始函数体开始 int z,y,i,k; /定义变量定义变量 if ( zzyy ) /如果如果 zz yy ,则做下列则做下列 7 件事件事:69整理课件 / 7 件事开始件事开始 z = zz; y = yy; k = array z ; /第第1件事件事70整理课件do /第第2件事件事(开始开始) while( z=k) y-; /2.1,右边的元素右边的元素=k,让让 y 往中间移往中间移 if( z y ) /2.2,右边的元素右边的元素k,让让 /array y 送给送给 array z ， /同时让同时让 z 往中间移往中间移 array z = ar