[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 333
  • Last Modified:

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.
0
valleytech
Asked:
valleytech
  • 6
  • 4
  • 2
2 Solutions
 
valleytechAuthor Commented:
hi ozo,
 Can you give help me in detail? I am think of array now.
 Thanks.
0
 
ozoCommented:
Does the link not answer your question?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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
 
sunnycoderCommented:
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
 
ozoCommented:
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:
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 6
  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now