生成斐波纳契数列

Question

var x=0, 
var y=1;
var z;

fib[0] = 0;
fib[1] = 1;
for(i=2; i<=10; i++)
{
    alert(x+y);
    fib[i]=x+y;
    x=y;
    z=y;
}

我试图生成一个简单的Fibonacci序列,但没有输出.谁能告诉我什么是错的？

Answer 1

根据采访蛋糕问题,顺序为0,1,1,2,3,5,8,13,21.如果是这种情况,此解决方案可以正常工作,而不需要使用数组.

function fibonacci(n) {
   return n < 1 ? 0
        : n <= 2 ? 1
        : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(4));

想想这样.

   fibonacci(4)   .--------> 2 + 1 = 3
      |          /               |
      '--> fibonacci(3) + fibonacci(2)
            |    ^           
            |    '----------- 2 = 1 + 1 <----------.
1st step -> |                     ^                |
            |                     |                |
            '---->  fibonacci(2) -' + fibonacci(1)-'

请注意,这个解决方案虽然效率不高.

Answer 2

你从未声明fib过是一个数组.使用var fib = [];来解决这个问题.

此外,您永远不会修改y变量,也不会使用它.

下面的代码更有意义,而且,它不会创建未使用的变量:

var i;
var fib = []; // Initialize array!

fib[0] = 0;
fib[1] = 1;
for (i = 2; i <= 10; i++) {
  // Next fibonacci number = previous + one before previous
  // Translated to JavaScript:
  fib[i] = fib[i - 2] + fib[i - 1];
  console.log(fib[i]);
}

Answer 3

这是一个简单的函数,使用函数中的参数迭代Fibonacci序列到一个数组中,而for不是循环体:

fib = function(numMax){
    for(var fibArray = [0,1], i=0,j=1,k=0; k<numMax;i=j,j=x,k++ ){
        x=i+j;
        fibArray.push(x);
    }
    console.log(fibArray);
}

fib(10)

[0,1,1,2,3,5,8,13,21,34,55,89]

Answer 4

您应该首先将fib变量声明为数组(例如var fib = []或var fib = new Array()),我认为您对算法有点困惑.
如果使用数组来存储斐波纳契数列,则不需要其他辅助变量(x,y,z):

var fib = [0, 1];
for(var i=fib.length; i<10; i++) {
    fib[i] = fib[i-2] + fib[i-1];
}
console.log(fib); 

单击演示

您也应该考虑递归方法(请注意,这是一个优化版本):

function fib(n, undefined){
    if(fib.cache[n] === undefined){
        fib.cache[n] = fib(n-1) + fib(n-2);
    }

    return fib.cache[n];
}
fib.cache = [0, 1, 1];

然后,在调用斐波纳契函数后,您将获得该fib.cache字段中的所有序列:

fib(1000);
console.log(fib.cache);

Answer 5

另一个答案是使用es6 生成器功能.

function* fib() {
  var current = a = b = 1;

  yield 1;

  while (true) {
    current = b;

    yield current;

    b = a + b;
    a = current;
  }
}

sequence = fib();
sequence.next(); // 1
sequence.next(); // 1
sequence.next(); // 2
// ...

Answer 6

你没有给一个值z,所以你期望y=z;做什么？同样,你从来没有真正从数组中读取.看起来你正在尝试两种不同方法的组合......尝试完全摆脱阵列,并使用:

// Initialization of x and y as before

for (i = 2; i <= 10; i++)
{
    alert(x + y);
    z = x + y;
    x = y;
    y = z;
}

编辑:在我添加此答案后,OP更改了代码.最初循环的最后一行是 y = z; - 如果你z按照我的代码进行了初始化,这是有意义的.

如果稍后需要该数组,那么显然需要进行填充 - 但是否则,我给出的代码应该没问题.

Answer 7

另一种简单的方法来实现这一点：

function fibonacciGenerator(n) {
  // declare the array starting with the first 2 values of the fibonacci sequence
  // starting at array index 1, and push current index + previous index to the array
  for (var fibonacci = [0, 1], i = 2; i < n; i++) 
fibonacci.push(fibonacci[i-1] + fibonacci[i - 2])

  return fibonacci
}

console.log(  fibonacciGenerator(10)  )

Answer 8

黄金比例"phi"^ n/sqrt(5)对于n的斐波那契是渐近的,如果我们将该值向上舍入,我们确实得到了斐波纳契值.

function fib(n) {
    let phi = (1 + Math.sqrt(5))/2;
    let asymp = Math.pow(phi, n) / Math.sqrt(5);

    return Math.round(asymp);
}

fib(1000); // 4.346655768693734e+208 in just 0.62s

与基于递归的解决方案相比,这在大数字上运行得更快.

Answer 9

function fib(n) {
  if (n <= 1) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

fib(10); // returns 55

Answer 10

斐波那契 1,000 ... 10,000 ... 100,000

\n

当尝试计算大斐波那契数时，一些答案会遇到问题。其他人则使用 phi 来近似数字。这个答案将向您展示如何计算精确的的大斐波那契数，而不会遇到 JavaScript 浮点实现设置的限制。

\n

下面，我们在几毫秒内生成前 1,000 个斐波那契数。稍后我们会做 100,000 个！

\n

const { fromInt, toString, add } =\n  Bignum\n\nconst bigfib = function* (n = 0)\n{\n  let a = fromInt (0)\n  let b = fromInt (1)\n  let _\n  while (n >= 0) {\n    yield toString (a)\n    _ = a\n    a = b\n    b = add (b, _)\n    n = n - 1\n  }\n}\n\nconsole.time (\'bigfib\')\nconst seq = Array.from (bigfib (1000))\nconsole.timeEnd (\'bigfib\')\n// 25 ms\n\nconsole.log (seq.length)\n// 1001\n\nconsole.log (seq)\n// [ 0, 1, 1, 2, 3, ... 995 more elements ]\n

\n

让我们看看第 1000 个斐波那契数

\n

console.log (seq [1000])\n// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875\n

\n

10,000

\n

这个解决方案的扩展性非常好。我们可以在 2 秒内计算出前 10,000 个斐波那契数。此时序列中的数字长度已超过 2,000 位 \xe2\x80\x93，远远超出了 JavaScript 浮点数的容量。尽管如此，我们的结果仍然包括精确的值，而没有进行近似值。

\n

console.time (\'bigfib\')\nconst seq = Array.from (bigfib (10000))\nconsole.timeEnd (\'bigfib\')\n// 1877 ms\n\nconsole.log (seq.length)\n// 10001\n\nconsole.log (seq [10000] .length)\n// 2090\n\nconsole.log (seq [10000])\n// 3364476487 ... 2070 more digits ... 9947366875\n

\n

当然，所有这些魔力都发生在 中Bignum，我们现在将分享。直观了解我们将如何设计Bignum，请回想一下您小时候如何使用笔和纸添加大数字......

\n

  1259601512351095520986368\n+   50695640938240596831104\n---------------------------\n                          ?\n

\n

您从右到左添加每一列，当一列溢出到两位数时，请记住将 1 转移到下一列......

\n

                 ... <-001\n  1259601512351095520986368\n+   50695640938240596831104\n---------------------------\n                  ... <-472

\n

从上面我们可以看到，如果有两个 10 位数字，则需要大约 30 次简单加法（每列 3 次）才能计算出答案。这就是我们将要设计的方式Bignum工作的方式

\n

const Bignum =\n  { fromInt: (n = 0) =>\n      n < 10\n        ? [ n ]\n        : [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]\n        \n  , fromString: (s = "0") =>\n      Array.from (s, Number) .reverse ()\n      \n  , toString: (b) =>\n      Array.from (b) .reverse () .join (\'\')\n      \n  , add: (b1, b2) =>\n    {\n      const len = Math.max (b1.length, b2.length)\n      let answer = []\n      let carry = 0\n      for (let i = 0; i < len; i = i + 1) {\n        const x = b1[i] || 0\n        const y = b2[i] || 0\n        const sum = x + y + carry\n        answer.push (sum % 10)\n        carry = sum / 10 >> 0\n      }\n      if (carry > 0) answer.push (carry)\n      return answer\n    }\n  }\n

\n

我们将运行一个快速测试来验证上面的示例

\n

const x =\n  fromString (\'1259601512351095520986368\')\n\nconst y =\n  fromString (\'50695640938240596831104\')\n\nconsole.log (toString (add (x,y)))\n// 1310297153289336117817472\n

\n

现在是完整的程序演示。展开它以在您自己的浏览器中计算精确的第 10,000 个斐波那契数！注意，结果与wolfram alpha提供的答案相同

\n

\r\n

\r\n

const { fromInt, toString, add } =\n  Bignum\n\nconst bigfib = function* (n = 0)\n{\n  let a = fromInt (0)\n  let b = fromInt (1)\n  let _\n  while (n >= 0) {\n    yield toString (a)\n    _ = a\n    a = b\n    b = add (b, _)\n    n = n - 1\n  }\n}\n\nconsole.time (\'bigfib\')\nconst seq = Array.from (bigfib (1000))\nconsole.timeEnd (\'bigfib\')\n// 25 ms\n\nconsole.log (seq.length)\n// 1001\n\nconsole.log (seq)\n// [ 0, 1, 1, 2, 3, ... 995 more elements ]\n

\r\n

\r\n

\r\n

\n

100,000

\n

我只是好奇这个小脚本能走多远。似乎唯一的限制就是时间和内存。下面，我们不进行近似计算前 100,000 个斐波那契数。序列中此时的数字长度超过 20,000 位，哇！需要 3.18 分钟才能完成，但结果仍然与Wolfram alpha的答案相符

\n

console.time (\'bigfib\')\nconst seq = Array.from (bigfib (100000))\nconsole.timeEnd (\'bigfib\')\n// 191078 ms\n\nconsole.log (seq .length)\n// 100001\n\nconsole.log (seq [100000] .length)\n// 20899\n\nconsole.log (seq [100000])\n// 2597406934 ... 20879 more digits ... 3428746875\n

\n

大整型

\n

JavaScript 现在原生支持BigInt。这允许非常快速地计算大整数 -

\n

\r\n

\r\n

console.log (seq [1000])\n// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875\n

\r\n

console.time (\'bigfib\')\nconst seq = Array.from (bigfib (10000))\nconsole.timeEnd (\'bigfib\')\n// 1877 ms\n\nconsole.log (seq.length)\n// 10001\n\nconsole.log (seq [10000] .length)\n// 2090\n\nconsole.log (seq [10000])\n// 3364476487 ... 2070 more digits ... 9947366875\n

\r\n

\r\n

\r\n

\n