Fibonacci sequence in Javascript - Stack Overflow

admin管理员组

文章数量:1339470

I am very new to programming in general and am having a hard time understanding this Fibonacci sequence example:

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

On the first iteration, index 2 is equal to 1, simple enough. But, when I try the second iteration with i = 3, I get:

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

Where am I going wrong with my thinking? So far I have:

var fib = [0,1,1,3]

which I know is not correct.

I am very new to programming in general and am having a hard time understanding this Fibonacci sequence example:

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

On the first iteration, index 2 is equal to 1, simple enough. But, when I try the second iteration with i = 3, I get:

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

Where am I going wrong with my thinking? So far I have:

var fib = [0,1,1,3]

which I know is not correct.

• javascript
• fibonacci

Share Improve this question Follow edited Sep 27, 2012 at 23:46 murgatroid99 20.3k1010 gold badges6363 silver badges9898 bronze badges asked Sep 27, 2012 at 23:42 KMcAKMcA 1,21311 gold badge1212 silver badges2121 bronze badges 5

• I'm not really sure what you are asking. Are you trying to understand a working program or fix a program that does not work? – murgatroid99 Commented Sep 27, 2012 at 23:45
• is this your homework ? or just hobby ? – c69 Commented Sep 27, 2012 at 23:46
• I know the code works, but when I go through the steps on paper, my logic is not following what the answer should be. – KMcA Commented Sep 27, 2012 at 23:46
• You are just confusing yourself. How did you get [0, 1, 1, 3] on paper? The equality relationships you give are meaningless really, it's the same as writing 3 = 3 - 1 + 1 = 3. – Jon Commented Sep 27, 2012 at 23:48
• Tip: In browsers, you can use the debugger; statement in your code to "pause" it and get an interactive mode where you can step through the code line-by-line and examine what happens. – Borgar Commented Sep 27, 2012 at 23:58

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 7

When you are reasoning about the code, you make the jump from fib[3] = fib[2] + fib[1] to fib[3] = fib[3]. This happens to be a transformation that results in a correct statement, but it is not how it works. This code is adding the value at index 2 to the value at index 1. That is not the same as taking the value at index 3. The way this reasoning should work is as follows:

You start with fib = [0, 1]. Then in the first iteration of the loop you have fib[2] = fib[1] + fib[0]. This means that you add the value at index 0 (which happens to be 0) to the value at index 1 (which happens to be 1) to get the value that you put at the end of the array (1). Then in the second iteration, you do a similar thing, adding the value at index 1 (still 1) to the value at index 2 (also 1) to get 2, which goes at the end of the array. This continues, and at each iteration you add together the last two values in the array to get the next value.

In JavaScript, when using an array like fib, fib[i] refers to the ith value in this array, counting from 0. So fib[0] is the first element in the array, fib[1] is the second element in the array, and so on.

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

You are adding the indexes up not the value in the array the index points to

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = 1 + 1;

[0,1,1,2]

fib[0] = 0
fib[1] = 1
fib[2] = 1
fib[3] will equal 2

So next iteration

fib[4] = fib[4-1] +fib[4-2]
fib[4] = fib[3] + fib[2]
fib[4] = 1 + 2
fib[4] = 3

You're code is fine. Ran this and got the proper output:

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

Console: 0,1,1,2,3,5,8,13,21,34

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

So your problem is in line #2. The numbers in the [] brackets are indices, which state which part of an array should be read. When the + operator is applied, they are not added, but instead the two fib[2] and fib[1] are evaluated to their corresponding data, meaning they are evaluated to 1 and 1, which then are added together to 2.

I hope this is understandable. If not, just ask in the ments.

Well, why did you do this in your calculation

fib[3] = fib[2] + fib[1]
fib[3] = fib[3]

When you're dealing with arrays the value at the index represented by the sum of the indices is not equal to the sum of the values of the array at those indices.

To put it simply, you can't add the numbers within the square brackets on paper. Its like having two wallets with 5 and 15 dollars each in them. You can't say you have 15 dollars because 1+1 is two and you'll look into the second wallet. You'll add the 'contents' of the wallets instead to find the total monetary amount. Which is 20

Implementation with array reduce()

var a = [3,2,3,6,2,3,4];
var fib  = a.reduce(function(sum, v, i) {
    return i === 0 ? sum.concat(v) : sum.concat(v + sum[i-1]);
},[]);
console.log( fib  );

ES6:

var fibES6 = a.reduce(
    (sum, v, i) => i === 0 ? sum.concat(v) : sum.concat(v + sum[i-1])
, []);
console.log( fibES6  );

本文标签： Fibonacci sequence in JavascriptStack Overflow