青蛙跳

作者: _Dot912 | 来源:发表于2017-10-20 17:22 被阅读0次

撒欢
看桃花
蛙跳
2021-07-22
《宇宙万物皆有定数》选文
青蛙跳
青蛙跳
蛙跳句
蛙跳有感
青蛙🐸跳跳跳

斐波那契数列变形

做到一个有意思的题：

一只青蛙一次可以跳上1级台阶，也可以跳上2级，该青蛙跳上一个n级的台阶总共有多少种跳法？

首先来理一下思路，做几个假设先：

找规律

从上图是不是可以看出些什么？当n=1时，跳法为1种，n=2时跳法为2种，n>2时，我们可以把n级台阶的跳法不同总数看成是n的函数f(n)，f(n)=f(n-1)+f(n-2)

关键思想

这个实质上就是斐波那契数列的简单变形，不知道斐波那契是什么的小伙伴可以移步至文首点击链接。

看到以上数学公式马上可以想到最简单的一种写法来解决这个问题：

方法一：递归

function fib(n) {
    return n < 3 ? n : (fib(n - 1) + fib(n - 2))
}

结果如下

递归写法结果

优点：代码简洁易懂
缺点：重复运算导致运算量太大，效率极其低下，损耗性能，递归的次数太多时就会超出栈的容量导致调用栈溢出，而栈溢出可能导致计算出错误的数据，不推荐！！！

既然递归的方法不可取，那有没有更高效的办法呢？
如果我们将计算过的斐波那契数存入数组中，那么当要计算一个斐波那契数时只需要通过下标的方式找到它前两个数字相加就可以了

方法二：循环

function fib(n) {
    var temp = []
    if (n == 1 || n == 2) {
        return n
    } else {
        temp[1] = 1
        temp[2] = 2
        for (var i = 3; i <= n; i++) {
            temp[i] = temp[i - 1] + temp[i - 2]
        }
        return temp[i - 1]
    }
}

结果如下：

循环写法结果

优点：效率高，避免重复计算，传入n=1000，只需要1ms就出现结果
缺点：循环写法用空间换时间，如果n足够大我们则需要开辟足够大的内存空间用来存储这个数组，也不是很可取

是不是可以不用存储所有的斐波那契数，只需要把我们要求的前两个斐波那契存储下来就可以了呢？答案是肯定的

方法三：定义临时变量

function fib(n) {
    var num1 = 1, num2 = 1, num3 = 1
    for (var i = 2; i <= n; i++) {
        num3 = num1 + num2
        num1 = num2
        num2 = num3
    }
    return num3
}

结果如下：

定义临时变量写法结果

优点：与循环写法一样，效率高，且只用存储前两个变量，省内存，省时间，可以说是非常完美了。

如果说不让使用临时变量呢，有这么苛刻的人吗？可是万一有呢【手动滑稽】
有也可以解决的啦~

方法四：一加一减解决问题

function fib(n) {
    var num1 = 1, num2 = 1
    for (var i = 2; i <= n; i++) {
        num1 = num1 + num2
        num2 = num1 - num2
    }
    return num1
}

结果如下：

一加一减

细心的你会发现，诶，为什么同样传入的n值为500，为什么前面得到的结果是2.2559151616193602e+104，而现在得到的却是2.2559151616193665e+104呢？

这就要说到浏览器计算的精度问题了，由于计算机是用二进制来存储和处理数字，无法精确表示浮点数，连自身都不能精确，运算起来就更加得不到精确的结果了，因此这种精度差异几乎出现在所有的编程语言中（例如C/C++/C#,Java），准确的说：“使用了IEEE 754浮点数格式”来存储浮点类型(float 32,double 64)的任何编程语言都有这个问题，而C#、Java是因为提供了封装类decimal、BigDecimal来进行相应的处理才避开了这个精度差异。而javascript是一种弱类型的脚本语言，本身并没有对计算精度做相应的处理。

举个简单的栗子：

精度测试

值越大误差越大，当计数变为科学计数法后，运算一次就有一次误差，上例中，加法一次误差，减法一次误差，导致最后呈现出的结果有些不一样，而实际的结果却没有问题，看以下在ruby中测试的结果~

n=500时ruby中的结果

以上结果测试的是n=500时方法三和方法四给的结果
可以看出，在不用科学计数法表示数字的情况下，精度就可以得到保证了，而我想知道的只是第四种方法得到的结果有没有问题，答案是没有问题，可以放心使用。

优点：非常完美，除了科学计数法表示的精度差别
缺点：值过大时得到的是科学计数法表示的结果，存在误差，n的值越大误差越大，然鹅实际结果是没有问题滴，可以大胆使用。

综上所述，还是推荐方法三，毕竟如果没有龟毛的人提出不准使用临时变量这种需求，它完全是完美的。

那么~来扩展一题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

首先还是穷举法：

找规律

虽然很蠢但这种找规律的方法很快呀
代码如下

function fibBT(n){
    return Math.pow(2,n-1)
}

结果如下：效率也是非常高呢

变态跳结果

做完后我在网上看了很多关于变态跳的解法，几乎都是千篇一律说变态跳是斐波那契引申问题，分析过程繁杂且不清晰，字数太多我一时还没看明白，所以感觉不太满意，我的代码经自己多次测试没有发现问题，如果你有查到bug欢迎随时指正，一定虚心接受。

20171024补充一题

用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法?

本题依旧是斐波那契数列变形

凑合看看

//n=1，f(n)=1,n=2,f(n)=2,n>2,f(n)=f(n-1)+f(n-2)

function recFib(n) {
    var num1 = 0, num2 = 1, num3
    if (n >= 1) {
        for (var i = 0; i < n; i++) {
            num3 = num1 + num2
            num1 = num2
            num2 = num3
        }
        return num3
    }
}
console.log(recFib(1))//1
console.log(recFib(2))//2
console.log(recFib(3))//3
console.log(recFib(4))//5
console.log(recFib(5))//8
console.log(recFib(6))//13
console.log(recFib(7))//21
console.log(recFib(8))//34
console.log(recFib(9))//55
console.log(recFib(500))//2.2559151616193602e+104

推荐阅读：