声明本课件版权归清华大学计算机系语音技术中心所有未经

《声明本课件版权归清华大学计算机系语音技术中心所有未经》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、声明：本课件版权归清华大学计算机系语音技术中心所有未经许可不得扩散青蛙过河快速排序分书问题习题讨论递归算法举例23m

2、

3、n==1c(m,n)m==0

4、

5、n==0n==mn!=m0m1c(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)*//******************************

6、*******#include//预编译命令Usingnamespacestd;5//计算C(m,n)，即从m个数中取n个数的组合数intC(intm,intn){if(m<0

7、

8、n<0

9、

10、m

11、

12、n<0

13、

14、

15、m

16、;}//主函数结束8intC(intm,intn){if(m<0

17、

18、n<0

19、

20、m

21、，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。

22、当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？11思路：1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。2.定义函数Jump(s,y)——最多可跳过河的青蛙数其中：S——河中柱子数y——荷叶数123.先看简单情况，河中无柱子：S=0，Jump(0,y)当y=1时，Jump(0,1)=2；第一步：1#跳到荷叶上；第

23、二步：2#从L直接跳至R上；第三步：1#再从荷叶跳至R上。如下图：1#2#13当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；14再看Jump(S,y)先看一个最简单情况：S=1，y=1。从图上看出需要9步，跳过4只青蛙。1#青蛙从L－>Y；2#青蛙从L－>S；1#青蛙从Y－>S；3#青蛙从L－>Y；4#青

24、蛙从L－>R；3#青蛙从Y－>R；1#青蛙从S－>Y；2#青蛙从S－>R；1#青蛙从Y－>R；15tLSYRL4L3L2L1S2S1R4R3R2R101234567894444433332212222211111311444443333221表一16为了将过河过程描述得更清楚，我们给出了表1。表中L1L2L3L4表示左岸石柱上落在一起