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

 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.
valleytechAsked:
Who is Participating?
 
ozoConnect With a Mentor 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
ptr1 = "BAD";
it is not valid to say
ptr2 = "BAD";
0
 
valleytechAuthor Commented:
hi ozo,
 Can you give help me in detail? I am think of array now.
 Thanks.
0
Improve Your Query Performance Tuning

In this FREE six-day email course, you'll learn from Janis Griffin, Database Performance Evangelist. She'll teach 12 steps that you can use to optimize your queries as much as possible and see measurable results in your work. Get started today!

 
ozoCommented:
Does the link not answer your question?
0
 
valleytechAuthor 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
 
sunnycoderConnect With a Mentor 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
 
valleytechAuthor Commented:
however, how big is the array?
0
 
valleytechAuthor 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
 
ozoCommented:
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
 
sunnycoderCommented:
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
 
valleytechAuthor 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
 
valleytechAuthor Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.