1

我正在尝试将前 100 个斐波那契数输出到 .txt 文件。我让它运行，但它需要一段时间。fibonacci 或 fibonacci2 会更快吗？下面的代码使用第一个。

#!/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 回答
1

递归斐波那契函数以错误的方式实现。本文讨论了递归实现它的正确方法Recursion and Fibonacci Numbers。对于那些懒得阅读的人，这是他们的代码（它是用 C 语言编写的，但翻译起来应该不会太难）：

unsigned long fib(unsigned int n)
{
  return n == 0 ? 0 : fib2(n, 0, 1);
}

unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1)
{
  return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}

一个更有效的实现会在计算斐波那契数列的值时对其进行缓存：

var cache = [];

var fibonacci = function(n) {
  if(cache.length > n) return cache[n];
  return (cache[n] = fib2(n, 0, 1));
};

var fib2 = function(n, p0, p1) {
  if(cache.length > n) return cache[n];
  return n == 1 ? p1 : (cache[n] = fib2(n - 1, p1, p0 + p1));
};

我真的不懂语言，所以代码可能存在一些问题，但这至少是它的要点。

于 2013-07-02T17:40:19.737 回答
1

对于您的问题，我们不能比 O(n) 做得更好，因为您需要生成所有前 n (n=100) 个数字。

有趣的是，如果您只需要第 n 个 fib 数字，那么也存在 O(log n) 解决方案。

该算法非常简单：使用分而治之的方法找到矩阵 A 的 n 次方并报告第 (0,0) 个元素，其中

 A = |1     1 |
     |1     0 |

递归是

 A^n = A^(n/2) * A^(n/2)

时间复杂度：

T(n) = T(n/2) + O(1) = O(logn)

如果你用一张纸想一想，你会发现证明很简单，而且是基于归纳原理的。如果您仍需要帮助，请参阅此链接

注意：当然，您可以迭代计算 A、A^2、A^3 等等。但是，与其他答案中描述的其他更简单的解决方案相比，使用它没有意义。（因为纯粹的代码复杂性）

于 2013-07-12T00:43:20.967 回答
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 回答