斐波那契数列.md

题目一

题目描述

求斐波那契数列数列的第n项。

写入一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

f(n) = 0; n=0
f(n) = 1; n=1
f(n) = f(n-1) + f(n-2); n>1

测试用例

• 功能测试（如输入3、5、10等）
• 边界值测试（如输入0、1、2）
• 性能测试（输入较大的数值，如40、50、100等）

题目考点

• 考察应聘者对递归、循环的理解及编码能力
• 考察队时间复杂度的分析能力
• 如果结合实际问题，可能还考察数学建模能力

解题思路

最简单的利用递归

大家都能想到，但是没有考虑时间复杂度，垃圾，如自己解题。

改进的循环

由于上面的方面很慢，是因为重复的计算太多（例如，计算 f(10) 需要计算 f(9) 和 f(8)，计算 f(9) 需要计算 f(8) 和 f(7)，可以看到 f(8) 被重复计算了。），所以我们要避免重复计算，我们可以吧已经计算得到的中间项保存起来，在下次需要计算的时候先查找一下，这样就可以避免重复计算了。

自己解题

/**
 * 最简单的递归
 * 没有考虑时间复杂度
 * @Author rex
 * 2018/7/15
 */
public class Solution {
    // 很垃圾
    public int Fibonacci(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

参考解题

/**
 * 聪明的循环
 * 考虑时间复杂度
 * @Author rex
 * 2018/7/15
 */
public class Solution1 {
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int pre1 = 0;
        int pre2 = 1;
        int fib = 0;
        for (int i = 2; i <=n; i++) {
            fib = pre1 + pre2;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }

}

题目二

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题目考点

考察数学建模能力，发现实质是斐波那契数列。

解题思路

与斐波那契数列相同，但是还是需要分析一下：

先分析最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法，分为每次跳1级，和一次跳两级。

再讨论一般情况，我们把n级台阶时的跳法看成n的函数，记为f(n)。当 n>2 时，第一次跳的时候就有两种不同的选择：一是第一次跳1级，此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目，即为 f(n-1) ，二是第一次跳2级，此时跳法数目等于后面剩下的 n-2 级台阶的跳法数目，即为 f(n-2) 。因此，n级台阶的不同跳法的总数f(n) = f(n-1) + f(n-2)。

我们马上就可以看出这就是斐波那契数列了。

自己解题

/**
 * 青蛙台阶问题
 * @Author rex
 * 2018/7/15
 */
public class FrogSolution {

    /**
     * 采用斐波那契解法
     * @param target
     * @return
     */
    public int JumpFloor(int target) {
        if (target < 3) {
            return target;
        }
        int pre1 = 1;
        int pre2 = 2;
        int fib = 0;
        for (int i = 3; i <= target; i++) {
            fib = pre1 + pre2;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }
}

参考解题

如自己解题。

补充

通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，则应聘者可以采用递归的方法编程，但是我们还是应该以时间复杂度为首要考虑。