1

最初の 100 個のフィボナッチ数を .txt ファイルに出力しようとしています。実行できるようになりましたが、時間がかかります。フィボナッチまたはフィボナッチ2はより高速ですか? 以下のコードは最初のものを使用しています。

#!/usr/bin/env node

var fs = require('fs');

// Fibonacci
// http://en.wikipedia.org/wiki/Fibonacci_number
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);}
};

// Fibonacci: closed form expression
// http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
var fibonacci2 = function(n) {
    var phi = (1 + Math.sqrt(5))/2;
    return Math.round((Math.pow(phi, n) - Math.pow(1-phi, n))/Math.sqrt(5));
};

// Find first K Fibonacci numbers via basic for loop
var firstkfib = function(k) {
    var i = 1;
    var arr = [];
    for(i = 1; i < k+1; i++) {
        var fibi = fibonacci(i);
        arr.push(fibi);

        // Print to console so I can monitor progress
        console.log(i + " : " + fibi); 
    }
    return arr;
};

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

var k = 100;

// write to file
var outfile = "fibonacci.txt";
var out = fmt(firstkfib(k));
fs.writeFileSync(outfile, out);
console.log("\nScript: " + __filename + "\nWrote: " + out + "\nTo: " + outfile);
4

4 に答える 4

1

一般に、再帰関数は「クリーン」で「簡単」に記述できますが、多くの場合、より多くのリソース (スタックの蓄積によるメモリ) が必要になります。あなたの場合、最初に100を取得する最良の方法は、フィボナッチ数列の次の数を計算してリストに追加する単純なループを使用してプログラムすることです。

double a[100];
a[0] = 1;
a[1] = 1;
K=2;
Do{ 

{
 a[k] = a[k - 2] + a[k- 1];
 k++;
}While (k!=100)
于 2013-07-02T15:52:26.840 に答える
0

これは、この計算を行うための非常に単純な方法です。次のようなことをしてみてください：

long[] a = new long[100];
a[0] = 1;
a[1] = 1;
for (int i = 2; i < 100; ++i)
{
    a[i] = a[i - 2] + a[i - 1];
}

for (int i = 0; i < 100; ++i)
Console.WriteLine(a[i]);

このようにして、線形時間 O(n) を取得しています

于 2013-07-02T15:49:33.323 に答える