Question

use cpp

1 a)Write a console program which creates an array of size 100 integers. Then use Fibonacci function Fib(n) to fill up the array with Fib(n) for n = 3 to n = 103: So this means the array looks like: { Fib(3), Fib(4), Fib(5), ...., Fib[102) }.  For this part of assignment you should first write a recursive Fib(n) funcion, as was done in class.For testing, print out the 100 integers.

1 b) For second part of this assignment, you must modify the Fib(n) you wrote for part a) so that it uses the array you fill in part a, to compute Fib (n+1) using Fib(n) and Fib(n-1)
already saved in the array.This way we do not compute the same Fib numbers many times.

Answer 1

1a)

#include <iostream>

using namespace std;

long int Fib(int n){//returns int value
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fib(n-1)+Fib(n-2);//recursively calling the sum of fib of previous two numbers
}
int main()
{
long int a[100];
int i,j=0;
for(i=3;i<103;i++){
a[j++]=Fib(i);//call the function and store the result in array
}
for(i=0;i<100;i++)
cout<<a[i]<<endl;//print the array

return 0;
}

Output:

Please see that the 100 numbers are produced as output and the run time is gigher because the execution involves more recursive calls.

1b)

#include <iostream>
using namespace std;
long int Fib(int n,long int a[100]){//returns int value
if(n==3)
return 2;
else if(n==4)
return 3;
else
return a[(n-3)-1]+a[(n-3)-2];//use the array and return the sum of previous two elements
}
int main()
{
long int a[100];
int i,j=0;
for(i=3;i<103;i++){
a[j++]=Fib(i,a);//call the function and store the result in array
}
for(i=0;i<100;i++)
cout<<a[i]<<endl;//print the array

return 0;
}

Output:

See that the above code uses the previous array elements and computes the fibonacci series.

This reduces the number of computations.