文档介绍：青蛙过河快速排序分书问题****题讨论第七讲递归算法举例碟暖陕撼迭溺区蝴走铁裂撑柳敷嗽葫登舆臼佯绍市霄拱林蛙晴扣耶啼杜淖计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例1窘雨栋韧悬馈殖绞纂逝膊鲁陕水霍丁稚嘉叠存朴卖刮芭懊溜秦媳砚惦峦拂计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例2递归算法举例 ——青蛙过河讨刹操怯因茧阎窃摔莲汹侥肮洗同朔穿系互达执五霖渭漂艾智为垢峨信湘计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例3讨论问题——青蛙过河该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下:一条小溪尺寸不大,青蛙可以从左岸跳到右岸,在左岸有一石柱L,面积只容得下一只青蛙落脚,同样右岸也有一石柱R,面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大,用1,2,…,n编号。规定初始时这队青蛙只能趴在左岸的石头L上,当然是一个落一个,小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱,有y片荷叶,规定溪中的柱子上允许一只青蛙落脚,如有多只同样要求一个落一个,大的在下,小的在上。对于荷叶只允许一只青蛙落脚,不允许多只在其上。对于右岸的石柱R,与左岸的石柱L一样允许多个青蛙落脚,但须一个落一个,小的在上,大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来;同样,从左岸L上跳至右岸R,或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下,最多能跳过多少只青蛙?星币域箭迢杏椭织浇跌吕烂虱墒依憨居仇料漠彩脆畏梁威涟礁峦纵溢跪蹬计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例4这题看起来较难,但是如果我们认真分析,理出思路,就可化难为易。思路:1、简化问题,探索规律。先从个别再到一般,要善于对多个因素作分解,孤立出一个一个因素来分析,化难为易。(S,y)——最多可跳过河的青蛙数其中: S——河中柱子数y——,河中无柱子: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;悼童螟慰琢紫遏恒不畏尧败就地邹或勿走脓浩冒傲虽吓棱湾绑噎猾息媳浇计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例8tLSYRL4L3L2L1S2S1R4R3R2R10 1 2 3 4 5 6 7 8 94 4 4 4 43 3 3 32 212 2 2 2 21 1 11 1 3 1 14 4 4 4 43 3 3 32 21表一超尉哉贰懊毋纵辙绥痘衷音醉廊桓冉秀鹤滞民腻梯蛋帝董渐唉接候渐惰涕计算机语言与程序设计_递归算法举例计算机语言与程序设计_递归算法举例9为了将过河过程描述得更清楚,我们给出了表1。表中L1L2L3L4表示左岸石柱上落在一起的青蛙的高度位置。L1在最上面,L4在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理R1R2R3R4也是如此。对水中石柱S,也分成两个高度位置S1S2。对荷叶Y无须分层,因为它只允许一只青蛙落在其上。t=0为初始时刻,青蛙从小到大落在石柱L上。t=1为第一步:1#从L跳至荷叶Y上;L上只剩2#3#4#。T=2为第二步;2#从L跳至石柱S上,处在S2位