《斐波纳契数列》

题目描述:斐波那契数列是一组第一位和第二位为1，从第三位开始，后一位是前两位和的一组递增数列，
像这样的：1、1、2、3、5、8、13、21、34、55。 写出第n项。

非递归思想

算法思路

和辗转相除法的非递归解法好像
辗转相除法是while循环以及中间是百分号
这里是for循环以及中间是加号（f3=f2+f1）
for循环是知道循环次数的循环，while循环是单一限制条件的循环 

代码实现

int Fibno2(int n)
{
    int num1 = 1;
    int num2 = 1;
    int tmp = 0;
    int i = 0;
    if (n < 3)
    {
        return 1;
    }
    else
    {
        for (i = 0; i>n-3; i++)
        {
            tmp = num1 + num2;
            num1 = num2;
            num2 = tmp;
        }
        return tmp;
    }
}

递归思想

算法思路

    本题的递推条件为： f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;
    递推条件的限制条件 f(1)=1,f(2)=1是递归的限制条件
    递推条件的公式是递归的主体部分
    这样来想递归是不是特别简单

    递归和非递归的区别：
    这里的非递归是从前往后推从而得到结论的，例如通过f(1)和f(2)得f(3)， 通过f(2)和f(3)得f(4)...
    递归却是从后往前，要求 f(9)，就要求f(8)和f(7),要求f(8)，就要求f(7)和f(6)
    递归的具体过程这里就不赘述了，递归是先由后往前，再由前往后得到f(9)，进行了两轮
    非递归是直接由前往后到f(9) ，进行了一轮

代码实现

int Fibon1(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    else
    {
        return Fibon1(n - 1) + Fibon1(n - 2);
    }
}
int main()
{
    int n = 0;
    int ret = 0;
    scanf("%d", &n);
    ret = Fibon1(n);
    printf("ret=%d", ret);
    return 0;
}

《台阶问题》

题目描述:有n阶台阶，每次可以跨一阶或者二阶，求总共有多少种走法?

暴力思想

算法思路

给个分析的例子：
有一个11级的台阶，一个人可走一步也可走两步，问这个人有多少种方法走完这个台阶？
解：
①只用一步走：1+1+1+1+1+1+1+1+1+1+1=11，共11步，只有C11,1=1种走法。
②用了一次两步走：1+1+1+1+1+1+1+1+1+2=11，共10步，有C10,1 =10种走法。
③用了两次两步走：1+1+1+1+1+1+1+2+2=11，共9步，有C9,2 =36种走法。
④用了三次两步走：1+1+1+1+1+2+2+2=11，共8步，有C8,3= 56种走法。
⑤用了四次两步走：1+1+1+2+2+2+2=11，共7步，有C7,4=35种走法。
⑥用了五次两步走：1+2+2+2+2+2=11，共6步，有C6,1=6种走法。
总共有1+10+36+56+35+6=144种

代码实现

递归思想

算法思路

只有一个台阶的话，只有1种走法，
2级台阶的话，可以一步一个台阶走，也可以一步2个台阶走，共有2种走法。
当台阶数大于等于3之后，可以这么分析：
如果最后一步走一个台阶，那么就是n-1个台阶的走法的种类，
如果最后一步走两个台阶，那么就是n-2个台阶的走法的种类，
所以n个台阶的走法种类就是n-1个台阶和n-2个台阶的走法的总和。
因此，这是一个递归函数。也是一个裴波那契函数。

代码实现

public int getResultByRecursion(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        return getResultByRecursion(n-1) + getResultByRecursion(n-2);
    }

算法分析

时间复杂度为2的n次方。

image

没错，这是一棵二叉树，如图所示，这里同样颜色的表示重复计算的节点，而且多数都不止重复计算了一次。我们可以对此进行优化，使用哈希表存储已经计算的节点，不再重复计算。

备忘录算法

算法思路

将计算过的保存起来

代码实现

public int getResultByMap(int n, Map<Integer,Integer> map){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int value = getResultByMap(n-1,map) + getResultByMap(n-2,map);
            map.put(n,value);
            return value;
        }
    }

算法分析

时间复杂度和空间复杂度都为O(n)。其实，我们无非使用了空间换时间，但这里很多节点不用保存，比如说，我们自底向上地来考虑这个问题，n为1和2时是显而易见的，当n=3时，可通过1和2的结果来得出，当n=4时，可通过2和3的结果来得出，我们只需要保存最近的两个结果就可以了。所以，还可以进一步优化。

动态规划

代码实现

public int getResultByDP(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
 
        int a = 1;
        int b = 2;
        int temp = 0;
 
        for (int i = 3; i < n+1 ; i++) {
            temp = a + b;
            a = b;
            b= temp;
        }
        return temp;
    }

算法分析

时间复杂度为O(n)，空间复杂度为O(l)。

《跳台阶》

楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

递归思想

代码实现

#include <iostream>
using namespace std;
int a[105];
int main(){
    a[1]=1;
    a[0]=1;
    a[2]=2;
    int n;
    while(cin>>n&&n!=0){
        for(int i=2;i<=n;i++){
            a[i]=a[i-1]+a[i-2]+a[i-3];
        }
        cout<<a[n]<<endl;
    }
    return 0;
}

《变态跳台阶》

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级，。。。，它也可以跳上n级，求该青蛙跳上一个n级的台阶总共有多少种方法？

《兔子问题》

题目描述:有一对小兔子，小兔子过Z个月长大，一对大兔子X个月生Y对小兔子，求n个月后的兔子总对数。

问题一：
有一对小兔子，小兔子过5个月长大，一对大兔子3个月生4对小兔子，求n个月后的兔子总对数。
f(n)表示n个月后的兔子总数
f(n)=n那个月原有的兔子+n那个月新生的兔子
n那个月原有的兔子是：f(n-1)
n那个月新生的兔子是：n-x那个月成熟的兔子，也就是n-x-z那个月所有的兔子，因为n-x-z那个月所有的兔子在n-x那个月的时候都成熟了

故f(n)= f(n-1)+ f(n-x-z)(y/x)；这里必须是(y/x)，这是每个月生产的。

这个表达式也适合于一个月生一对的情况；
一个月的情况可以看成成熟+不成熟，和原来的+新生的。而多个月的情况看成后一种比较好，因为看成前一种会超级麻烦。

到本题，也就是f(n)= f(n-1)+ f(n-x-z)y；也就是f(n)= f(n-1)+ f(n-8)(4/3)；

问题二：
有一对小兔子，小兔子过5个月长大，一对大兔子3个月生4对小兔子，求n个月后的大兔子总对数。
用f(n)表示大兔子，那么
f(n)= 上个月的大兔子数+这个月新长成的大兔子数
上个月的大兔子数是：f(n-1)
这个月新长成的大兔子数是：因为兔子需要5个月长大，所以应该是n-5个月那个月的新出生的兔子，
n-5个月那个月的新出生的兔子是n-5-3那个月的所有大兔子数，因为大兔子经过三个月才能下崽崽，
故f(n)=f(n-1)+f(n-5-3)*(4/3);
其实因为我把它看成每月生产(4/3)对兔子，所以不需要再减3

代码实现

#include <iostream>
using namespace std;
//前八个月的兔子总对数都是一对，initTotalRabbit[1]表示第一个月
double initTotalRabbit[9]={0,1,1,1,1,1,2.3333,3.6667,5};
double calcTotalRabbit(int n){
    if(n<=8)
        return initTotalRabbit[n];
    else
        return calcTotalRabbit(n-1)+ calcTotalRabbit(n-8)*(4.0/3);
}

//前五个月的大兔子数目为0，initBigRabbit[1]表示第一个月的大兔子数目
double initBigRabbit[9]={0,0,0,0,0,0,1,1,1};
double calcBigRabbit(int n){
    if(n<=8)
        return initBigRabbit[n];
    else
        return calcBigRabbit(n-1)+ calcBigRabbit(n-5)*(4.0/3);
}
int main(){
    for(int i=1;i<=20;i++){
        double total=calcTotalRabbit(i);
        double big=calcBigRabbit(i);
        printf("月份：%3d    兔子总对数：%6.2lf    大兔子对数：%6.2lf    小兔子对数：%6.2lf\n",i,total,big,total-big);
    }

    return 0;
}