【刷算法】我知道的所有類似斐波那契數列的問題

NotFound 發布于2019-08-22 18:10 / 3400人閱讀

摘要：有一類算法問題類似斐波那契數列，而且解決辦法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契數列跳臺階問題題目描述一只青蛙一次可以跳上級臺階，也可以跳上級。給定整數，求年后牛的數量。分析設為年后牛的數量，則第年牛的來源有兩個。

有一類算法問題類似斐波那契數列，而且解決辦法基本差不多。
不了解斐波那契套路的可以看【刷算法】斐波那契數列

跳臺階問題

題目描述
一只青蛙一次可以跳上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云服務器波那契數列最短路問題的算法分析數據的算法問題學習遺傳算法遇到的問題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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