2

私は現在、coursera で提供されているスタートアップ エンジニアリング コースのプログラム 2 を行っています。

Amazon Web サービスを使用して ubuntu インスタンスを使用してプログラミングしていますが、プログラミングが常にハングしています。node.js プログラムに問題がある可能性がありますが、見つけられないようです。

このプログラムは、コンマで区切られた最初の 100 個のフィボナッチ数を生成することを目的としています。

    #! /usr/bin/env node

    //calculation

    var fibonacci = function(n){
                    if(n < 1){return 0;}
                    else if(n == 1 || n == 2){return 1;}
                    else if(n > 2){return fibonacci(n - 1) + fibonacci(n-2);}
            };

    //put in array

    var firstkfib = function(k){
                    var i;
                    var arr = [];
                    for(i = 1; i <= k; i++){
                            arr.push(fibonacci(i));
                    }
            return arr

            };

    //print

    var format = function(arr){
            return arr.join(",");
            };

    var k = 100;
    console.log("firstkfib(" + k +")");
    console.log(format(firstkfib(k)));

私が得る唯一の出力は

    ubuntu@ip-172-31-30-245:~$ node fib.js
    firstkfib(100)

その後、プログラムがハングします

4

3 に答える 3

4

あなたが時間の複雑さとアルゴリズム分析に精通しているかどうかはわかりませんが、プログラムの実行時間が指数関数的であることがわかりました。これは基本的に、入力が増加すると、プログラムの実行にかかる時間が指数関数的に増加することを意味します。（私の説明があまり明確でない場合は、このリンクを確認してください）

この種の実行時間は非常に遅いことがわかります。たとえば、プログラムを実行するのに 1 ミリ秒かかる場合、プログラムをk=1実行2^100 msするにはk=100. これは途方もなく大きな数字であることが判明しました。

いずれにせよ、Zhehao が指摘するように、解決策は and の値を (たとえば配列に) 保存し、fib(n-1)それfib(n-2)を再利用して を計算することfib(n)です。方法については、MIT のビデオ レクチャー (最初の 15 分) をご覧ください。

于 2013-06-25T23:48:58.907 に答える
1

最後にリスト全体を印刷するのではなく、計算中の数値を印刷してみることをお勧めします。計算が途中でぶら下がっている可能性があります。

別の注意点として、これはおそらくフィボナッチ数のリストを計算する最も非効率的な方法です。fibonacci(n) を計算し、次に fibonacci(n+1) を計算しますが、前の計算の作業を再利用する必要はありません。戻って、方法を再考することをお勧めします。はるかに高速で単純な反復法があります。

于 2013-06-25T23:49:15.010 に答える