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;
}
我尝试生成一个简单的斐波那契数列，但没有输出。
请问有人能告诉我出了什么问题吗？
生成斐波那契数列
48
- methuselah
52个回答
88
你从未声明 fib 为一个数组。使用 var fib = []; 来解决这个问题。
此外，你从未修改过 y 变量，也没有使用过它。
下面的代码更有意义，而且不会创建未使用的变量：
var i;
var fib = [0, 1]; // Initialize array!
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]);
}- Rob W
2
8不要忘记输出初始的0和1，即斐波那契数列中的前两个数字。 - tronman
2我会这样改进它：var sequence = [0,1];for(var i = 0; i < 10-2; i++){
sequence.push(sequence[i]+sequence[i+1]);
}console.log(sequence); - obinoob
76
根据Interview Cake的问题，数列为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)-'
请注意，尽管这个解决方案可行，但效率不是很高。
- Alex Cory
10
2尽管这不可扩展 - Zach Smith
14这个ASCII艺术品是我所见过的最好的展示“this+1”逻辑的例子。 - Deprecated Darren
2不管多贵，尝试先处理前500个值！ - obinoob
这不是回答“我的代码有什么问题？”的问题。这只是一些没有解释的其他代码。它也是最糟糕的实现之一（使用递归）。 - melpomene
很明显，你没有阅读“像这样考虑”的部分。此外，针对你所说的“这不是一个答案”，似乎更多的人因为其他评论赞扬了这个答案而不同意你的观点。如果这不是答案，为什么其他人都提供了代码，而你又为什么没有评论其他帖子......？然而，我会同意递归并不是最好的解决方案，尽管它非常简洁。 - Alex Cory
显示剩余5条评论
26
另一种答案是使用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
// ...
- Dimitris Zorbas
1
2我认为它应该以
0 开始。 - vsync23
这是一个简单的函数，使用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 ]
- irth
2
fib(10) 应该等于 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55。 - Alex Coryfib(0) 返回 [0,1]。 - Sheelpriy
20
你本应该在一开始就将变量
如果使用数组来存储斐波那契数列，就不需要其他辅助变量（如
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];
然后，在调用 fibonacci 函数之后，你可以在 fib.cache 字段中找到整个数列：
fib(1000);
console.log(fib.cache);
- gion_13
17
黄金比例"phi"^n/√5渐近于斐波那契数列的第n个数，若将该值四舍五入得到的结果，正是斐波那契数列的第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 a few milliseconds
与基于递归的解决方案相比，此方法在处理大数字时运行速度更快。
- Biereagu Sochima
4
很酷 :) 为了提高效率，我会在函数外预先计算
Math.sqrt(5) 和 phi。作为参考，我已经测试了 fib(7)，并且完美运行。使用说明：fib(0) = 0。 - Akseli Palén是的，在函数外预先计算phi会使它更快，我只是为了演示才这样做。 - Biereagu Sochima
这是计算斐波那契数列最有效的方法，但它只适用于不太大的值。例如，对于fib(77)，它会给出错误的值。它给出的是5527939700884755，但实际上应该是5527939700884757。 - WebBrother
显然，这个解决方案在多年前就已经发布在这里了。 - vsync
10
你没有给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，那么这是有意义的。
如果数组以后还需要使用，那么显然仍然需要填充 - 但否则，我给出的代码应该是可以的。
- Jon Skeet
2
投票否决，因为用户从未假定y=z表达式。我相信用户想要稍后使用该数组。 - Marian Bazalik
4请看编辑之前的问题……并不是我的错，原帖发布者在我指出问题后修复了代码 :) - Jon Skeet
8
另一种实现此目的的简单方法是：
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) )- Mezzanine
3
我的代码有真正的问题吗？尽管我只是提供了一个替代方案，但我还是和其他几个人一样被踩了。如果有下投票的原因，我希望能够看到一篇帖子来解释，因为这将成为改进答案的机会，如果它确实存在问题的话。 - Mezzanine
喜欢这个解决方案！我认为这是迄今为止最干净的。 - vsync
1喜欢这个解决方案！我认为这是迄今为止最干净的。唯一的问题是
listFibonacci(0)和listFibonacci(1)。 - vsync5
斐波那契数列 1,000 ... 10,000 ... 100,000
一些解决方案在计算大型斐波那契数时会遇到问题。另一些则使用黄金分割率逼近数字。本答案将向您展示如何计算一系列精确的大型斐波那契数，而不会受限于 JavaScript 浮点实现所设定的限制。
下面，我们在几毫秒内生成了前 1,000 个斐波那契数。稍后，我们将计算前 100,000 个斐波那契数！
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (1000))
console.timeEnd ('bigfib')
// 25 ms
console.log (seq.length)
// 1001
console.log (seq)
// [ 0, 1, 1, 2, 3, ... 995 more elements ]
让我们来看看第1000个斐波那契数
console.log (seq [1000])
// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
10,000
这种解决方案具有很好的可扩展性。我们可以在不到2秒钟内计算出前10,000个斐波那契数。在这个序列的这一点上，数字超过了2,000位 - 远远超出了JavaScript浮点数的容量。尽管如此，我们的结果包括了精确的值，而没有做出近似。
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875
当然，所有这些魔法都发生在Bignum中，我们现在将分享它。为了对我们如何设计Bignum有所感悟，回想一下你小时候用笔和纸相加大数的方法...
1259601512351095520986368
+ 50695640938240596831104
---------------------------
?
您需要从右到左依次相加每一列，当某一列进位时，需要将1进位到下一列...
... <-<b>001</b>
1259601512351095520986368
+ 50695640938240596831104
---------------------------
... <-<b>472</b>从上面可以看出，如果我们有两个10位数，大约需要30次简单的加法（每列3次）来计算答案。这就是我们设计Bignum的工作方式。
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
我们将运行一个快速测试来验证上面的示例。
const x =
fromString ('1259601512351095520986368')
const y =
fromString ('50695640938240596831104')
console.log (toString (add (x,y)))
// 1310297153289336117817472
现在展示一个完整的程序。您可以在自己的浏览器中扩展它以计算精确的第10000个斐波那契数！请注意，结果与 wolfram alpha 提供的答案相同。
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875100,000
我只是好奇这个小脚本能做到什么程度。似乎唯一的限制就是时间和内存。下面，我们不使用近似方法计算前100,000个斐波那契数列的数字。在数列中的这一点上，数字已经超过20,000位了，哇！完成需要3.18分钟，但结果仍然与沃尔夫拉姆阿尔法的答案相匹配。
console.time ('bigfib')
const seq = Array.from (bigfib (100000))
console.timeEnd ('bigfib')
// 191078 ms
console.log (seq .length)
// 100001
console.log (seq [100000] .length)
// 20899
console.log (seq [100000])
// 2597406934 ... 20879 more digits ... 3428746875
BigInt
JavaScript现在原生支持BigInt。这使得计算超大整数非常快速 -
function* fib (n)
{ let a = 0n
let b = 1n
let _
while (n >= 0) {
yield a.toString()
_ = a
a = b
b = b + _
n = n - 1
}
}
console.time("fib(1000)")
const result = Array.from(fib(1000))
console.timeEnd("fib(1000)")
document.body.textContent = JSON.stringify(result, null, 2)body {
font-family: monospace;
white-space: pre;
}- Mulan
5
function fib(n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
fib(10); // returns 55
- Mikhail
2
2虽然这段代码片段可能解决了问题，但包括解释真的有助于提高您的帖子质量。请记住，您正在为未来的读者回答问题，而这些人可能不知道您的代码建议原因。同时，请尽量不要在代码中添加过多的解释性注释，因为这会降低代码和解释的可读性！ - Blue
这不是回答问题“我的代码有什么问题？”的答案。这只是一些没有解释的其他代码。这也是最糟糕的实现之一（使用递归）。 - melpomene
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接