【詳細な証明過程を含む】カエルは1回に1段の階段を飛び上がることも、2段を飛び上がることもできる.このカエルが1つのn級の階段に飛び上がることを求めて全部で何種類の跳び方があります

【問題】カエルは1回に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
時間制限:1秒空間制限:32768 K

考え方1：再帰法

二叉木を用いて,結点が現在の残りの階段数,左の子供が1段跳び,右の子供が2段跳び,残りの階段数が0,すなわち葉の結点になるまでジャンプ法の数を加算する.
アルゴリズムは簡単で、以下はJavaScript実装コード(実行タイムアウト)です.

var ways = 0;
//    
// function TreeNode(val) {
//  this.val = val;
//  this.left = null;
//  this.right = null;
// }
//      ，      ，           
function createTree(number) {
    // var T = new TreeNode(number);
    if (number >= 1)
        // T.left = createTree(number - 1);
        createTree(number - 1);
    if (number >= 2)
        // T.right = createTree(number - 2);
        createTree(number - 2);
    if (number == 0) {
        ways++;
    }
    // return T;
}
// main
function jumpFloor(number)
{
    ways = 0;
    createTree(number);
    return ways;
}

長所:分かりやすく、自分で絵を描く考え方と同じです.欠点:本当にツリーを作成しなくてもnumber比が大きい場合、再帰的で空間時間の複雑さが高く、プログラム効率も低い.

 

構想2:再帰回転反復(フィボナッチ数列)

考え方1の再帰を反復書き方に変えると,フィボナッチ数列によく似ていることがわかる.実験結果からnumberを0から10までそれぞれ求めた結果,[1,1,2,3,5,8,13,21,34,55,89]であり,フィボナッチ数列法則にも合致した.次に、数学的帰納法を用いて検証します.
Fb(i)はフィボナッチ数列第i項の値(iは0から)、jump(i)はステップ数iのときの総ホップ数、numberはステップ数1と記す.number=0または1の場合、ジャンプ法は1であり、jump(0)=Fb(0)、jump(1)=Fb(1)が成立する.2.number=n(n>1)の場合、jump(n)=Fb(n)が成立すると仮定すると、number=n+1の場合、2つの反発するジャンプ法がある:①n段目にジャンプし、1段目にジャンプすると、n段目にジャンプするにはいくつかの方法があり、このジャンプ法がどれだけあるか、すなわちjump(n)である.なお、ここではjump(n)+1ではなく、ここでは「第n級にジャンプし、さらに1級にジャンプする」というジャンプ法を指し、「再1級にジャンプする」とは、n級にジャンプした上で②第n-1級にジャンプし、さらに2級にジャンプすることを意味し、ジャンプ法はjump(n-1)である.注意ここでは一気に2段ジャンプするしかありません.そうしないと1段ジャンプとジャンプ①が重なるとjump(n+1)=jump(n)+jump(n-1)=Fb(n)+Fb(n-1)=Fb(n+1)jump(n+1)=Fb(n+1)が成立します.
したがって,本テーマはフィボナッチ数列のnumber項を求めることに等しい.コードは次のとおりです.

function jumpFloor(number)
{
    var fb = [1, 1];
    for (var i = 2; i <= number; i++) {
    	fb.push(fb[i - 2] + fb[i - 1]);
    }
    return fb[number];
}

利点:速度の速さの欠点:空間が時間を変えて、前の計算結果を保存する必要があります(3つの変数を繰り返し利用することで、空間を下げることができます)