「剣指offer」—JavaScript(8)ジャンプ階段

745 ワード

階段をおどる
テーマの説明
一匹のカエルは一回に1段の階段を上ったり、2段の階段を登ったりします.この蛙が1つのn段の階段に上がることを求めて、全部で何種類の踊り方がありますか?
コードを実現
function jumpFloor(number)
{
    if (number<0){
        return -1;
    }else if(number <=2){
        return number
    }
    var arr = [];
    arr[0] = 1;
    arr[1] = 2;
    for(var i = 2; i < number; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[number-1];
}
考え方
本題の前提は一回だけの1階または2階の踊りです.
  • は、最初にジャンプしたのが1階であると仮定し、残りはn−1ステップであり、踊り方はf(n−1)である.
  • は、最初のジャンプは2階であると仮定し、残りはn−2段であり、踊りはf(n−2)である.
  • は、f(n)=f(n−1)+f(n−2)であると仮定される.
  • 階段が一階しかない場合、f(1)=1、二階しかない場合、f(2)=2;
  • はここまで見積りました.最終的に得られたのはフィボナッチの数列です.n=1、f(n)=1 n=2、f(n)=2 n>2、整数、f(n)=f(n)+f(n-2)