• C

# fibonacci optimal

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.

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

Commented:
It is valid to do
ptr2[0] = 'F';
is may or may not be valid to do
ptr1[0] = 'F';
it is valid to say
it is not valid to say
0

Commented:
0

Author Commented:
hi ozo,
Can you give help me in detail? I am think of array now.
Thanks.
0

Commented:
0

Author Commented:
i wonder 1 thing.
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.
0

Commented:
Given a number n, you store its fib value at index n ... e.g.
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
0

Author Commented:
however, how big is the array?
0

Author Commented:
I really want to make the program work dynamiccally. So i don't know know to deal with the array. If you can, please help me on coding. Thanks.
0

Commented:
If the user can enter any number less than 100 then array[100] would be big enough.
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.
0

Commented:
What do you mean by wanting the program to work dynamically?

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.
0

Author Commented:
Thanks sunnycoder and ozo. I start coding now. By the way,
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.

0

Author Commented:
oh ozo,