学校课件递归算法_3

1、算法设计与分析什么是递归？什么是递归？ 当你往镜子前面一站，镜子里面就有当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗一个你的像。但你试过两面镜子一起照吗? ?如果甲、乙两面镜子相互面对面放着，你如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千往中间一站，嘿，两面镜子里都有你的千百个百个“化身化身”! !为什么会有这么奇妙的现为什么会有这么奇妙的现象呢象呢? ?原来，甲镜子里有乙镜子的像，乙原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的复，就会产生一连串的“像中像像中像”。

2、这是。这是一种递归现象。一种递归现象。什么是递归？什么是递归？ 这种日常生活中的现象这种日常生活中的现象又被称为德罗斯特效应（英又被称为德罗斯特效应（英语：语：Droste effectDroste effect）是递归）是递归的一种视觉形式。的一种视觉形式。 图中女性手持的物体中图中女性手持的物体中有一幅她本人手持同一物体有一幅她本人手持同一物体的小图片，进而小图片中还的小图片，进而小图片中还有更小的一幅她手持同一物有更小的一幅她手持同一物体的图片，依此类推。体的图片，依此类推。什么是递归？什么是递归？ 在日常生活中，递归一在日常生活中，递归一词较常用于描述以自相似方词较常用于描述以自相似方

3、法重复事物的过程。法重复事物的过程。 在算法中，递归一词用在算法中，递归一词用于表示直接或间接的调用自于表示直接或间接的调用自身的算法。身的算法。 特别的，特别的，用函数自身给用函数自身给出定义的函数被称之为递归出定义的函数被称之为递归函数。函数。 什么是递归？什么是递归？ 其实，我们在生活中经常运用递归的其实，我们在生活中经常运用递归的方式来思考问题，如参考下面这个例子：方式来思考问题，如参考下面这个例子：例例1 1：第：第5 5个人的年龄比第个人的年龄比第4 4个人的年龄大个人的年龄大2 2岁，第岁，第4 4个人的年龄比第个人的年龄比第3 3个人的年龄大个人的年龄大2 2岁，第岁，第3 3

4、个人的年龄比第个人的年龄比第2 2个人的年龄大个人的年龄大2 2岁，第岁，第2 2个人的年龄比第个人的年龄比第1 1个人的年龄大个人的年龄大2 2岁，第岁，第1 1个的年龄个的年龄1010岁。第岁。第5 5个人的年该该个人的年该该是多少呢？是多少呢？ 著名的意大利数学家斐波那契著名的意大利数学家斐波那契(Fibonacci)(Fibonacci)在他的著作在他的著作算盘书算盘书中提出了中提出了一个一个“兔子问题兔子问题”：假定小兔子一个月就可：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到对小兔子。如果年初

5、养了一对小兔子，问到年底时将有多少对兔子年底时将有多少对兔子? (? (当然得假设兔子当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖没有死亡而且严格按照上述规律长大与繁殖) ) 输入计算兔子的月份数：输入计算兔子的月份数：n n If n 3 Then c = 1 Else a = 1 If n 3 Then c = 1 Else a = 1；b = 1b = 1 i = 3 i = 3 c = a + b c = a + b a = b a = b b = c b = c i=i+1, i=i+1,如果如果inin则返回则返回 结束结束1月2月3月4月5月6月7月8月9月10月11月1

6、2月小兔111235813213455大兔1123581321345589合计1123581321345589144这个表格虽然解决了斐波那契的兔子问题这个表格虽然解决了斐波那契的兔子问题( (年年底时兔子的总数是底时兔子的总数是144144对对) )，但仔细观察一下，但仔细观察一下这个表格，你会发现兔子的数目增长得越来这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会越快，如果时间再长，只用列表的方法就会有困难。有困难。( (例如，你愿意用列表的方法求出例如，你愿意用列表的方法求出5 5年后兔子的数目吗？年后兔子的数目吗？) )我们需要研究表中的规我们需要研究表中的

7、规律，找出一般的方法，去解决这个问题。律，找出一般的方法，去解决这个问题。 仔细研究上页的表，你有些什么发现？仔细研究上页的表，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？你，你快成功了？ “ “兔子问题兔子问题”很容易列出一条递推式而很容易列出一条递推式而得到解决。假设第得到解决。假设第N N个月的兔子数目是个月的兔子数目是F(N)F(N)，我们有：我们有： 这是因为每月的大兔子数目一定等于上这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔

8、子数目一月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目定等于上月的大兔子数目( (即前一个月的兔即前一个月的兔子的数目子的数目) )。第n个Fibonacci数可递归地计算如下：int fibonacci(int n) if (n =1); fish5=fish5+5; / .1 for ( i=4; i=1; i- ) / .2 fishi+1%4 != 0 true false break; /退出 for 循环 fishi = fishi+1*5/4+1; 该图可分为三部分该图可分为三部分(1) 是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始

9、化为 1 和定义循和定义循环控制变量环控制变量 i，并初始化为，并初始化为 0。(2) 是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i的初值为的初值为 4，终值为，终值为 1，步长为，步长为 -1，该，该循环的循环体是一个分支语句，如果循环的循环体是一个分支语句，如果 fishi+1不能被不能被 4 整除，整除，则跳出则跳出 for 循环（使用循环（使用 break 语句

10、语句;）否则，从）否则，从 fishi+1 算出算出fishi。当由当由 break 语句让程序退出循环时，意味着某语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令人看到的鱼数不是整数，当然不是所求，必须令fish 5 加加 5 后再试，即重新进入直到型循环后再试，即重新进入直到型循环 do while 的循环体。的循环体。当着正常退出当着正常退出 for 循环时，一定是控制变量循环时，一定是控制变量 i 从初值从初值 4，一步一步执行到终值，一步一步执行到终值 1，每一步的鱼数均，每一步的鱼数均为整数，最后为整数，最后 i = 0，表示计算完毕，且也达到了退，表示计算

11、完毕，且也达到了退出直到型循环的条件。出直到型循环的条件。(3) 输出计算结果输出计算结果（五人合伙捕鱼）（五人合伙捕鱼） 递推算法的实现递推算法的实现 /*#include / 预编译命令预编译命令using namespace std;void main() /主函数主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人醒来后看到的鱼数整型数组，记录每人醒来后看到的鱼数 int i=0; do fish5=fish5+5; / 让让E看到的鱼数增看到的鱼数增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 )break; / 跳出跳出f

12、or循环循环elsefishi=fishi+1*5/4+1;/ 计算第计算第i人看到的鱼数人看到的鱼数 while( i=1 ); / 当当 i=1 继续做继续做do循环循环for (i=1; i=5; i+) / 输出计算结果输出计算结果cout fishi endl;system(pause);31212496199615961276输出结果为：输出结果为：递递 归归 经经 典典 题题 目目故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘个

13、一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将一只盘子的话，按照上述规则将64只盘子从一个柱子移至另只盘子从一个柱子移至另一个柱子上，所需时间约为一个柱子上，所需时间约为5800亿年。亿年。 怎样编写这种程序？思路上还是先从最简单的情况分析起，搬怎样编写这种程序？思路上还是先从最简单的情

14、况分析起，搬一搬看，慢慢理出思路。一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为 1，这时只需将该，这时只需将该盘从盘从 A 搬至搬至 C，一次完成，记为，一次完成，记为move 1 from A to C (演示演示)ABC12、在、在 A 柱上有二只盘子，柱上有二只盘子，1 为小盘，为小盘，2 为大盘。为大盘。第（第（1）步将）步将1号盘从号盘从A移至移至B，这是为了让，这是为了让 2号盘能移动；号盘能移动；第（第（2）步将）步将 2 号盘从号盘从A 移至移至 C；第（第（3）步再将）步再将 1 号盘从号盘从 B 移至移至 C；这三步记为（这三步

15、记为（演示演示）：）：ABC21move 1 from A to B;move 2 from A to C;move 3 form B to C;3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作为整体从号盘视为一个整体；先将二者作为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至C的机会。这一步记为的机会。这一步记为 move( 2, A, C, B) 意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第（第（2）步）步 将

16、将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 move 3 from A to C第（第（3）步）步 处于处于B上的作为一个整体的上的作为一个整体的2只盘子，再移至只盘子，再移至C。这一步。这一步记为记为 move( 2, B, A, C)意思是将意思是将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。所谓所谓借助借助是什么意思，等这件事做完了不言自明。是什么意思，等这件事做完了不言自明。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示：移动演示：移动3 3个盘子的

17、分解个盘子的分解move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC2134、从题目的约束条件看，大盘上可以随便摞小盘，相、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将反则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过的过程中程中 move(2, A, C, B) 实际上

18、是分解为以下三步实际上是分解为以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to B;第（第（1）.3步：步：move 1 form C to B;经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条创造了条件。同样，件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何，就要考虑如何实现将实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过的过程了。实际上程了。实际上 move( 2, B, A,

19、 C ) 也要分解为也要分解为三步：三步：第（第（3）.1步：步：move 1 form B to A;第（第（3）.2步：步：move 2 form B to C;第（第（3）.3步：步：move 1 form A to C;5、看、看 move(2, A, C, B) 是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，因为第（是不行的，因为第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条件盘创造条件从从 A 移至移至 B，然后再把，然后再把 1 盘从盘从 C 移至移至 B。看。看到这里就能明白借助到这里就能明白借助 C

20、 的含义了。因此，在的含义了。因此，在构思搬移过程的参量时，要把构思搬移过程的参量时，要把 3 个柱子都用上。个柱子都用上。6、定义搬移函数、定义搬移函数 move(n, A, B, C)，物理意义是，物理意义是将将 n 只盘子从只盘子从 A 经经 B 搬到搬到 Cmove(n, A, B, C) 分解为分解为3步步(1)move(n-1, A, C, B)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从A经经C移至移至B；(2)输出输出n：A to C，理解将，理解将n号盘从号盘从A移至移至C，是直接可，是直接可解结点；解结点；(3)Move(n-1, B, A,

21、C)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从B经经A移至移至C。这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 move(n-1, A, C, B)时又可想到，将其分解为时又可想到，将其分解为 3 步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个整体从只盘子作为一个整体从A经经B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1号盘子从号盘子从A直接移至直接移至B，即，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个整体从只盘子作为一个整体从C经经A移至移至B，move(n-2, C,

22、A, B)；#include using namespace std;/把n号圆盘从x移到y，并打印出。void Move(int n, char x, char y)cout 把 n 号圆盘从 x 移动到 y endl;/把前n个通过b从a移到cvoid Hanoi(int n, char a, char b, char c) if(n = 1)Move(1, a, c);elseHanoi(n-1, a, c, b);Move(n, a, c);Hanoi(n-1, b, a, c);int main()int n;cout n;Hanoi(n, a, b, c);cout Ok! end

23、l;system(pause);作业：作业：1 1、运动会开了、运动会开了N N天，一共发出金牌天，一共发出金牌M M枚。第一天发金枚。第一天发金牌牌1 1枚加剩下的七分之一枚，第二天发金牌枚加剩下的七分之一枚，第二天发金牌2 2枚加剩下枚加剩下的七分之一枚，第的七分之一枚，第3 3天发金牌天发金牌3 3枚加剩下的七分之一枚，枚加剩下的七分之一枚，以后每天都照此办理。到了第以后每天都照此办理。到了第N N天刚好还有金牌天刚好还有金牌N N枚，枚，到此金牌全部发完。编程求到此金牌全部发完。编程求N N和和M M。1717枚，枚，6 6天天作业：作业：2 2、国王分财产。某国王临终前给儿子们分财产

24、。他把、国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩财产分为若干份，然后给第一个儿子一份，再加上剩余财产的余财产的1/101/10；给第二个儿子两份，再加上剩余财产；给第二个儿子两份，再加上剩余财产的的1/101/10；给第；给第i i个儿子个儿子i i份，再加上剩余财产的份，再加上剩余财产的1/101/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是孰不知国王是“一碗水端平一碗水端平”的。请用程序回答，老的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？国王共有几个儿子？财产共分成了

25、多少份？作业：作业：3 3、出售金鱼。、出售金鱼。第一次卖出全部金鱼的一半加二分之一条金鱼；第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下现在还剩下1111条金鱼，在出售金鱼时不能把金鱼切开条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？或者有任何破损的。问这鱼缸里原有多少条金鱼？2222作业：作业：4 4、某路公共汽车，总共有八站，从一号站发轩时车上、某路公共汽车，总共有八站，从一号站发轩时车上已有已有n n位乘客，到了第二站先下一半乘客，再上来了六位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客