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只通过

最近更新

辽宁省盘锦市第一完全中学2020年高二政治期末.. 5页

辽宁省营口市大石桥建第一中学2020年高三数学.. 9页

辽宁省营口市盖州团山中学2022年高一物理联考.. 10页

辽宁省营口市第三十中学2021年高三化学模拟试.. 12页

超临界CO?萃取装置行业市场调研分析报告 52页

辽宁省葫芦岛市建昌第二中学高一物理模拟试题.. 6页

辽宁省葫芦岛市建昌第二中学高一物理月考试题.. 5页

辽宁省辽阳市朝鲜族中学2022年高三数学理期末.. 5页

辽宁省辽阳市县柳壕镇中学2021-2022学年高二英.. 3页

辽宁省辽阳市灯塔鸡冠山乡中学2021年高一英语.. 4页

一年级下册音乐教案 34页

辽宁省铁岭市修丝顿十美中学2021-2022学年高三.. 12页

二零二五年度能源行业股份转让合同模板 3页

辽宁省铁岭市无极限职业中学2022年高三化学期.. 13页

辽宁省锦州市北镇鲍家乡中学2021年高三数学理.. 6页

二零二五年度航空航天设备安装与验收协议 3页

环境监测技术服务合同范本汇编 3页

辽宁省阜新市第十六中学2021年高三数学理联考.. 16页

二零二五年度航空货运智能物流系统采购合同 4页

二零二五年度航空货运货运代理资质认证合同 3页

辽宁省鞍山市关门山中学2020-2021学年高一数学.. 5页

辽宁省鞍山市冶金职业中学2020-2021学年高三化.. 6页

车辆驾驶考试技巧授权代理委托书 17页

销售工作总结报告(精选15篇) 35页

辽宁省鞍山市新甸职业中学高二物理期末试卷含.. 9页

二零二五年度节日庆典活动策划合同,共享欢乐.. 3页

运动会日记(通用5篇) 9页

身体不适的辞职报告(通用7篇) 8页

二零二五年度花卉种植基地土壤改良与施肥合同.. 3页

语文课前演讲稿【精】(通用15篇) 17页