第七饼递归犷法举例 习题讨论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 —— 荷叶数
3.先看简单情况,河中无柱子:S=0, Jump(o,y) 当y=1时,Jump(0,1)=2; 说明:河中有一片荷叶,可以过两只青蛙,起始时L上有两 只青蛙,1#在2#上面。 第一步:1#跳到荷叶上; 第二步:2#从L直接跳至R上; 第三步:1#再从荷叶跳至R上。 如下图: 2#) 左岸 右岸
6 3. 先看简单情况，河中无柱子：S=0， Jump(0,y) 当y=1时，Jump(0,1)=2； 说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两 只青蛙，1#在2#上面。 第一步：1# 跳到荷叶上； 第二步：2# 从L直接跳至R上； 第三步：1# 再从荷叶跳至R上。 如下图： 2# 1# 2 1 3 L 左岸 R 右岸
当y=2时, Jump(0,2)=3; 说明:河中有两片荷叶时,可以过3只青蛙。起始时: l#,2#,3#3只青蛙落在L上 第一步:1#从L跳至叶1上, 第二步:2#从L跳至叶2上, 第三步:3#从L直接跳至R上, 第四步:2#从叶2跳至R上, 第五步:1#从叶1跳至R上, 叶 采用归纳法:Jump(,y)=y+1; 意思是:在河中没有石柱的情 (叶2 况下,过河的青蛙数仅取决于荷 叶数,数目是荷叶数+1
7 当y=2时， Jump(0,2)=3； 说明：河中有两片荷叶时，可以过3只青蛙。起始时： 1#，2#，3# 3只青蛙落在L上， 第一步：1# 从L跳至叶 1上， 第二步：2# 从L跳至叶 2上， 第三步：3# 从L直接跳至R上， 第四步：2# 从叶2跳至R上， 第五步：1# 从叶1跳至R上， 叶1 3 1 5 L R 叶2 2 4 采用归纳法：Jump(0,y)=y+1； 意思是：在河中没有石柱的情 况下，过河的青蛙数仅取决于荷 叶数，数目是荷叶数+1
再看Jump(s,y) 先看一个最简单情况:S=1,y=1 从图上看出需要9步,跳过4只青蛙。 ④4)3# 1#青蛙从L 3# 2#青蛙从L 1#青蛙从Y一>S; 1# 9 3#青蛙从L R Y 1# 4#青蛙从L一>R; 1# 3#青蛙从Y R 2# S 2# 1#青蛙从S 2#青蛙从S R 1#青蛙从Y一>R; 4#
8 再看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 ； SY 5 4 6 L R 12 3 7 8 1# 9 2# 4# 3# 3# 1# 2# 1# 1#
表 一 L Y R L4 L3 L2 L1 S2 SI R4R3R2RI 1234 4444 3333 222 22 789 44444 3333
9 t L S Y R L4 L3 L2 L1 S2 S1 R4 R3 R2 R1 0 1 2 3 4 5 6 7 8 9 4 4 4 4 4 3 3 3 3 2 2 1 2 2 2 2 2 1 1 1 1 1 3 1 1 4 4 4 4 4 3 3 3 3 2 2 1 表一
为了将过河过程描述得更清楚,我们给出了表1。表中L1L2 L3L4表示左岸石柱上落在一起的青蛙的高度位置。L1在 最上面,L4在最下面的位置。引入这个信息就可比较容易 地看出对青蛙占位的约束条件。同理RR2R3R4也是如 此。对水中石柱S,也分成两个高度位置s1S2。对荷叶Y无 须分层,因为它只允许一只青蛙落在其上。t=0为初始时刻 青蛙从小到大落在石柱L上。t1为第一步: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系统。前者二只 青蛙号大;后者二只青蛙号小。先跳号大的,再跳号小的。 从第五步到第九步可以看出的确是这么做的。 10
10 为了将过河过程描述得更清楚，我们给出了表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系统。前者二只 青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。 从第五步到第九步可以看出的确是这么做的