PROBLEM 5 The implementation of terribleFibonacci is TERRIB

* PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a more efficient version of fibonacci. Do not change runFibonacciLoop or runFibonacciSomeValues. To make fibonacci run faster, you want it so that each call to fibonacci(n) computes the fibonacci numbers between 0 and n once, notover and over again.

   *

   * Comment: You will want to use a local variable of type \"long\" rather than

   * type \"int\", for the reasons discussed above.

   *

   * Comment: At some point, your fibonacci numbers might become negative.

   * This is normal and expected.

   * http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length

   * in our systems classes.

   *

   * You may not use any \"fields\" to solve this problem (a field is a variable

   * that is declared \"outside\" of the function declaration --- either before

   * or after).

   */

   public static void runFibonacciLoop () {

       for (int N = 0; N < 100; N++)

           StdOut.format (\"fibonacci(%2d)=%d\ \", N, fibonacci (N));

   }

   public static void runFibonacciSomeValues () {

       StdOut.format (\"fibonacci(%2d)=%d\ \", 13, fibonacci (13));

       StdOut.format (\"fibonacci(%2d)=%d\ \", 7, fibonacci (7));

       StdOut.format (\"fibonacci(%2d)=%d\ \", 21, fibonacci (21));

   }

   public static long fibonacci (int n) {

       return 0; // TODO

   }

Solution

Below is the approach with memoization. the implementation is in c.

===========================================

#include<iostream>
using namespace std;
int F[500];
int fib(int n)
{
   if(n<=1)
   {
       return n;
   }
   if(F[n]!= -1)
   {
       return F[n];
   }
   F[n]= fib(n-1)+fib(n-2);
   return F[n];
}
int main()
{
   for(int i=0;i<500;i++)
   {
       F[i]=-1;
   }
   int n;
   cout<<\"Enter number\";
   cin>>n;
   int result=fib(n);
   cout<<result;
}