Posts Tagged Puzzles

Fibonacci

If you were given a task to compute the nth Fibonacci number, how would you do it?

You would go straight away and write a recursive function right?

public static int getNumberRecurse(int n) {
    if (n == 0 | n == 1) {
       return 1;
    } else {
       return getNumberRecurse(n - 1) + getNumberRecurse(n - 2);
    }
 }

elapsed for n=30: 31 ms

elapsed for n=40: 3016 ms

Well think again. Because there might be a better way of doing it.

public static int getNumberLoop(int n) {
if (n == 0 | n == 1) {
return 1;
} else {
int[] fib = new int[n + 1];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n]; } } [/sourcecode] elapsed for n=100000: 31 ms If we compare the elapsed time (in ms) between the two functions, we can clearly see which one is better. Anyway, I've found an invaluable book called Algorithms from where I got the example above.

I know a lot of programmers (myself included) who are easily satisfied with a workable solution rather than an efficient one.

I hope someday (with enough time and practice) I can be an expert on this topic too.

Advertisements

Leave a Comment