Mathworks "Cody"‎ > ‎Problems 10-19‎ > ‎

Problem 12

Calculate the nth Fibonacci number.

Given n, return f where f = fib(n) and f(1) = 1, f(2) = 1, f(3) = 2, ...

Examples:

 Input  n = 5
 Output f is 5
 Input  n = 7
 Output f is 13

Solution

So for those of you who follow my project euler solutions, we've already solved the fibonacci problem. I just used the same code to solve this problem. The coding took all of 2 seconds and it worked (didn't even code inside matlab, just entered the solution in directly).

The first run through gave me a size of 46 and a leading solution of only 16. I am aware that there is a formula to directly compute the nth term in the fibonacci sequence so I figured I'd cheat and look it up on Wikipedia. Sure enough, there is. I included both codes, but honestly there is much more to learn from the looping method than the direct formula route.

Code

function f = fib(n)

  f(1) = 1;  % We have to prime our code with the first two values of fib

  f(2) = 1;  % as we start the loop at f(3) = f(1) + f(2), not really cheating

             % and it makes f true for values of n=1 or 2 (robustness).

    for i = 2 : n-1

      f(i+1) = f(i-1) + f(i);  % For optimization sake, we should have prelocated

                               % f with f = zeros(n). For our sake, we care

                               % about size and not about speed so I

                               % didn't. We save each value of the fib to

                               % an indexed value within f to not only

                               % calculate the next number but to speed it

                               % up as well (eliminates repeat calculation)

    end

    f = f(n);

end

using Wikipedia:

function 

    f = fib(n) f = floor((1.6180339887^n + 0.618033988768953^n)/(1.6180339887+0.618033988768953)); 

end

Size for Loop: 46

Size for equation: 24

Recommendations

So it's still not quite 16, maybe if we could somehow remove the floor command we could knock it down a few, but it's not exactly equal and we use floor to round the result down to the correct value. Let me know how you guys got it even lower!

Follow me!
Comments