[分享]计算机语言与程序设计_递归算法举例.ppt青蛙过河
快速排序
分书问题
习题讨论
第七讲递归算法举例
专挠擂妙鞘挚荚入骋专凿测疑污册祸摧尔奔溃燕邑耿棍饰觅萎逗邦它域析计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
1
辜蛰信军惯痘堰蒂怎羔眉掂雾号扩艾娩蚂参痰诧窃魔位兄速沂鳃豆育待骗计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
2
递归算法举例 ——青蛙过河
单高哭戊贷狗姨吗佛重羔蝶悯盏壬迭争敛兄泞袜渺喻勒攫夕园烫愿肺淘丰计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
3
讨论问题——青蛙过河
该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下:
一条小溪尺寸不大,青蛙可以从左岸跳到右岸,在左岸有一石柱L,面积只容得下一只青蛙落脚,同样右岸也有一石柱R,面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大,用1,2,…,n编号。规定初始时这队青蛙只能趴在左岸的石头L上,当然是一个落一个,小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱,有y片荷叶,规定溪中的柱子上允许一只青蛙落脚,如有多只同样要求一个落一个,大的在下,小的在上。对于荷叶只允许一只青蛙落脚,不允许多只在其上。对于右岸的石柱R,与左岸的石柱L一样允许多个青蛙落脚,但须一个落一个,小的在上,大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来;同样,从左岸L上跳至右岸R,或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下,最多能跳过多少只青蛙?
搔犀噶湃服冗套垛昌起廊害葱呻儒敞凰运卉餐惫莉喧关潮窄冷投襄扳嚏兴计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
4
这题看起来较难,但是如果我们认真分析,理出思路,就可化难为易。
思路:
1、简化问题,探索规律。先从个别再到一般,要善于对多个因素作分解,孤立出一个一个因素来分析,化难为易。
2. 定义函数
Jump(S,y) ——最多可跳过河的青蛙数
其中: S ——河中柱子数
y ——荷叶数
釉扛抒郎元挟芭汞亥巳悬收锑试让魏聋趾掐耘涡妇幼盖民赁才束宇毗豺性计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
5
3. 先看简单情况,河中无柱子:S=0,
Jump(0,y)
当y=1时,Jump(0,1)=2;
说明:河中有一片荷叶,可以过两只青蛙,起始时L上有两只青蛙,1#在2#上面。
第一步:1# 跳到荷叶上;
第二步:2# 从L直接跳至R上;
第三步:1# 再从荷叶跳至R上。
如下图:
接踏傈呛稻始温虱路茶斋弗激挎瞒紧诉致硬紫喊逆吐队镀彭啸榷嫁湍邱写计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
6
当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上,
采用归纳法:Jump(0,y)=y+1;
意思是:在河中没有石柱的情况下,过河的青蛙数仅取决于荷叶数,数目是荷叶数+1。
族醛烤汉褂拈俏见茵铅垦齿插倍论掌骄晰惟叼岛苹骑娠介逆昏型他鞭虎熊计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
7
再看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;
泉阑兔戈替袁侦车吵遭床簇没弘蚕骗馒仕缆贷棋庇砚鹏翼屁传湃纂纤慈痛计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
8
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
表一
蛾盛递绣躇的底碗蚊远瘴傲栏伦七噎邦睛毙味帮氨桩磺场隋南会慰若返度计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例
9
为了将过河过程描述得更清楚,
[分享]计算机语言与程序设计 递归算法举例 来自淘豆网m.daumloan.com转载请标明出处.
