斐波那契数列

剑指offer面试题系列

代码

package com.study;

/*
 * 求斐波那契数列第n个数字 
 * */
public class suanfa7 {

    /*最原始的递归版，思路简洁，但是如果输入参数较大，会造成栈的深度太深，运行会很慢*/
    public static int Fibonacci1(int num) {
        if(num <= 1)
            return num;

        else
            return Fibonacci1(num - 1) + Fibonacci1(num - 2);
    }

    /*第二种方法，算法复杂度为O(n),利用一种迭代的思路，避免了递归的入栈等操作，提高了时间效率
     * 但是如果数字超过了30可能就需要把返回类型改成long了*/
    public static int Fibonacci2(int num) {
        if(num <= 1)
            return num;
        else {
            int sum = 1;
            int preNum = 1;
            int prepreNum = 0;
            int i = 2;
            while(i < num) {
                prepreNum = preNum;
                preNum = sum;
                sum = prepreNum + preNum;
                i++;
            }

            return sum;
        }
    }


    public static void main(String[] args) {
        System.out.println(Fibonacci2(10));
    }
}

备注：

1.斐波那契数列虽然看似简单，但是要考虑清楚实际的情况，要不断优化算法的复杂度。

2.另外，对于迭代这种思路，以前很没有感觉，就觉得没有一种属于自己的快速的方法，可以看出迭代量。突然想到，调试的时候，观察变量的时候，经常用列表的方法去看值，直观对比，那么写程序的时候不妨也列表试试，果然相当有效果，迭代量是什么一目了然。

之后只要顺着思路写程序即可。

3.斐波那契数列的应用场景很多：

典型的比如：青蛙跳台阶问题，矩形覆盖问题等。解决这种问题的思路关键在于看能否找到一种递归关系

f(n) = f(n-1) + f(n - 2)

如果找到这种递推关系，则很容易想到是斐波那契数列。

以后遇到数列题，一般首先应该想到是斐波那契数列。