Solved

fibonacci optimal

Posted on 2006-05-26
327 Views
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.
0
Question by:valleytech

LVL 84

Expert Comment

0

Author Comment

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

LVL 84

Expert Comment

0

Author Comment

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

LVL 45

Assisted Solution

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 Comment

however, how big is the array?
0

Author Comment

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

LVL 84

Expert Comment

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

LVL 45

Expert Comment

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 Comment

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

LVL 84

Accepted Solution

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

Author Comment

oh ozo,
One of my friend just asked me to help him to write a function return to about 16 byte aligned.
I have no idea what is 16 byte aligned. Could you please explain for me. Thanks.
0

Join & Write a Comment Already a member? Login.

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

755 members asked questions and received personalized solutions in the past 7 days.

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

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!