1 / 52
文档名称:

计算机语言与程序设计 递归算法举例.ppt

格式:ppt   大小:634KB   页数:52页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

计算机语言与程序设计 递归算法举例.ppt

上传人:AIOPIO 2021/6/28 文件大小:634 KB

下载得到文件列表

计算机语言与程序设计 递归算法举例.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
为了将过河过程描述得更清楚,我们给出了表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只通过

最近更新

音乐生学生实习周记 2页

题西林壁古诗词意思 3页

餐桌前的谈话初一500字 2页

高三新生如何制定学习计划 3页

高中数学学习如何适应 4页

高层办公楼工程质量监督制度 4页

高级中学行政领导值周值日制度 2页

孟子第三讲:德行 38页

黑龙江省伊春市宜春东煌外语学校2020年高三历.. 8页

高考冲刺励志口号(精选15篇) 23页

高中历史教师个人工作总结(精选7篇) 16页

饭店寒假社会实践(通用11篇) 22页

面试英语口语自我介绍(通用4篇) 3页

销售团队工作计划(精选15篇) 40页

铁路实习生自我鉴定(通用6篇) 21页

酒店保安工作计划(通用7篇) 10页

黑龙江省哈尔滨市临江中学2022年高一英语上学.. 4页

调查报告作文(精选7篇) 14页

试用期自我述职报告(精选5篇) 8页

西游记读书笔记作文(通用4篇) 4页

英语学期教学工作计划(通用7篇) 16页

股权转让协议书(通用3篇) 9页

置业顾问实习总结(通用15篇) 50页

黑龙江省哈尔滨市宾县第一中学2020-2021学年高.. 9页

黑龙江省哈尔滨市尚志中学2020年高三语文月考.. 11页

第一次月考优秀作文(精选4篇) 5页

黑龙江省哈尔滨市振华中学高一英语月考试卷含.. 4页

社区卫生服务工作计划(通用8篇) 17页

黑龙江省哈尔滨市海城中学高一化学下学期期末.. 4页

黑龙江省哈尔滨市是第二十一中学2021年高三语.. 25页