斐波那契数列 -- java

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

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

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

最简单的利用递归
大家都能想到，但是没有考虑时间复杂度

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

public class Fibonacci {
    // 递归方式
    public static long fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

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

    // 测试
    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
}

public class Fibonacci {
    // 循环方式
    public static long fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        long pre1 = 1L;
        long pre2 = 0L;
        long fib = 0L;
        for (int i = 2; i <= n; i++) {
            fib = pre1 + pre2;
            pre2 = pre1;
            pre1 = fib;
        }
        return fib;
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
}

一只青蛙一次可以跳上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)。

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

首先根据f(1)和f(2)算出f(3)，再根据f(2)和f(3)算出f(4)……以此类推就可以算出第n项了。

public class Fibonacci {
    // 循环方式
    public static long fibonacci(int n) {
        if (n <= 2) {
            return n;
        }
        long pre1 = 2L;
        long pre2 = 1L;
        long fib = 0L;
        for (int i = 3; i <= n; i++) {
            fib = pre1 + pre2;
            pre2 = pre1;
            pre1 = fib;
        }
        return fib;
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(fibonacci(3));
    }
}

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

来自：
《剑指Offer》
Coding-Interviews/斐波那契数列.md at master · todorex/Coding-Interviews