JavaScript でフィボナッチ数列を実装する 4 つの方法の紹介 (コード)

この記事では、JavaScript でフィボナッチ数列を実装する 4 つの方法 (コード) を紹介します。一定の参考値があります。困っている友人は参考にしてください。お役に立てれば幸いです。

先日、インタビューでフィボナッチ数列の実装と最適化について聞かれたのですが、そのシーンが長らく行き詰まっていたので、まとめてみます(jsで実装)。

タイトル紹介

フィボナッチ数列は黄金分割数列とも呼ばれ、1,1,2,3,5,8,13,21,34のような数列を指します。 ...、次の再帰メソッド定義があります: F(1)=1,F(2)=1,F(n)=F(n-1) F(n-2)(n> =2, nは正の整数です)、フィボナッチ関数を実装するには js を使用してください。

方法 1: 再帰的実装

質問の再帰にヒントを得て、再帰的に実装できます。コードは次のとおりです:

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

利点: コードは比較的簡単です。シンプルで簡単 分かりやすい;
デメリット: 数値が大きすぎると特に遅くなる理由は、F(9)を計算する際にF(8)とF(7)を計算する必要があるためですが、 F(8)を計算すると、F(7)とF(6)を計算する必要があり、F(7)を繰り返し計算することになり、毎回計算を繰り返すと無駄が発生するため、あまり良い方法ではありません。

方法 2: クロージャを使用して各再帰値を保存する

方法 1 から、通常の再帰を使用すると不要な無駄が発生することがわかります。そこで、最初に考えることは、それぞれの再帰値を保存することです。再帰値。今回生成された再帰値は保存され、次回から直接使用できます。コードは次のとおりです。

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        let arr = [0,1];//在外部函数中定义数组，内部函数给数组添加值
        function calc(n){
            if(n<2){
                return arr[n];
            }
            if(arr[n] != undefined){
                return arr[n];
            }
            let data = calc(n-1) + calc(n-2);//使用data将每次递归得到的值保存起来
            arr[n] = data;//将每次递归得到的值放到数组中保存
            return data;
        }
        return calc(n);
    }

方法 3: 配列実装を直接使用する (動的プログラミング)

アイデアは方法 2 と似ていますが、後続の繰り返し計算では計算値を保存する必要があるため、配列を直接使用して保存することができます。

function fibonacci(n){
        var a = [0,1,1];
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        if(n >= 3){
            for(var i=3;i<=n;i++){
                a[i] = a[i-1]+a[i-2];
            }
        }
        return a[n];
    }

方法 4: 変数を直接使用して実装する

配列を使用して格納する場合と比較して、変数を使用すると、変数が合計 3 つしかないため、メモリをあまり浪費しません。最後に計算された値と最初の 2 つの値しか保存できず、以前の値は置き換えられてしまうという欠点もあります。

function fibonacci(n){
        var pre = 0;//表示前一个值
        var cur = 1;//表示后一个值
        var data;//表示当前值

        if(n < 0) throw new Error(&#39;请输入大于0的值！&#39;);
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n > 2){
            for(var i=2;i<=n;i++){
                data = pre + cur;
                pre = cur;
                cur = data;
            }
        }
        return data;
    }

まとめ

実際、フィボナッチ数列を計算するとき、ほとんどの人は再帰的手法を思い浮かべますが、イベントの複雑さの観点から、それは良い手法ではありません。空間を使用して時間を交換すること、つまり、次回の計算の繰り返しを避けるために再帰によって生成された値を保存することです。

以上がJavaScript でフィボナッチ数列を実装する 4 つの方法の紹介 (コード)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。