Question

Write a C++ program to computer the nth Fibonacci Number in 3 ways. Clearly define which way you are solving in your code using comments. You must provide an algorithm to solve for the nth Fibonacci Number in 1. a straight-forward recursive solution 2. a top-down memoized solution and 3. a bottom-up dynamic programming solution. These algorithms will be tested with randomly generated input, and a single non-negative number will be given through command line.

Answer 1

Method 1

//Fibonacci Series using Recursion
#include<iostream>

using namespace std;
int fib(int n)
{
if (n <= 1)
   return n;
return fib(n-1) + fib(n-2);
}

int main (int argc, char *argv[])
{
int n = atoi(argv[1]);

printf("%d", fib(n));
return 0;
}

Method 2

#include <iostream>

using namespace std;

int F[50]; //array to store fibonacci terms

// Initially, all elements of array F are -1.

void init_F() {

int i;

for(i=0; i<50; i++) {

F[i] = -1;

}

}

int dynamic_fibonacci(int n) {

if (F[n] < 0) {

if (n==0) {

F[n] = 0;

}

else if (n == 1) {

F[n] = 1;

}

else {

F[n] = dynamic_fibonacci(n-1) + dynamic_fibonacci(n-2);

}

}

return F[n];

}

int main(int argc, char *argv[]){

int n = atoi(argv[1]);

printf("%d\n",dynamic_fibonacci(n));

return 0;

}

Method 3

#include <iostream>

using namespace std;

int F[50]; //array to store fibonacci terms

int fibonacci_bottom_up(int n) {

F[n] = 0;

F[1] = 1;

int i;

for(i=2; i<=n; i++) {

F[i] = F[i-1] + F[i-2];

}

return F[n];

}

int main(int argc, char *argv[]){

int n = atoi(argv[1]);

printf("%d\n",fibonacci_bottom_up(n));

return 0;

}