00:00
各位同学,我们来看几个关于递归的课堂练习题,第一个题我们来看一下,叫求斐波那契数。那首先我们解释一下什么叫斐波那系数。斐波拉系数呢?它要求我们用递归的方式来求解,斐波拉系数指的是这个第一个数是一,第二个数也是一,从第三个数开始呢?对,它是前面两个数的和,比如说第三个数是二一加一。第四个数是一加二。五是怎么来的呢?是前面两个数的和。八呢又是前面两个数的和,13又是前面两个数的和,也就是说。从第三个数开始,它是前面两个数的和,那么这个就是斐波那契数列。现在的要求是给了你一个整数N。求出它的斐波那系数是多少?比如说我给了一个N等于五。就要返回。
01:00
第五个就说这个斐波拉契数列的第五个是哪一个呢?就应该是五,如果我给的是六,他应该返回的就是。就是八,诶看看123456,对第六六就应该对于18以此类推,那这样子哈,我们用递归来完成,那么我们拿到这个题呢,我们就来开始分析。各位同学,打开这个代码,我们来玩一把。那现在呢,我们是做的非关于递归的相关练习题,我写个名叫recurs exer c就RS一个。好,我们来走一走吧,看看这道题应该怎么做,跟上老师思路。首先呢,我们include标准的输入输出,然后VO的主函数。来,走起来。先把需求拿过来。
02:00
那这个题其实呢,我们关键是要分析它的特点是什么,我们来做一个简单的分析。第一点呢,哎,第一点就是如果N等于一。N等于20。返回几呢?返回就是一,大家看到这个特点了没有?是不是我们如果,呃,第一个斐波拉奇数列的第一个数是一,第二个数也是一,那么从,从N等于三开始。N等于三开始,那么对应的怎么样?斐波那契数?是多少呢?就应该是。就应该是它的前面,就应该是前面两个数的和,是这意思吧,好,同学们,那现在老师就可以写代码了,根据这个分析,我来写代码。那怎么写呢?咱们返回一个int,所以说我叫斐波那简写啊斐波那这样写,我接收一个N。
03:06
接收一个N,我就开始玩了,如果N你等于是一,或者N等于二,是不是在这种情况下呢?我们认为你的结果就是一看懂了没有。否则,如果你不是一或者二,那就是三以上了,假定我们这个N值就是正数哈,那应该返回什么呢?斐波那。N减一,这个N减一是不是它的前面这个数,再加上斐波那。N减二是不是它前面的第二个数就写完了代码。这就写完了,那是不是这样,可不可以用呢?我们来验一下,比如说我们要得到13,就是第几个数啊,1234567,好,第七个数我们搜一下。
04:00
比如说我写个number或者res等于斐波,那然后呢给一个七,那理论上re就应该等于13,我们看看对不对,PF我们输出来。RS等于白跑低,为了好看呢,换一行。那这个时候我们拿到二一,我们来get下一下各位同学,我们运行一下哈,把前面这个已经注销了,我们运行一下。我们运行看看是不是等于13,如果等于13就正确,否则就是有问题的。运起来,我发现就是13答案正确。完了代码就写完了。第一个题就完成了第二个题。第二个题呢,更加的简单,它呢也要求我们用这个什么呀,也要求我们用递归来完成,那现在呢,看第二个题的需求。好的,那先把这个题先注销好不好,先把这个注销。
05:00
第二个题呢,说求函数对应的值,它已经把这个公式给我们了,如果呃,传的是一返回三,否则的话是二乘以FN减一加一,其实这个很简单,就公式就应给我了,分析。分析,因为因为该题的该题的公式已经已经给出,所以直接套用,所以直接使用即可,好同学们,那我现在开始写这个函数了啊,它的函数你看这地方写的很清楚吗?就这么一个条件,那既然是这个条件,那没什么可说的,直接玩一下就行了,Int f,我接收一个in n。对,那怎么返回呢?如果N等于一。如果N等于一,它的结果就是三,看到没有。是不是如果你给我传一个一,我就返回3A,如果不是这个条件怎么办呢?把这个公式套用一下就可以了。
06:03
往这儿一扔,完事了。是不是就应该二乘以FN减一加一啊,代码写完。好,那么我们可以测一下,我们可以测一下还是前面的这样一个方式RS。二等于F,我们传一个30。对,Print f print f,我们把这个RS打出来。对不对,222,对对对,不是RS是R2,同样我们给一个get。好了,朋友们,我们运行一下应该也不会有什么错,是吧?很简单一道题。我们看看这个结果是三,那就不对,三好像不太对,我们看一下为什么。三应该不是正确的。30啊。30的话。我们看一下F。这个地方传进去30 30的话是二乘以。
07:03
这个应该不不会等于哦,最后忘了写了一个return语句,不好意思。是不是忘了一个return啊?那肯定就错了,来,朋友们再跑起来。好,这样应该就对了。是不是这么大一个数啊,正确的啊,同学们可以验验一下,我就不去验了。第二个题咱们就评价完毕,我们再来看第三个好玩的题,第三个题呢比较好玩,我们来一起做一做。第三个题是一个关于猴子吃桃子的问题,我们来分析和解答。来看一下这个题的要求吧。来看一下这个题的要求。走到这里来。这道题的要求呢,是这样玩的,他说啊,有一个猴子吃桃子啊,第一天呢,他吃了,吃了其中的一半。并且再多吃了一个,就吃完一半,过后呢,再多吃以后以后每这个,每天这个猴子都吃其中的一半,再多吃一个。
08:01
最后到第十天的时候呢,想吃的时候还没有吃,只剩下一个桃子了,问最初也是第一天的时候,有多少个桃子?这个题大家听懂了没有?好,现在呢,我们作为用递归来完成最关键的地方,叫做一个分析。好,我来做分析,大家看是不是我们可以这样理解,对,十。D等于十的时候,有几个桃,有一个桃,这个能理解吗?就是第十天的时候,有一个有一个桃子。没问题吧,那我问大家一个问题,这等于九的时候有几个桃子呢?这个大家能推出来吗?就对D等于九的时候,是有几个套子,是不是就应该是对十。带石的这个桃子。干什么呀?是不是在这个基础上加一个一,就是它的它的对对九应该是对十这个桃子的数量加一再乘以二啊。
09:01
这个大家能看看出来吗?因为你是你是不是吃完一半过后再多吃一个就第十天了,也就是说这个大家应该推出来是几呢?就应该是一加一刮起来乘以二。你看一下是不是这个道理。乘以二等于几呢?等于四,你看,假设第四天第九天有四个桃子,我吃完一半,是不是吃了两个,还剩两个,再多吃一个,是不是第四天只有一个桃子了?那这样子是不是就可以以此类推了?问大家,D等于八的时候有几个桃子?有几个桃子能推推出来吗?如果N等于D等于八的话,就应该是对九的这个桃子加一再乘以四,那就应该是四。增加,那这个就是五,这就等于十了。看出来了吗?好,同学们,后面我就不写了,大家看出规律来了没有,也就是说他第几天的桃子呢?是由他后面这天桃子加一乘以二得到的,那代码就基本上写出来了,那开始写的这段代码了,来,把这段分析拿到上面去,我们来一起完成。
10:05
这是老师的分析,那现在我们来写这段代码好不好?跟着老师思路,Int pitch。Picture就是逃的意思,那么我接收这个day。我接受这个day,如果这个D是等于第十天。对不对,那就应该返回一个套子,看出来没有A,如果不是第十天的话呢,应该怎么返回呢?就应该这样返回pitch。N。加一是不是它的,诶不是对,加一就是它的下一天加一。然后再加一刮起来乘以二能理解吗?这个大家应该能绕过来吧,乘以二完事了。写完了,为什么?因为我刚讲过了嘛,如果你求的这一天,其实是它的下一天,加一乘二已经分析过来了,就是上面已经写的很清晰了。你看求第八天,其实是第九天加一乘以二,不第九天就是D加一吗?写完了,那现在呢,我们要求第一天桃子就很快出来了,写一个,比如说PH number等于什么呢?OK,等于PH的函数写一就完事了,当然就出来了,我们打印一下。
11:19
输出。写出来第一天,第一天有这么多个桃子。写完了,那这么多桃子呢,就PE number写完了,最后我们定一下这空起来,各位朋友看第一天到底有多少个桃子走起来。走起来,我们看第一件桃子呢,应该有,呃,不少,1534个桃子。多不多?这个题做完了过后,我有一个疑惑,就是这个桃子啊,这个桃子有这么多,那就意味着这个猴子第一天就吃吃了700多个桃子,很恐怖吧,哼,这个我们不去管它,我们认为这个这个猴子很厉害,是一个,是一个非常能吃的一个猿猴啊巨呃,金刚啊金刚,他可以吃这么多桃子。
12:05
那这个呢,我们就完成到这里。大会就行了,那各位同学到此呢,关于函数递归我们就讲这么多,尤其是对三个题的讲解,大家一定要认真的去体会好,各位我把递归的内容呢给大家梳理一下,我们看看怎么讲的。跑起来。我们梳理一下讲的递归的内容,函数递归。在这里讲的对不对?递归很重要啊,这个知识点其实非常重要的,而且呢是一个难点,首先呢,我们先给各位同学讲了递归的基本概念,何为递归啊?何为递归?所谓递归呢?就是一个函数在函数体内调用了自己。很简单一个概念,然后呢,我们就做了一个递归的快速入门案例,那么快速入门案例,呃,其实就是这两个题了。就是这两个题。好,就是这,哎,就是这两个题,我把这两个题拿过来,那么这两个题呢,我们的具体的分析看一下,通过通过两个题。
13:09
两个。两个题。分析了分析递归,递归执行的一个流程和机制是这样子吧,这个是特别重要的,同学们这个不要小看它啊,实际上是非常重要的,那具体来说我们怎么分析的呢?是不是这样分析的呀。这是我们的A,不是递归,是在这分析的。是不是这分析的这两道题,好,我把这我把这两个呢,给大家拿过来。没有问题吧,应该应该很好理解的啊把这个。流程图拿过来,拿过来过后呢,基本上这个就搞定,下面呢,我们为了加深大家对递归的一个理解呢,我们说了一下递归的时候的需要的需要注意的事项有四点。需要注意事项有四点,其实这四点呢,呃,准确的讲就是对前面这一个流程和机制的总结,是不是也不难,就是大家知道啊是怎么回事就OK了。
14:10
紧接着我们要讲什么呀?为了加强对递归的理解,是不是我们做了三个题,是不是三个题来梳理到这里,哪三个题呢?我们看一下第一个题。我们讲的是用递归来求解非波拉器,第二个题我们用递归来求函数值,还有第三个题是一个猴子吃桃子的问题。这个是反向推的,就是我们知道最后一天反推第一天是这样子吧,同学们好,这个大家有个印象,好,我把他的答案给各位朋友板书到这里来。那么第一个题的答案呢?第二个题的答案,我们梳理到第一个题的答案。干脆这样,咱们就放在一起算了吧,好不好,因为这这个这一块呢,其实也并不是很难的,我把它打开就行了。这地方打开。
15:00
这一门是不是也打开?是不是上面的函数的定义呢?都都在上面,这是第一个,第二个,这好整体我就翻过来好不好,这就大家到时间去看就行了,好,这我写一句话,就是三个题的答案,前面三个。题题的解答如下。解答。一下我放到这里。调查老师思路好,那你到时间呢,呃,拿把这个代码拿出来,因为我写的很清晰嘛,这边是T2这边是。这边是题一,都有标题,都有一个说明的,应该不会看错,这是题一,写到这,这是题二没问题,第三个是题三,就是猴子吃桃子的分析和代码的完成,各位同学,那关于我们函数的递归就给各位朋友介绍到这里,大家一定要认真的体会好,这讲就说到这儿。
我来说两句