Ben Reichelt's Weblog

CSci 101 Part II

This post has moved to a new server.

View it at:

CSci 101 Part II

(http://benreichelt.net/blog/2005/1/20/CSci-101-Part-II/)

Published Jan 20 2005, 08:03 AM by breichelt

Comments

Darrell said:

The first thing I would try is to make an array of size n when fibo(n) is called. Then if the value was in the array, return it, else calculate it recursively (which will also do the lookup).

That way it should be on the O(n), right? I always get my big-O notation whacked. ;)

# January 20, 2005 3:29 AM

ben said:

Darrell, you keep ruining my fun!! ;) Yes, you're right on about the array, thanks for reading!

# January 20, 2005 4:16 AM

Darrell said:

Sorry. I won't answer next time! :)

# January 20, 2005 6:33 AM

Scot Boyd said:

I thought about the array, but decided I'd rather try and use tail calls, so that I wouldn't have to create a data structure:

int fibofact(int ordinal, int* pfactor)
{
if (ordinal == 1)
{
*pfactor = 0; return 0;
}
if (ordinal == 2)
{
*pfactor = 0; return 1;
}
int myfactor = 0;
*pfactor = fibofact(ordinal-1, &myfactor);
return *pfactor + myfactor;
}
int fibo(int ordinal)
{
if (ordinal == 1)
return 0;
if (ordinal == 2)
return 1;
int myfactor = 0;
return fibofact(ordinal-1, &myfactor)+myfactor;
}

# January 20, 2005 9:29 AM