算法学习--斐波那契算法

什么是斐波那契查找

image

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。规律也比较好找。

上代码：

/**
     * [fib description]斐波那契算法1(递归方法) -- 调用（n-1）和（n-2）两个数相加得到结果，但是不能计算过大的数值，否则会卡死
     * @param  {[type]} n [description]
     * @return {[type]}   [description]
     */
    function fib1(n){
        let result = n <= 1 ?  n : fib1(n-1) + fib1(n-2);
        return result;
    }
    console.log('fib1-- ',fib1(40));

    /**
     * [fib2 description]斐波那契算法2（循环）-- 只需要弄清楚需要循环的次数（n-1），然后计算result，再重新给first和second赋值计算下一次result，直到循环结束。此方法可以计算大数值的值，且计算速度飞快（ps:写法还有优化空间）。
     * @param  {[type]} n [description]
     * @return {[type]}   [description]
     */
    function fib2(n){
        if(n <= 1)return n;
        let first = 0;
        let second = 1;
        for(let i = 0;i < n - 1;i++){
            let result = first + second;
            first = second;
            second = result;
        }
        return second;
    }
    console.log('fib2-- ',fib2(100));

计算结果