How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

Friday, June 8, 2012

Print all Fibonacci numbers

Problem:  Print all the Fibonacci numbers from 1 to n using the fibNum() from two problems ago function.

void printFib(int n) {...}

Solution:  This is a relatively simple problem that appears straight forward.  It would be asked early on to simply screen out people.  It is straight forward as:

  int i;

  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;

    for (=0; i < n; i++) 

        printf("%d\n", fibNum(i));
} 



Well, that's it.  Not too much to it.  Let's analyze the algorithmic run time.  Since we know fibNum is O(n), then we could have to call fibNum n times, this is O(n^2).  Not great, and we know that we're doing this slowly.

Next problem is to do this in linear time.

/* Please let me know if you find any bugs to this.  Thx, Noah */