简单的递推与递归

A养兔子

Description

一对成熟的兔子每月能且只能产下一对小兔子，每次都生一公一母，每只小兔子的成熟期是一个月，而成熟后的第二个月才开始生小兔。某人领养了一对小兔子，一公一母，请问第N个月以后，他将会得到多少对兔子。

Input

测试数据包括多组，每组一行，为整数n(1≤n≤90)。 输入以0结束。

Output

对应输出第n个月有几对兔子(假设没有兔子死亡现象，而且是一夫一妻制)。

Sample Input

1
2
0

Sample Output

1
2

解题思路：这个问题实际上就是斐波那契数列的一个表现，或者说是斐波那契数列发现的一个源头。我们知道第n个月的兔子有两个来源，一个是上个月原有的兔子，一个是这个月刚出生的兔子，而刚出生的兔子是有前年的兔子成熟后生下的，也就是说刚出的兔子的数量等于前n-2年兔子的数量。所以能够得到递推方程：f(1)=1,f(2)=2,f(n)=f(n-1)+f（n-2）.
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long int
 5 using namespace std;
 6 ll f[100];
 7 int main()
 8 {
 9     ll n,ans,i,t;
10     while(scanf("%lld",&n)!=EOF)
11     {
12         if(n==0)
13         {
14             break;
15         }
16         f[1]=1;
17         f[2]=2;
18         for(i=3;i<=n;i++)
19         {
20             f[i]=f[i-1]+f[i-2];
21         }
22         printf("%lld
",f[n]);
23     }
24     return 0;
25 }


B 汉诺塔





Description




汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着n个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从A棒搬到C棒上，规定可利用中间的一根B棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。僧侣们搬得汗流满面，可惜当n很大时这辈子恐怕就很搬了 聪明的你还有计算机帮你完成，你能写一个程序帮助僧侣们完成这辈子的夙愿吗？






















Input




输入金片的个数n。这里的n<=10。






















Output




输出搬动金片的全过程。格式见样例。






















Sample Input




2










Sample Output




Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C


解题思路：题目要求是将所有圆盘最终从A号柱移动到C号柱，对于问题规模为n的情况，可将问题分解为三步：
1.将顶上的n-1个黄金圆盘从A号柱通过C号柱移动到B号柱上。
2.将A号柱子上的最后一个圆盘移动到C号柱上。
3.将B号柱上的n-1个圆盘通过A移动到C号柱上。




 1 #include<cstdio>
 2 #include<cstring>
 3 void Move(int n,char a,char b)
 4 {
 5     printf("Move disk %d from %c to %c
",n,a,b);
 6 }
 7 void Han(int n,char A,char B,char C)
 8 {
 9     if(n==1)
10     {
11         Move(n,A,C);///最后一个从A移动到C
12     }
13     else
14     {
15         Han(n-1,A,C,B);///将A柱顶上的n-1个圆盘通过C柱移动到B柱上
16         Move(n,A,C);
17         Han(n-1,B,A,C);///将B柱上的n-1个圆盘移动到C柱上
18     }
19 }
20 
21 int main()
22 {
23     int n;
24     scanf("%d",&n);
25     Han(n,'A','B','C');
26     return 0;
27 }





C 蟠桃记




Description




孙悟空在大闹蟠桃园的时候，第一天吃掉了所有桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。这下可把神仙们心疼坏了，请帮忙计算一下，第一天开始吃的时候桃子一共有多少个桃子。








Input




输入数据有多组，每组占一行，包含一个正整数n（1≤n≤30），表示只剩下一个桃子的时候是在第n天发生的。 输入以0结束。








Output




对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。








Sample Input




2
4
0








Sample Output




4
22

解题思路：设第n天有x个桃子，则要吃掉x/2+1个桃子，则第n+1天还剩x/2-1个桃子了，所以f(n)=(f(n-1)+1)*2，已经知道第n天还剩一个，那么倒推就可以了。




 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int main()
 6 {
 7     int n,ans,i;
 8     ans=1;
 9     while(scanf("%d",&n)!=EOF)
10     {
11         if(n==0)
12         {
13             break;
14         }
15         ans=1;
16         for(i=n-1;i>0;i--)
17         {
18             ans=(ans+1)*2;
19         }
20         printf("%d
",ans);
21     }
22     return 0;
23 }












 D骨牌铺方格




Description




在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图： 








Input




输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。








Output




对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。








Sample Input




1
3
2








Sample Output




1
3
2


解题思路：最后一个木块只有两种排放方式，1）竖排，那么前n-1格有f(n-1)种方案；2）横排，前n-2格有f(n-2)种方案；
由此可得：f(n)=f(n-1)+f(n-2),即为Fibonacci数。




#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long int
using namespace std;
ll f[100];
void fib()
{
    f[1]=1;
    f[2]=2;
    int i;
    for(i=3;i<=60;i++)
    {
        f[i]=f[i-1]+f[i-2];
    }
    return ;
}
int main()
{
    ll n;
    fib();
    while(scanf("%lld",&n)!=EOF)
    {
        printf("%lld
",f[n]);
    }
    return 0;
}





这里再给出一种使用记忆化递归的方法来求斐波那契数列，开一个数组来保存信息。




import java.util.*;
public class Main {
    public static long[] dp = new long [100];
    public static long fib(int n){
        
        if(n==0||n==1)//递归边界
        {
         return 1;
        }
        if(dp[n]==0)//如果没有计算过，就计算保存一下
        {
            dp[n]=fib(n-1)+fib(n-2);
        }
        /*
         * 如果计算存在过，就不用计算了
         */
        return dp[n];
    }
    public static void main(String args[]) {
       Scanner cin = new Scanner(System.in);
       while(cin.hasNext())
       {
           int n = cin.nextInt();
           System.out.println(fib(n));
       }
    }
    
}




E 不容易系列之一





Description




 大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！ 
做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。 
 
话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。
 
 

 
不幸的是，这种小概率事件又发生了，而且就在我们身边： 
 
事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！ 
 

 
现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？ 




    













Input







  输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=20），n表示8006的网友的人数。 




    













Output







  对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。 




    





















Sample Input






2
3 










 


















Sample Output




1
2 











解题思路：错位排序！我之前写过的https://www.cnblogs.com/wkfvawl/p/8998468.html


错位排列：


第一步，错排第一号元素（将第一号元素排在k位置），有n-1种方法。


第二步，错排其余n-1个元素。紧接第一步的结果，若第一号元素落在第k个位置，第二步就先把K排好


1、 k 号元素排在第1个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2) 种方法；
2、
 k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k 
个位置(也就是说本来准备放到k位置为元素，可以放到1位置中),于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 
1) 种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。 
根据乘法原理， n 个不同元素的错排种数 



错排公式 f(1)=0,f(2)=1;f(n)=(n-1)(f(n-1)+f(n-2))






 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long int
 5 using namespace std;
 6 ll cuopai(ll n)
 7 {
 8     if(n==1)
 9     {
10         return 0;
11     }
12     else if(n==2)
13     {
14         return 1;
15     }
16     else
17     {
18         return (n-1)*(cuopai(n-1)+cuopai(n-2));
19     }
20 }
21 int main()
22 {
23     ll n,ans;
24     while(scanf("%lld",&n)!=EOF)
25     {
26         ans=cuopai(n);
27         printf("%lld
",ans);
28     }
29     return 0;
30 }





递推写法：




1 a[1]=0;
2 a[2]=1;
3 for(int i=3; i<=22; i++)
4 {
5     a[i]=(i-1)*(a[i-1]+a[i-2]);
6 }





F 超级楼梯




Description




有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？








Input




输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。








Output




对于每个测试实例，请输出不同走法的数量


 








Sample Input






2


2


3




 






Sample Output




1


2


 


解题思路：这道题其实和骨牌排方格是一道题，也是斐波那契数列的一个应用。最后一步上楼梯有两种方式，一种是走一级台阶，那么前有f(n-1)种方式，


另一种是走两级台阶，那么前面有f(n-2)种方式，按照加法法则f(n)=f(n-1)+f(n-2)。






 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==1)
 8     {
 9         return 1;
10     }
11     else if(n==2)
12     {
13         return 2;
14     }
15     else
16     {
17         return f(n-1)+f(n-2);
18     }
19 }
20 int main()
21 {
22     int n,ans,i,t;
23     scanf("%d",&t);
24     while(t--)
25     {
26         ans=0;
27         scanf("%d",&n);
28         ans=f(n-1);
29         printf("%d
",ans);
30     }
31     return 0;
32 }







 




 











        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/wkfvawl/p/9917780.html