* PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a more e
ID: 3781951 • Letter: #
Question
* 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
}
Explanation / Answer
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.