题目一：斐波那契数列

题目描述

写一个函数，输入n，求斐波那契(Fibonacci)数列的第n项。斐波那契数列定义为：

        | 0, n = 0
 f(n) = | 1, n = 1
        | f(n-1) + f(n-2), n>1

解题思路:

1. 递归会产生很多重复的计算，这里使用循环的方式。
2. 根据f(0)和f(1)计算出f(2)，再根据f(1)和f(2)计算出f3，以此类推就可以计算出f(n)了。

代码

int fibonacci(int n){
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int f1 = 0;
    int f2 = 1;
    int fn = 0;
    for (int i = 2; i <= n; i++) {
        fn = f1 + f2;
        f1 = f2;
        f2= fn;
    }
    return fn;
}

题目二：青蛙跳台阶问题

题目描述

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

解题思路:

1. 假设跳到n级台阶的跳法为f(n)， 则调到n-1级台阶的跳法为f(n-1)，跳到n-2级台阶的跳法为f(n-2)
2. 要跳到n级台阶，必须是从n-1级再跳一个台阶，或者从n-2级再跳2个台阶，因此f(n) = f(n-1)+ f(n - 2)
3. 即为斐波那契数列。