【剣指offer】8.フィボナッチ数列

タイトル

タイトルの説明では、フィボナッチ数列を知っていますが、整数nを入力する必要があります.フィボナッチ数列のn番目の項目(0から0番目)を出力してください.

基本的な考え方

この問題は剣指offerの中で実際には再帰的な反例として話されている.
再帰の本質は,1つの問題が2つ以上の小さな問題に分解され,複数の小さな問題が互いに重なり合う場合,繰返し計算が存在することである.
f(n)=f(n−1)+f(n−2)このような分割は再帰的に使用されるのが典型的なオーバーラップの存在であるため,非常に多くの繰返し計算をもたらす.
また、関数呼び出しのたびに愛メモリに空間を割り当てる必要があり、各プロセスのスタックの容量は限られており、再帰階層が多すぎると、スタックがオーバーフローします.
再帰は最大数から始まり、小さな数に分解して計算し、再帰を考えなければ小数から計算し、底から積み重ねていけばいいのですが、実は考え方も簡単です.

コード#コード#

function Fibonacci(n)
{
    if(n<=1){
        return n;
    }
    let i = 1;
    let pre = 0;
    let current = 1;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

拡張

1.階段を跳ぶ：

1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を飛び上がるのが全部で何種類の跳び方があることを求めます(前後の順序が異なって異なる結果を計算します).
法則を探す:
3段階段を跳ぶのは2段階段を跳ぶ跳法+1段階段を跳ぶ跳法に等しい.
四段階段を跳ぶのは三段階段を跳ぶ跳法+二段階段を跳ぶ跳法に等しい.
明らかにフィボナッチ数列の法則にも合致している.

function jumpFloor(n)
{
    if(n<=2){
        return n;
    }
    let i = 2;
    let pre = 1;
    let current = 2;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

3.長方形のオーバーライド

21の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の21の小さい矩形で重ならずに1つの2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
階段を飛び降りる問題に似ている.
8ブロックあると仮定
1枚目は縦置きで、後ろに7枚残っていて、f(7)の方法があります.
1枚目は横に置いて、後ろに6枚残って、全部でf(6)種類の方法があります.
すなわちf(8)=f(6)+f(7)
f(n)=f(n-1)+f(n-2)

function rectCover(n)
{
    if(n<=2){
        return n;
    }
    let i = 2;
    let pre = 1;
    let current = 2;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

3.変態ステップ

1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
各階段はジャンプするかしないかを選択することができ、最後の階段は必ずジャンプします.
各ステップには2つの選択があり,n個のステップには2つのn次方種の選択がある.
だから全部で2のn-1ジャンプ法があります.
ビット演算の使用

function jumpFloorII(number)
{
    return 1<