Solved

Posted on 2006-05-26

Hi ,

I have the fibonacci function like this:

long Fib(int n)

{

if ( n == 0)

return 0;

else if ( n ==1 || n ==2)

return 1;

else return Fib(n-1) + Fib(n-2);

}

I converted it to the loop function

int Fib( int n)

{

if ( n == 0)

return 0;

else if ( n == 1 || n == 2)

return 1;

else

{

int x1=1;

int x2=1;

int x3= 2;

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

{

x3= x1+x2;

x1= x2;

x2= x3;

}

return x3;

}

}

Both functions work. However I want to optimize them. WHen user give a number such as number 5, they need to calculate from fib(1) to fib(5). After that, user give such as nunmber 8, they need to calculate from fib(1) to fib(8).

It's a waste since previous time they have fib(5) already. So they need to calculate only from fib(5) to fib(8) only.

I am think of that way to optimize both function. Please help.

PS: user can enter any number less than 100. and user can enter randomly such as 20, 10, 15 as long as user wants.

I have the fibonacci function like this:

long Fib(int n)

{

if ( n == 0)

return 0;

else if ( n ==1 || n ==2)

return 1;

else return Fib(n-1) + Fib(n-2);

}

I converted it to the loop function

int Fib( int n)

{

if ( n == 0)

return 0;

else if ( n == 1 || n == 2)

return 1;

else

{

int x1=1;

int x2=1;

int x3= 2;

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

{

x3= x1+x2;

x1= x2;

x2= x3;

}

return x3;

}

}

Both functions work. However I want to optimize them. WHen user give a number such as number 5, they need to calculate from fib(1) to fib(5). After that, user give such as nunmber 8, they need to calculate from fib(1) to fib(8).

It's a waste since previous time they have fib(5) already. So they need to calculate only from fib(5) to fib(8) only.

I am think of that way to optimize both function. Please help.

PS: user can enter any number less than 100. and user can enter randomly such as 20, 10, 15 as long as user wants.

12 Comments

when you store the value to array, which index you will store at? Because you need to access in later on as you calculate another fib number. that's why i can't code it now.

fib[1]=1;

fib[2]=1;

fib[3]=2;

What you can do is initialize all elements of the array fib[] to some invalid value such as 0.

Next initialize index 1 and 2 to value 1 as shown above.

Next time that you need to calculate fib of a number you simply store the value at index number ... e.g. as per the code shown at the link posted by ozo, this is how fib will be calculated ...

calculate_fib(5)

{

if (fib[5] !=0) //we have this value .. had we not calculated it before, this value would have been 0 - the initial value

return fib[5];

fib[5] = calculate_fib(4) + calculate_fib(3);

}

As you can see this would recursively calculate the fib value for 5 to 3 (2 and 1 are defined) and store the respective values at the index value that is same as the number for which value was calculated....

Later if you need to determine fib value for number n, all you need to do is determine if fib[n]!=0 ... If this condition is true you already have the value .. if it is false, then it will start calculating the value down to the greatest number whose value has not been calculated before.

If all this confused you a bit, then I strongly recommend that you take a pen and paper and actually trace the recursive calls for 5 and 8, in that order.

Cheers!

sunnycoder

Fib(100) would overflow a 64 bit int, so it may not be much use to go hiher anyway.

setting the array to all 0 is still O(size), but you given another array you can initialize in O(1) with O(1) overhead per access.

Ozo's link explains the concepts and I have tried to clarify a few things ... If you do not understand something in specific ask here ... However, we cant code it for you ... You will have to start coding and we can help you if you are facing some kind of errors.

char *ptr1= "GOOD"

char ptr2[]="GOOD"

I can see only 1 difference. ptr1 points to string "GOOD", and ptr2 is array that contains string "GOOD". Are there any other differences between them? Thanks.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**23** Experts available now in Live!