本文共 3043 字，大约阅读时间需要 10 分钟。

递归系列之入门水题一

对于递归我的感觉就是找到f(n)与前面f(n-1)等等的关系，最后拿出一个式子，这就是我理解的递归的方法，至于怎么找到关系列出式子就是难点了也就是怎么找递归方程了。 还有一点要注意的是，递归的结果一般都很大，所以尽量定义为long long形；防止溢出；

1；杭电2041超级楼梯；

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ 2-------1； 3------2； 按套路来，先找f(n)与前面f(n-1)等等的关系； 先看与f(n-1)的关系； n-1 n

根据题目可知，n-1到n只有一格那么就只有一种方法了则可以得出f(n) = 加上f(n-1)

再看与f(n-2)的关系了。 n-2 n-1 n

因为之前算过n-1的关系，则n-2就不能一步到n-1否则就是重复了。因此就只有跨2级直接到n，因此也只有一种方法因此也是f(n) = 加上f(n-2)要记得考虑重复的情况

再看看与n-3有关系没； n-3 n-2 n-1 n

n-3跨一级就是到了n-2，然而已经算过了，如果跨2级就是到了n-1还是算过了，因此可以得出n-3以后的都不用看了，肯定与n-3一样，都会到n-2，n-1，重复了。

因此可以得出结果；

f(n) = f(n-1)+f(n-2);那么代码就是很容易的事情了，第一个先摆出代码，并且这是用到打表的方法。后面的就不摆代码了； #include<stdio.h> int main() {

    int jt[1009],n,m,i;     jt[2]=1;jt[3]=2;     for(i=4;i<1000;i++)         jt[i]=jt[i-1]+jt[i-2];      scanf("%d",&n);     while(n--)     {

        scanf("%d",&m);         printf("%d\n",jt[m]);     }               return 0 ; }

2；杭电2042不容易系列之二；

由于徐老汉没钱，收费员就将他的羊拿走一半，看到老汉泪水涟涟，犹豫了一下，又还给老汉一只。巧合的是，后面每过一个收费站，都是拿走当时羊的一半，然后退还一只，等到老汉到达市场，就只剩下3只羊了。你,当代有良知的青年，能帮忙算一下老汉最初有多少只羊吗； 同样的，我们也是按照之前的思路去做，去找n与n-1，n-2，，，，等等的他们的关系。 根据题目意思拿一半又退一只。就可以列出一个等式，f(n) = (f(n-1)-1)*2。试着带一下吧。当n=1时可以求出f(1)=4; 还是推导一下这个式子怎么来的吧。 设n-1次有x只羊那么再过一次收费站就是n次收费站了还有y只羊。根据每次收费站都是拿一半又退一只。可以列出x=y/2+1;y=(x-1)*2因为这题是求最开始有好多只羊，已经知道过了几次收费站后还剩了3只，因此就可以得出递归方程. f[i]=(f[i-1]-1)*2; 这题就到这里了。

3；杭电2044一只小蜜蜂...

思路还是一样的，只是我们先模拟一下次数， 1  ~  2;~~~一种方法；1-2； 1 ~ 3~~~~2种方法；1-2-3；1-3； 1 ~ 4~~~~2种方法；1-2-3-4；1-3-4；1-2-4 根据上面的方法，和自己模拟的路径是不是可以发现有递归方程为； f(n) = f(n-1)+f(n-2); 是不是有点疑惑这是总上面开始都会这样不错，那下面开始呢？那么我们再来模拟一次； 2    3;~~~1种方法；2-3； 2  4~~~~2种方法；2-3-4；2-4； 2  5~~~~2种方法；2-3-4-5；2-4-5；2-3-5； 你模拟的路径是不是得出的结果与上面一致；则可以推导出；至于他们之间的蜂房数目有关； mf[i]=mf[i-1]+mf[i-2];

4杭电2013蟠桃记

第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？ 看到题意是不是很熟悉，感觉跟那个扣羊的题目类似，恩恩，是的一样的思路，去找到等式的规律 设n-1天还有x个，n-2天还有y个；可以得到；

y = x-(x/2 + 1)y=x/2+1; 其实递归方程已经出来了。只是我们可能还不知道了，怎么与题目联系起来，它是要求第一天的桃子数，那么我们只需要把n与n-1换一下就可以了啊。就变成了f(n)= 2*f(n-1)+2；在就是带代码就OK了；这里是要用到函数调用，所以我也摆一下代码； #include<stdio.h> int f(); int main() {

    int n;     while(scanf("%d",&n)!=EOF)         printf("%d\n",f(n));     return 0 ; } int f(int n) {

    if(n==1)         return 1;     else          return 2*f(n-1)+2; } 再仔细想想吧，第一次做这一类型都是这样的。

5；杭电2018母牛的故事

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？ 这题自我感觉就开始上了一点难度了，还记得第一次入acm就有这么一道题，超难的，现在看来，只能说还好吧，也不是那么容易。

方法还是一样的，也是去找f(n)与前面的关系，只是这次不是那么容易找的而已。

我用的方法是模拟吧；

第1年~1(4);1头

第2年~1(4)+ 1(1)2头

第3年~1(4)+ 1(2)+ 1(1);3头

第4年~1(4)+ 1(3)+ 1(2) + 1(1);4头

第5年~1(4)*2+ 1(3)+ 1(2) + 1(1)*2;6头

第6年~1(4)*3+ 1(3)+ 1(2)*2 + 1(1)*3;9头

第7年~1(4)*4+ 1(3)*2+ 1(2)*3 + 1(1)*4;13头

第8年~1(4)*6+ 1(3)*3+ 1(2)*4 + 1(1)*6;19头

是不是还是有点迷茫啊。就是这样的，这就要去思考思考了，看看发现规律没，

4年的有好多头那么该年1年的也就有好多头，而3年的就是前面2年的。而2年的就是前年1年的头数，这个规律应该容易看出来吧，然而看起来用处却不大，其实后面的推导的基础就是这个规律

。

既然要找f(n)与前面的关系那么我们就要落到实处上去啊，看一看每年增加(注意这里只是增加的)的有什么规律，是不是就是

该年4年的头数，

然而就是前1年，4年的头数加上3年的头数，

似乎还没大用，那么再分一下，变成,

前2年的4年的头数加3年的头数加2年的头数，

嘿嘿，是不是明悟了，根据最前面说的就是找规律找f(n)与前面f(n---等等)的关系，如果再分一下就可以得出来了啊，我们继续再分一下可以得出就是

前3年的4年的加3年的加2年的加1年的。

是不是很神奇就找到了f(n)与f(n-3)的关系。根据这么多的推论终于可以得出n年在n-1年的基础上增加了f(n-1)头；所以递归方程就可以写出来了，

f(n) = f(n-1)+f(n-3);是不是很6的样子。当然还有一种方法就是你可以根据上面的数据看出这个等式出来。(当然这个需要一点点运气吧)。代码就不打了继续下一题吧。

转载地址：https://blog.csdn.net/zw1996/article/details/51212831 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！