《剑指offer第二版》题10：斐波那契数列

fibonacci.png

解法一：递归

public static long fibonacciRecursively(long number) {
    if ((number == 0) || (number == 1))
        return number;
    else
        return fibonacciRecursively(number - 1) + fibonacciRecursively(number - 2);
}

使用递归方法会存在很多重复的计算。比如以求解f(5)为例进行分析。想求得f(5)，需要先求得f(4)和f(3)，要求得f(4)，需要先得到f(3)和f(2)，要求得f(3)，需要先求得f(2)和f(1)...，求解过程如下图所示：

img2.png

解法二：从下到上求解

首先根据f(0)和f(1)计算出f(2),再根据f(1)和f(2)计算出f(3)...以此类推就可以计算出f(n)了。这种方法的时间复杂度是O(n)。

     public static long fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }

        //记录第n-2个数的fibonacci值
        long preTwo = 1;
        //记录第n-1个数的fibonacci值
        long preOne = 1;
        //记录前两个（第n个）的Fibonacci数的值
        long current = 2;
        for (int i = 3; i <= n; i++) {
            current = preTwo + preOne;
            preTwo = preOne;
            preOne = current;
        }
        return current;
    }

注意：剑指 Offer 10- I. 斐波那契数列 上的题最后的计算结果是需要对一个大数字取模。因为在45左右，斐波那契数列的结果就很大了，超出Long的最大值。

LeetCode上的提交

public int fib(int n) {

         final int MOD = 1000000007;
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }

        //记录第n-2个数的fibonacci值
        int preTwo = 1;
        //记录第n-1个数的fibonacci值
        int preOne = 1;
        //记录前两个（第n个）的Fibonacci数的值
        int current = 0;
        for (int i = 3; i <= n; i++) {
            current = (preTwo + preOne) % MOD;
            preTwo = preOne;
            preOne = current;
        }
        return current;
    }

测试用例

     public static void main(String[] args) {
        for (int counter = 0; counter <= 10; counter++) {
            System.out.printf("Fibonacci of %d is: %d\n",
                    counter, fibonacci(counter));
            System.out.printf("fibonacciRecursively of %d is: %d\n",
                    counter, fibonacciRecursively(counter));
        }
    }

输出结果

Fibonacci of 0 is: 0
fibonacciRecursively of 0 is: 0
Fibonacci of 1 is: 1
fibonacciRecursively of 1 is: 1
Fibonacci of 2 is: 1
fibonacciRecursively of 2 is: 1
Fibonacci of 3 is: 2
fibonacciRecursively of 3 is: 2
Fibonacci of 4 is: 3
fibonacciRecursively of 4 is: 3
Fibonacci of 5 is: 5
fibonacciRecursively of 5 is: 5
Fibonacci of 6 is: 8
fibonacciRecursively of 6 is: 8
Fibonacci of 7 is: 13
fibonacciRecursively of 7 is: 13
Fibonacci of 8 is: 21
fibonacciRecursively of 8 is: 21
Fibonacci of 9 is: 34
fibonacciRecursively of 9 is: 34
Fibonacci of 10 is: 55
fibonacciRecursively of 10 is: 55

题目二：青蛙跳台阶问题

参考青蛙跳台阶问题

参考链接：

*【剑指Offer学习】【面试题9 ： 斐波那契数列】

• 青蛙跳台阶问题