生成斐波那契数列

Question

生成斐波那契数列

48

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;
}

我尝试生成一个简单的斐波那契数列，但没有输出。

请问有人能告诉我出了什么问题吗？

- methuselah

52个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HynekS · Answer 1

我喜欢的是，在JS中创建斐波那契数列的方法有很多种。我会尝试复制其中一些方法。目标是将序列输出到控制台（如{n: 6, fiboNum: 8}）

好老的闭包方法

// The IIFE form is purposefully omitted. See below.

const fiboGenClosure = () => {
  let [a, b] = [0, 1];
  let n = 0;
  return (fiboNum = a) => {
    [a, b] = [b, a + b];
    return {
      n: n++,
      fiboNum: fiboNum
    };
  };
}

// Gets the sequence until given nth number. Always returns a new copy of the main function, so it is possible to generate multiple independent sequences.

const generateFiboClosure = n => {
  const newSequence = fiboGenClosure();
  for (let i = 0; i <= n; i++) {
    console.log(newSequence());
  }
}

generateFiboClosure(21);

精美的ES6生成器

与上述闭包模式类似，利用生成器函数和for..of循环的优点。

// The 'n' argument is a substitute for index.

function* fiboGen(n = 0) {
  let [a, b] = [0, 1];
  while (true) {
    yield [a, n++];
    [a, b] = [b, a + b];
  }
}

// Also gives a new sequence every time is invoked.

const generateFibonacci = n => {
  const iterator = fiboGen();
  for (let [value, index] of iterator) {
    console.log({
      n: index,
      fiboNum: value
    });
    if (index >= n) break;
  }
}

generateFibonacci(21);

尾调用递归

尾调用递归是一个有些棘手的问题，因为即使到了2018年末，尾调用优化仍然是一个问题。但老实说——如果你不使用任何聪明的技巧允许默认的JS引擎使用非常大的数字，它会变得昏头转向，并声称下一个斐波那契数在第1477次迭代时为“无穷大”。栈可能在第10,000次迭代左右溢出（这主要取决于浏览器、内存等等）。可以通过try... catch语句块来缓解，或者检查是否已达到“无穷大”。

const fibonacciRTC = (n, i = 0, a = 0, b = 1) => {
  console.log({
    n: i,
    fibonacci: a
  });
  if (n === 0) return;
  return fibonacciRTC(--n, ++i, b, a + b);
}

fibonacciRTC(21)

如果我们不考虑console.log，只返回一个数字，它可以被写成一行代码：

const fibonacciRTC2 = (n, a = 0, b = 1) => n === 0 ? a : fibonacciRTC2(n - 1, b, a + b);

console.log(fibonacciRTC2(21))

重要提示！

阅读此mathIsFun文章后，我发现斐波那契数列也适用于负数！我尝试按照上面的递归尾调用形式进行实现：

const fibonacciRTC3 = (n, a = 0, b = 1, sign = n >= 0 ? 1 : -1) => { 
  if (n === 0) return a * sign;
    return fibonacciRTC3(n - sign, b, a + b, sign);
}

console.log(fibonacciRTC3(8)); // 21
console.log(fibonacciRTC3(-8)); // -21

- Samuel Pinto · Answer 2

您可以获取一些缓存来加速算法...

var tools = {

    fibonacci : function(n) {
        var cache = {};

        // optional seed cache
        cache[2] = 1;
        cache[3] = 2;
        cache[4] = 3;
        cache[5] = 5;
        cache[6] = 8;

        return execute(n);

        function execute(n) {
            // special cases 0 or 1
            if (n < 2) return n;

            var a = n - 1;
            var b = n - 2;

            if(!cache[a]) cache[a] = execute(a);
            if(!cache[b]) cache[b] = execute(b);

            return cache[a] + cache[b];
        }
    }
};

- sqram · Answer 3

3

如果使用ES2015：

const fib = (n, prev = 0, current = 1) => n 
  ? fib(--n, current, prev + current) 
  : prev + current

console.log( fib(10) )

- sqram

1

可以轻松地重写为箭头函数：var fib = (n, prev = 0, current = 1) => !n ? prev + current : fib(--n, current, prev+current); 似乎显示的是第n+3个项目而不是第n个项目。将测试更改为!(n-3)即可解决此问题；但是，这意味着fib(0)，fib(1)和fib(2)无法正常工作。 - Roger_S

为了构建准确的集合，即0、1、1、2、3、5...需要添加一个条件。

function fib(n, prev = 0, current = 1) {
    if (n > 2) {
        return fib(--n, current, prev+current);
    }
    if (n === 2) {
        return prev + current;
    }
    return n;
}

- radzserg

- Sparkida · Answer 4

一种快速获取约75的方法

ty @geeves for the catch, I replaced Math.floor for Math.round which seems to get it up to 76 where floating point issues come into play :/ ... either way, I wouldn't want to be using recursion up and until that point.

/**
 * Binet Fibonacci number formula for determining
 * sequence values
 * @param {int} pos - the position in sequence to lookup
 * @returns {int} the Fibonacci value of sequence @pos
 */

var test = [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026];
var fib = function (pos) {
        return Math.round((Math.pow( 1 + Math.sqrt(5), pos) 
            - Math.pow( 1 - Math.sqrt(5), pos)) 
            / (Math.pow(2, pos) * Math.sqrt(5)));
    };

/* This is only for the test */
var max = test.length,
    i = 0,
    frag = document.createDocumentFragment(),
    _div = document.createElement('div'),
    _text = document.createTextNode(''),
    div,
    text,
    err,
    num;
for ( ; i < max; i++) {
    div = _div.cloneNode();
    text = _text.cloneNode();
    num = fib(i);
    if (num !== test[i]) {
        err = i + ' == ' + test[i] + '; got ' + num;
        div.style.color = 'red';
    }
    text.nodeValue = i + ': ' + num;
    div.appendChild(text);
    frag.appendChild(div);
}
document.body.appendChild(frag);

- dekarpaulvictor · Answer 5

如果您需要轻松地构建斐波那契数列列表，可以使用数组解构赋值来简化操作：

function fibonacci(n) {
  
  let fibList = [];
  let [a, b] = [0, 1]; // array destructuring to ease your pain

  while (a < n) {
    fibList.push(a);
    [a, b] = [b, a + b]; // less pain, more gain
  }
  
  return fibList;
}

console.log(fibonacci(10)); // prints [0, 1, 1, 2, 3, 5, 8]

- galarius · Answer 6

对于负整数，也有Binet公式的推广：

static float phi = (1.0f + sqrt(5.0f)) / 2.0f;

int generalized_binet_fib(int n) {
   return round( (pow(phi, n) - cos(n * M_PI) * pow(phi, -n)) / sqrt(5.0f) );
 }

 ...

 for(int i = -10; i < 10; ++i)
    printf("%i ", generalized_binet_fib(i));

- Vijay Jagdale · Answer 7

另一种实现方式，虽然是递归的，但非常快速，并使用单个内联函数。它在第80个序列（以及所有其他算法）时达到了JavaScript 64位数字精度限制：例如，如果您想要第78个术语（78放在最后一个括号中）：

(function (n,i,p,r){p=(p||0)+r||1;i=i?i+1:1;return i<=n?arguments.callee(n,i,r,p):r}(78));

将返回：8944394323791464

这是向后兼容的，一直到 ECMASCRIPT4 - 我已经在 IE7 上测试过了，它可以工作！

- evoldoc · Answer 8

不需要慢速循环，生成器或递归函数(有缓存或无缓存)。这里是一个使用Array和reduce的快速一行代码。

ECMAScript 6:

var fibonacci=(n)=>Array(n).fill().reduce((a,b,c)=>a.concat(c<2?c:a[c-1]+a[c-2]),[])

ECMAScript 5:

function fibonacci(n){
    return Array.apply(null,{length:n}).reduce(function(a,b,c){return a.concat((c<2)?c:a[c-1]+a[c-2]);},[]);
}

在 Windows 10 中使用 Chrome 59 进行测试：

fibonacci(10); // 0 ms -> (10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

JavaScript可以处理最大为1476的数字，达到Infinity之前。

fibonacci(1476); // 11ms -> (1476) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]

- AKHIL · Answer 9

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
        <title>fibonacci series</title>
        <script type="text/javascript">
                function generateseries(){
                    var fno = document.getElementById("firstno").value;
                    var sno = document.getElementById("secondno").value;
                    var a = parseInt(fno);
                    var result = new Array();
                    result[0] = a;
                    var b = ++fno;
                    var c = b;
                    while (b <= sno) {  
                    result.push(c);
                    document.getElementById("maindiv").innerHTML = "Fibonacci Series between "+fno+ " and " +sno+ " is " +result;
                        c = a + b;
                        a = b;
                        b = c;
                    }
                }
                function numeric(evt){
                    var theEvent = evt || window.event;
                    var key = theEvent.keyCode || theEvent.which;
                    key = String.fromCharCode(key);
                    var regex = /[0-9]|\./;
                    if (!regex.test(key)) {
                        theEvent.returnValue = false;
                        if (theEvent.preventDefault) 
                            theEvent.preventDefault();
                    }
                }

            </script>
        <h1 align="center">Fibonacci Series</h1>
    </head>
    <body>
        <div id="resultdiv" align="center">
        <input type="text" name="firstno" id="firstno" onkeypress="numeric(event)"><br>
        <input type="text" name="secondno" id="secondno" onkeypress="numeric(event)"><br>
        <input type="button" id="result" value="Result" onclick="generateseries();">
        <div id="maindiv"></div>
        </div>
    </body>
</html>

- Steve M. Romain · Answer 10

我知道这是一个有点老的问题，但是我意识到这里的许多答案都在使用for循环而不是while循环。

有时候，while循环比for循环更快，所以我想贡献一些在while循环中运行斐波那契数列的代码！使用适合自己需求的任何方法。

function fib(length) {
  var fibArr = [],
    i = 0,
    j = 1;
  fibArr.push(i);
  fibArr.push(j);
  while (fibArr.length <= length) {
    fibArr.push(fibArr[j] + fibArr[i]);
    j++;
    i++;
  }
  return fibArr;
};
fib(15);