第七饼递归犷法举例 习题讨论Cn 青蛙对河 快速排序 分书问题
1 ➢青蛙过河 ➢快速排序 ➢分书问题 ➢习题讨论 第七讲 递归算法举例 n Cm
习题: 已知Cn表示从m个元素中取n个的组合数,又知 Cn=cn,+C m 1、试画出符合上述关系的与或结合图; 2、指出哪个是直接可解结点; 3、画出C2求解结点图; 4、写出递归程序求解组合问题
2 1 1 1 1, , 1 2 5 ; 1 2 3 n m n n n m m m n m n m m n C m n C C C C C − − − = = = + = 习题： 已知 表示从 个元素中取 个的组合数，又知 、试画出符合上述关系的与或结合图； 、指出哪个是直接可解结点； 、画出 求解结点图； 4、写出递归程序求解组合问题
递归算法举例 青蛙过河
3 递 归 算 法 举 例 ——青蛙过河
讨论问题—青蛙过河 该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下 一条小溪尺寸不大,青蛙可以从左岸跳到右岸,在左岸有一石柱L, 面积只容得下一只青蛙落脚,同样右岸也有一石柱R,面积也只 容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们 将青蛙从小到大,用1,2,…,n编号。规定初始时这队青蛙只 能趴在左岸的石头L上,当然是一个落一个,小的落在大的上面。 不允许大的在小的上面。在小溪中有S个石柱,有y片荷叶,规定 溪中的柱子上允许一只青蛙落脚,如有多只同样要求一个落一个 大的在下,小的在上。对于荷叶只允许一只青蛙落脚,不允许多 只在其上。对于右岸的石柱R,与左岸的石柱L一样允许多个青 蛙落脚,但须一个落一个,小的在上,大的在下。当青蛙从左岸 的L上跳走后就不允许再跳回来;同样,从左岸L上跳至右岸R, 或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。 问在已知溪中有S根石柱和y片荷叶的情况下,最多能跳过多少只 青蛙?
4 讨论问题——青蛙过河 该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下： 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L， 面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只 容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们 将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只 能趴在左岸的石头L上，当然是一个落一个，小的落在大的上面。 不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定 溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个， 大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多 只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青 蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸 的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R， 或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。 问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只 青蛙？
这题看起来较难,但是如果我们认真分析,理出思路,就可化 难为易。 思路: 1、简化问题,探索规律。先从个别再到一般,要善于对多个 因素作分解,孤立出一个一个因素来分析,化难为易。 2.定义函数 Jump(s, y) 最多可跳过河的青蛙数 其中:S 河中柱子数 y荷叶数
5 这题看起来较难，但是如果我们认真分析，理出思路，就可化 难为易。 思路： 1、简化问题，探索规律。先从个别再到一般，要善于对多个 因素作分解，孤立出一个一个因素来分析，化难为易。 2. 定义函数 Jump(S,y) —— 最多可跳过河的青蛙数 其中： S —— 河中柱子数 y —— 荷叶数