斐波那契数列

1. 什么是斐波那契数列？

0，1，1，2，3，5......；数学函数：f(n) = f(n-1) + f(n-2)；

2. 非递归实现

int fibonacci(int n) {
    int result =0;
    int a =1;
    int b =1;

    if(n ==0) {
        return result;
    }
    if(n ==1||n ==2) {
        result = a;
        return result;
    }

    for(int i =3; i < n; i++) {
        result = a + b;
        a = b;
        b = result;
    }

    return result;
}

3. 递归实现

int recursiveFibonacci(int n) {
    if(n ==0) {
        return 0;
    }

    if(n ==1||n ==2) {
        return 1;
    }

    return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}

4. 其他斐波那契数列问题

• 跳台阶问题：

  • 一只青蛙一次可以跳上1级台阶，也可以跳上2级

  求该青蛙跳上一个n级的台阶总共有多少种跳法。第n级台阶跳法等于第n-1级跳1步跟第n-2级跳2步，所以还是斐波那契数列f(n)=f(n-1)+f(n-2)。

• 变态跳台阶问题：

  • 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  青蛙只跳1或2可以得出是一个斐波那契问题，即a[n]=a[n-1]+a[n-2],那么能跳1,2,3个台阶时a[n]=a[n-1]+a[n-2]+a[n-3],......依次类推，能推出a[n]=a[n-1]+a[n-2]+......+a[1];然后a[n-1]=a[n-2]+a[n-3]+......+a[1];那么两个公式相减a[n]-a[n-1]=a[n-1];所以a[n]=2a[n-1]。

int jumpFloorII(int number) {
    if (number < 2)
        return 1;
    int a = 1;
    int r = 0;
    for (int i = 2; i <= number; i++) {
        r = 2*a;
        a = r;
    }
    return r;
}