Small Fibonacci number

Question

Given an integer 1 ≤ n ≤ 40 , it is necessary to calculate the n- th Fibonacci number (recall that F [0] = 0, F [1] = 1 and Fn = Fn − 1 + Fn − 2 for n ≥ 2 ).
Sample Input:
  3 
Sample Output:
  2 

I tried to implement this:

function fib(n) { if (n < 1 || n > 40) return 1; var a = [0, 1]; for (var i = 2; i <= n; i++) { a.push(a[i - 1] + a[i - 2]); } return a[n]; }

If you fill the array with Fibonacci numbers by the same condition, it is obtained as follows:

 [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]

But this decision is why wrong. Tell me where I made a mistake. Task taken from Stepic.org.

yes, you try to array the function fib(n) var a = [0,1,1,2 ...]; return a[n];
I don’t know why, but with a[20] I get 6765 , but I should - 10946 .

Answer 1 · 2016-08-15T17:40:39

Perhaps the problem is that if you pass the number 41 to your implementation of the algorithm, which of course should be excluded by the statement of the problem, then it will return 1.

What is more likely, for the Stepic.org platform, maybe you have exceeded the memory limit, since your solution creates an array to store all Fibonacci numbers, and in fact you only need the last two terms of the sequence.

Try a solution using recursion, for example:

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

And if you use this solution?

 function fib(n){ if (n == 1 || n == 2) { return 1; } var prev = 1, current = 1; for(var i = 3; i <= n; i++) { temp = current; current = prev + current; prev = temp; } return current; }

It seems that the problem is not in the algorithm, but in the Stepic.org verification system. The implementation of the algorithm in Python3 has been tested the first time:

 def fib(n): if n == 1 or n == 2: return 1 prev = 1 current = 1 for i in range(3, n + 1): temp = current; current = prev + current; prev = temp; return current

In the absence of optimization, this is about 2 ^ N operations.

ampawd ampawd 2.578 1 golden mark 6 silver marks 23 bronze marks · Answer 2 · 2016-08-15T19:01:21

Here is one of the simplest solutions, linear in time from the number of the fibonacci number, that is, O(n) but the memory is constant O(1) must pass all tests

 function fib(n) { var a = 1, b = 1, c = 0; for (var i = 2; i < n; i++) { c = a + b; b = a; a = c; } return n <= 2 ? (n == 1 || n == 2 ? 1 : 0) : c; } var n = 40; for (var i = 0; i <= n; i++) { console.log("fib("+i+") = " + fib(i)); }

@ Artem weirdly, can you give an example of a test on which my solution does not work?
@Artem because of such a banal and trivial task as it is not particularly desirable to register to login, etc.

Community spirit ♦ one · Answer 3 · 2016-08-15T17:31:37

Perhaps because the Fibonacci number up to 40 is completely removed in a 32-bit integer, so it can be calculated much faster using the Binet analytical formula.

 function fibanchi(n) { return Math.round( ( Math.pow(((1 + Math.sqrt(5)) / 2), n) - Math.pow(((1 - Math.sqrt(5)) / 2), n)) / Math.sqrt(5)); } console.log(fibanchi(40));

it works correctly, but the Stepic platform scolds Failed test #2. Wrong answer
I think you should not use fractional arithmetic until you "pressed", the probability of getting an error here is IMHO higher.
@cheops mathematically exact formula, if not for rounding errors - would give the correct result for any n

Small Fibonacci number

3 answers 3

More articles: