吴文虎程序设计基础第2版递推算法举例08.ppt

1,青蛙过河,快速排序,分书问题,计算组合数,6.4 递归算法举例,2,3,mn| n=1 c(m,n) m=0|n=0 n=m n!=m 0 m 1 c(m-1,n) c(m-1,n-1) c(m-1,n)+ c(m-1,n-1),4,/ * / * 程 序 名：6_7.cpp * / * 编制时间：2002年10月28日 * / * 主要功能：计算组和数C(m,n) * / * #include / 预编译命令 using namespace std;,5,int Cmn( int m, int n) if (m0 | n0 | mn) return 0; if (m=n) / C(m,m)=1 return 1; if (n=1) / C(m,1)=m return m; return Cmn(m-1, n)+Cmn(m-1,n-1); ,6,int main() / 主函数开始 / 测试一些结果 cout “C(6,0)=“ Cmn(6,0) endl; cout “C(6,1)=“ Cmn(6,1) endl; cout “C(6,2)=“ Cmn(6,2) endl; cout “C(6,6)=“ Cmn(6,6) endl; return 0; / 主函数结束,7,递 归 算 法 举 例 青蛙过河,8,讨论问题青蛙过河,该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下： 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？,9,思路： 1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。 2. 定义函数 Jump ( s ,y ) 最多可跳过河的青蛙数 其中： S 河中柱子数 y 荷叶数,10,3. 先看简单情况，河中无柱子：S = 0 ， Jump ( 0 , y ) 当 y = 1 时，Jump ( 0 , 1 ) = 2 ； 第一步：1# 跳到荷叶上； 第二步：2# 从 L 直接跳至 R 上； 第三步：1# 再从荷叶跳至 R 上。 如下图： 1# 2#,11,当 y = 2 时， Jump ( 0 , 2 ) = 3 ； 1#，2#，3# 3只青蛙落在 L 上， 第一步：1# 从 L 跳至叶 1上， 第二步：2# 从 L 跳至叶 2上， 第三步：3# 从 L 直接跳至 R 上， 第四步：2# 从叶 2 跳至 R 上， 第五步：1# 从叶 1 跳至 R 上，,采用归纳法： Jump ( 0 , y ) = y+1；,12,再看Jump( S, y ) 先看一个最简单情况： S = 1，y = 1 。 从图上看出需要 9 步，跳过 4 只青蛙。 1# 青蛙从 L Y； 2# 青蛙从 L S； 1# 青蛙从 Y S； 3# 青蛙从 L Y； 4# 青蛙从 L R； 3# 青蛙从 Y R； 1# 青蛙从 S Y； 2# 青蛙从 S R； 1# 青蛙从 Y R；,13,表一,14,为了将过河过程描述得更清楚，我们给出了表1。表中L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。L1 在最上面，L4 在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理R1 R2 R3 R4也是如此。对水中石柱S，也分成两个高度位置S1 S2。对荷叶Y无须分层，因为它只允许一只青蛙落在其上。t=0为初始时刻，青蛙从小到大落在石柱L上。t=1为第一步：1#从L跳至荷叶Y上；L上只剩2# 3# 4#。T=2 为第二步；2#从L跳至石柱S上，处在S2位置上，L上只剩3#和4#。T=3为第三步，1#从Y跳至S，将Y清空。这时你看，S上有1#、2#，L上有3#、4#，好象是原来在L上的4只青蛙，分成了上下两部分，上面的2只通过荷叶y转移到了S上。这一过程是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了S上。这时我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。,15,2,Y,R,S,L,3,1,16,L-Y-S ,将 L上的一半青蛙转移到 S 上 L-Y-R,将 L上的青蛙转移到 R 上 S-Y-R,将 S 上的青蛙转移到 R 上 对于LYR系统，相当于Jump(0,1) 对于SYR系统，相当于Jump(0,1) 两个系统之和为2*Jump(0,1)，因此有： Jump(1,1)=2*Jump(0,1)=2*2=4,17,现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作S1和S2，荷叶叫y，考虑先将L上的青蛙的一半借助于S2和y转移到S1上，当然是一半小号的青蛙在S1上，大的留在L上。,18,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1,19,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 1,20,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 2 1,21,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 2 3 1,22,L-S2-Y-S1 以S1为跳转的目的地，从L经S2Y到S1,相当于JAMP（1，1）=4, 即S1 上有4 只青蛙，L上还保留4 只。 1 2 Y 3 4 5 1 6 2 L 7 S2 1 3 S1 8 2 4,23,L,R,Y,S2,S1,24,L Y R S2 S1 LS2YR S1S2YR,25,这样 L S1 S2 y R 系统分解为 ： （L S2 y R 系统） + （S1 S2 y R 系统） = 2 * （L S2 y R 系统） = 2 * Jump(1,1) 用归纳法 Jump(S, y)=2*Jump(S-1, y),26,5. 将上述分析出来的规律写成递归形式的与或结点图为：,27,举例：S=3，y=4，算 Jump(3,4),28,/ * / * 程 序：6_5.cpp * / * 作 者：wuwh * / * 编制时间：2002年10月20日 * / * 主要功能：青蛙过河(递归) * / *,29,#include /预编译命令 int Jump(int, int); /声明有被调用函数 int main() /主函数 int s=0,y=0,sum=0; cout s; /输入正整数s cout y; /输入正整数y sum = Jump ( s , y ) ; /Jump(s,y)为被调用函数 cout “Jump(“ s “,“ /输出结果 y “)=“ sum endl; return 0; ,30,/以下函数是被主程序调用的函数 int Jump ( int r, int z ) /自定义函数, r , z 为形参 /自定义函数体开始 int k=0; /整型变量 if (r=0) /如果 r 为 0 ,则为直接可解结点, k = z + 1; /直接可解结点, k 值为 z + 1 else /如果r不为0,则要调用Jump( r-1, z ) k=2*Jump(r-1,z); return ( k ) ;/将 k 的值返回给 Jump ( s , y ) /自定义函数体结束,31,递 归 算 法 举 例 快速排序,32,快速排序的思路： 1、将待排序的数据放入数组 a 中，下标从 z 到 y ； 2、取 a z 放变量 k 中，通过分区处理，为 k 选择应该排定的位置。这时要将比 k 大的数放右边，比 k 小的数放左边。当 k 到达最终位置后，由 k 划分左右两个集合。然后再用同样的思路处理左集合与右集合。 3、令sort( z ,y )为将数组元素从下标为 z 到下标为 y 的 y z + 1 个元素从小到大排序。,33,z y k z m y m-1 m+1 z m-1 m m+1 y,34,我们画出与或图来阐述快速排序的思路：,35,A sort( z,y ) z=y zy B C 不做事 D E F 分区处理 sort(z,m-1) sort(m+1,y),36,分区处理： k 1、让 k=a z a = y，则什么也不做。这是直接可解结点。 C 结点是在 z y 情况下 A 结点的解。C 是一个与结点。要对 C 求解需分解为三步。依次为：,37,1、先解 D 结点，D 结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是 （1）将 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。 （见下图）,38,a,z,y,a,m,下标：,下标：,z,m-1,y,m+1,39,2、再解 E 结点，这时要处理的是 a 0 a 3 ； 3、再解 F 结点，处理a 5 ,a 6 。 下面按照这种思路构思一个快速排序的程序框图。 void sort( int array , int zz, int yy ) int z, y, i , k ;,40,z,y,k,54,52,56,53,51,57,41,42,下面举例说明排序过程,图1 a数组中有7个元素待排序 1 让 k = a z = a 0 = 5,z,y,图 1,k,43,2 进入直到型循环 执行（1）ay=a6=4 不满足当循环条件，y不动。 执行（2）zy，做两件事： a z = a y ，即a 0 = a 6 = 4， z = z +1 = 0+1 = 1，见图2,z,y,图 2,k,44,执行（3）图2中的a1 5,z,y,图 3,k,45,执行（4）ay=az，即a6=a2=6，见图4。这时 z != y 还得执行直到型循环的循环体。,z,y,图 4,k,46,执行（1）ay=a6=6，6k满足当循环的条件， y = y-1 = 6-1 = 5 见图5，之后退出当循环，因为 a y = 3k (k=5),z,y,图 5,k,47,执行（2）a z =a y ，并让 z = z+1=3，见图6,z,y,图 6,k,48,执行（3）由于a3=1k，退出循环。见图7,z,y,图 7,k,49,执行（4）az=ay，a5=7。见图8 这时仍然 zy ，应继续执行直到型循环的循环体。,z,y,图 8,k,50,执行（1），a y = 7k，让 y = y-1 = 4。见图9,z,y,图 9,k,51,之后，z = y，退出直到型循环，做 a z = k，z = 4， a 4 = 5，这是 5 的最终位置，5 将整个数据分成左右两个集合，见图10。,z,y,图 10,左,右,k,52,用上述思路去排左边的部分 从 z = 0 到 y = 3，见图11。让 k = a z = a 0 = 4，然后进到直到型循环， 执行（1）a y = 1k，不满足当循环的条件，y不动。 执行（2）a z = a y ，z = z+1 = 1, 见图12,z,y,图 12,z,y,图 11,k,53,执行（3）a z k，z=z+1=2，a2k，z=z+1=3，这时z=y，不会执行（4），同时退出直到型循环，见图13。然后做 a z =k，即a 3 =4，见图14，左边也排好了。,图 14,z,y,图 13,z,y,k,k,54,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,图 16,z,y,图 15,z,y,k,55,这时 z = y，不再执行（3）（4），退出直到型循环后，做 a z = k，见图17。,图 17,z,y,k,56,在有了递归调用函数之后，主程序很容易写，主程序中应包含 1、 定义整型变量：数组 a10 ，i ； 2、 用循环结构输入待排序的数，将其放入 a 数组； 3、 调用 sort 函数，使用三个实际参数 a将数组 a 当实参； 0数组下标下界； 9数组下标上界； 4、 输出排序结果 下面给出参考程序（分两页）,57,/ * / * 程 序：6_6.cpp * / * 作 者：wuwh * / * 编制时间：2002年10月28日 * / * 主要功能：快速排序 * / * #include /预编译命令 using namespace std;,58,void sort(int array , int zz, int yy) /被调用函数，数组array,zz,yy为形参 /函数体开始 int z,y,i,k; /定义变量 if ( zz=k) y-; /2.1,右边的元素=k,让 y 往中间移 if( z k, 让 array z array y = array z ; /送给array y while( z != y ) ; /第2件事(结束),59,array z = k; /第3件事,k已排到位 for(i = zz ;i a i ; sort(a,0,9); /调用sort函数,实参为数组a和0，9 cout “排序结果为:“; /提示信息 for (i =0; i10 ;i+ ) cout a i “;“; /输出排序结果 cout endl; return 0; /主函数结束,60,void sort(int array , int zz, int yy) /被调用函数，数组array,zz,yy为形参 /函数体开始 int z,y,i,k; /定义变量 if ( zzyy ) /如果 zz yy ,则做下列 7 件事:,61, / 7 件事开始 z = zz; y = yy; k = array z ; /第1件事,62,do /第2件事(开始) while( z=k) y-; /2.1,右边的元素=k,让 y 往中间移 if( z k, array y = array z ; while( z != y ) ; /第2件事(结束),63,k z y while(z=k) y- ; /2.1,右边的元素=k,让 y 往中间移,64,k z y if( z y ) array z = array y ; z = z+1; ,65,k z y while(zk; array y = array z ;,66,z y 5 2 6 1 7 3 4 z y 4 2 6 1 7 3 4 k z y 5 4 2 6 1 7 3 6 z y 4 2 3 1 7 3 6 z y 4 2 3 1 7 7 6 zy 4 2 3 1 5 7 6,67,array z = k; /第3件事,k已排到位 for(i = zz ;i = yy ;i+) /第4件事，输出 cout“a“i“=“ array i “; “; cout endl; /第5件事，换行 sort( array, zz ,z-1 ); /第6件事，排左边部分 sort( array ,z+1, yy); /第7件事，排右边部分 /7件事结束 /函数体结束,68,int main() /主函数开始 int a10, i=0; /整型变量 cout a i ; sort( a, 0, 9 ) ; /调用sort函数,实参为数组a和0,9 cout “排序结果为:“; /提示信息 for (i =0; i10 ;i+ ) cout a i “;“; /输出排序结果 coutendl; return 0; /主函数结束,69,研究 sort( a , 0, 9 ) 主函数 调用 sort ( a , 0 , 9 ) 实在参数 子函数中 sort ( array, zz, yy ) 形式参数 a 0 9 Array zz yy &Array &zz &yy,70,研究 sort( a , 0, 9 ) a 3 5 6 1 4 7 9 8 0 2 0 1 2 3 4 5 6 7 8 9 array 3 5 6 1 4 7 9 8 0 2 0 1 2 3 4 5 6 7 8 9,71,a array a 3 5 6 1 4 7 9 8 0 2 0 1 2 3 4 5 6 7 8 9 实参a所表示的数组与形参array所表示的数组是同一个数组,72,小结： 1，数组也可作参数，数组a,0,9为实参，数组array,zz,yy为形参。 2，只在被调用时系统才为array,zz,yy 分配内存单元，调用后释放掉内存单元. array 赋值为 a, 是说 array就是a数组，讲到指针时再详细解释。 3, zz 和 yy 为数组的下标,是参加排序的数组元素的左右边界。,73,递 归 算 法 举 例 分书问题,74,教学目标：巩固用递归思想编写程序 教学内容：分书问题 题 目：有编号分别为 0，1，2，3，4 的五本书，准备分给 A, B, C, D, E 五个人，每个人阅读兴趣用一个二维数组加以描述：,75,希望你写一个程序，输出所有分书方案，让人人皆大欢喜。假定 5 个人对 5 本书的阅读兴趣如下表：,0 1 2 3 4 A B C D E,人,书,76,1、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义 int like55 = 0,0,1,1,0 , 1,1,0,0,1, , 0,1,1,0,1 ,0,0,0,1,0 ,0,1,0,0,1 ; 2、定义一个整型一维数组book5用来记录书是否已被选用。用下标作为五本书的标号，被选过元素值为1，未被选过元素值为0，初始化皆置0。 int book5= 0,0,0,0,0 ;,解题思路：,77,3、画出思路图 定义 Try( i )试着给第 i 人分书 ( i=0, 1, 4 ),78,79,说明： （1）试着给第 i 个人分书，先试分 0 号书，再分 1 号书，分 2 号书，因此有一个与结点，让 j 表示书 j = 0, 1, 2, 3 , 4 。 （2）LP 为循环结构的循环体。 （3）条件 C 是由两部分“与”起来的。“第 i 个人喜欢 j 书，且 j 书尚未被分走”。满足这个条件是第 i 人能够得到 j 书的条件。 （4）如果不满足 C 条件，则什么也不做，这是直接可解结点。,80,（5）满足C条件，做三件事。 sh1第一件事： 将 j书分给 i，用一个数组 take i =j， 记住书 j 给了 i ， 同时记录 j 书已被选用，book j = 1。,81,sh2第二件事： 查看 i 是否为 4，如果不为 4，表示尚未将所有 5 个人所要的书分完，这时应递归再试下一人，即Try( i+1 )。 如果 i = 4，则应先使方案数 n = n+1，然后输出第 n 个方案下的每个人所得之书。,82,Sh3第三件事：回溯。让第 i 人退回 j 书，恢复 j 书尚未被选的标志，即 book j = 0。这是在已输出第 n 个方案之后，去寻找下一个分书方案所必需的。 （6）在有了上述的与或图之后，我们很容易写出一个程序框图。先看被调用函数 Try( i ) 的框图。,83,84,/ * / * 程 序：6_7.cpp * / * 作 者：wuwh * / * 编制时间：2002年10月28日 * / * 主要功能：分书问题 * / * #include /预编译命令 using namespace std; int take5,n; /整型变量 int like55 = 0,0,1,1,0, 1,1,0,0,1, 0,1,1,0,1, 0,0,0,1,0, 0,1,0,0,1 ;/整型变量,定义数组，初始化 int book5=0,0,0,0,0; /整型变量,定义数组，初始化,下面讨论主程序应该做的事情 1、将分书方案号预置0 2、从第0号人（A）开始试分书，调用Try(0),85,void Try(int i) /函数体开始 int j,k; /定义变量 for(j=0;j0) /记录j书待分 sh3 / j 循环体开始 ,86,int main() /主函数 /主函数开始 n=0; /分书方案号预置0 Try(0); /调用Try函数,实参为0 return 0; /主函数结束,87,结 束,