【刷算法】我知道的所有类似斐波那契数列的问题

NotFound 发布于2019-08-22 18:10 / 3371人阅读

摘要：有一类算法问题类似斐波那契数列，而且解决办法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契数列跳台阶问题题目描述一只青蛙一次可以跳上级台阶，也可以跳上级。给定整数，求年后牛的数量。分析设为年后牛的数量，则第年牛的来源有两个。

有一类算法问题类似斐波那契数列，而且解决办法基本差不多。
不了解斐波那契套路的可以看【刷算法】斐波那契数列

跳台阶问题

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析
设到第n阶总共有f(n)种跳法，而且想跳到第n阶只有两种可能，要么从第n-1阶跳一阶到达，要么从第n-2阶跳两阶到达，所以递推式为f(n)=f(n-1)+f(n-2)。特殊情况为，n=0的时候跳法为0；n=1时，跳法为1；n=2时，跳法为2
递归

function jump(n) {
    if(n < 1)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    return jump(n-1) + jump(n-2);
}

非递归

function jumpFloor(number)
{
    if(number < 1)   
        return 0;
    if(number === 1)
        return 1;
    if(number === 2)
        return 2;
    var s1 = 1;
    var s2 = 2;
    var res =  0;
    for(var i = 3;i <= number;i++){
        res = s1 + s2;
        s1 = s2;
        s2 = res;
    }
    return res;
}

{{BANNED}}跳台阶问题

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析
{{BANNED}}的跳台阶问题处理起来确实是有些棘手，一次可以跳上的阶数是不定的。
先看n=0时，跳法f(0)=0；
n=1，只能是从第0个台阶跳过来，跳法f(1)=1;
n=2，可能是第0个台阶跳了2阶或者从第1个台阶跳了1阶，跳法f(2)=f(0)+f(1);
n=3，可能是第0个台阶跳了3阶、第1个台阶跳了2阶、第2个台阶跳了1阶，跳法f(3)=f(0)+f(1)+f(2);
...
n=n-1，跳法f(n-1)=f(0)+f(1)+f(2)+...+f(n-2);
n=n，跳法f(n)=f(0)+f(1)+f(2)+...+f(n-1);
由上面两个等式得：f(n) = f(n-1)+f(n-1) = 2f(n-1)
代码实现：

function jumpFloorII(number)
{
    if(number < 1)
        return 0;
    if(number === 1)
        return  1;
    return 2*jumpFloorII(number-1)
}

矩阵覆盖

题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
分析
ps：为了方便分析问题，给每个小矩形不同的颜色，其实他们之间没有差别

假设上图为用n个21的小矩形无重叠地覆盖一个2n的大矩形，方法数为f(n)，那么f(n)可以从哪些情况推导出来呢？
首先很明显我们知道，2*1的小矩形要么是横着放要么是竖着放，所以f(n)的情况只能由以下两种情况得来：

这种情况只需要再加一个竖着的小矩形就可以了，所以这种情况其实是f(n-1)

这种情况下，只需要再加一个横着的小矩形就可以了，但是由于这种横着的小矩形只能成对出现，所以这种情况其实是f(n-2)
综上，f(n) = f(n-1)+f(n-2)
特殊情况时，f(0)=0，f(1)=1，f(2)=2
代码实现
递归版

function rectCover(n)
{
    if(n === 0)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    return rectCover(n-1) + rectCover(n-2)
}

非递归版

function rectCover(n)
{
    if(n === 0)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    var s1 = 1, s2 = 2;
    var res = 0;
    for(var i = 3;i <= n;i++) {
        res = s1 + s2;
        s1 = s2;
        s2 = res;
    }
    
    return res;
}

母牛生小牛问题

题目描述
假设农场中成熟的母牛每年只会生一头小母牛，且永远不会死。第一年农场有1头成熟的母牛，从第二年开始，母牛开始生小母牛，每只小母牛3年之后成熟又可以生小母牛。给定整数N，求N年后牛的数量。
分析
设f(n)为n年后牛的数量，则第n年牛的来源有两个。
首先，牛是永远不会死的，所以第n-1的牛都会活到第n年；
其次，还有一部分新生的牛，因为每只小母牛3年之后成熟才可以生小母牛，所以第n-3年的未成熟小母牛到了第n年会成熟且开始生小母牛，所以第n年新生的牛来自于第n-3年的未成熟小母牛和成熟母牛。
综上，f(n) = f(n-1) + f(n-3)
特殊的，f(1)=1，f(2)=2，f(3)=3
代码实现
直接非递归版

function cow(n) {
    if(n < 1)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2) 
        return 2;
    if(n === 3)
        return 3;
    var s1 = 1, s2 = 2, s3 = 3;
    var res = 0;
    for(var i = 4;i <= n;i++){
        res = s1+s3;
        s1 = s2;
        s2 = s3;
        s3 = res;
    }
    
    return res;
}

GPU云服务器云服务器波那契数列最短路问题的算法分析数据的算法问题学习遗传算法遇到的问题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95572.html

【刷算法】斐波那契数列

摘要：题目现在要求输入一个整数，请你输出斐波那契数列的第项。递归操作时间复杂度太高，而且用递归会产生很多重复的操作。非递归操作这种方法就是一次遍历过去就行，计算第个数时，使用了两个变量存储第和第个数，使时间复杂度降低到题目现在要求输入一个整数n，请你输出斐波那契数列的第n项。递归操作O(2^n) function fibonacci(n) { if(n < 1) ...

IamDLY 2019-08-22 18:09 评论0 收藏0
算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0
太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0
动态规划问题（1）——斐波那契数列

摘要：动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。今天我们先从我们最熟的斐波那契数列数列开始。斐波那契数列在很多地方都会用上，我是从一个台阶问题发现的，同时知道了动态规划的解法。前段时间一直写了几个算法题目，发现有个很牛逼的算法，动态规划，虽然有的解题思路和动态规划很像，但是当时不知道其中的原理和一些通用性，接下来的几天，通...

Eminjannn 2019-08-21 11:24 评论0 收藏0
leetcode 100 斩！回顾

摘要：斩从第题开始，到现在也差不多快一年了，回顾纪念一下。当时对回溯动态规划也都只是上课的时候学过，也并不熟练。最经典的例子就是斐波那契数列了，求第项数列的值。 leetcode 100 斩！从第 1 题开始，到现在也差不多快一年了，回顾纪念一下。 showImg(https://segmentfault.com/img/bVbu461?w=661&h=191); 为什么开始刷题？从大一就...

wyk1184 2019-08-16 18:35 评论0 收藏0