Lab 11 C++
Download the attached program and run it - as is. It will promptfor a Fibonacci number then calculate the result using a recursivealgorithm. Enter a number less then 40 unless you want to wait fora very long time.
Find a number that takes between 10 and 20 seconds. (10,000 -20,000 milliseconds).
- Modify the program to use the static array of values to\"remember\" previous results. Then when the function is called againwith the same value, simply return the value. You might think ofthis as the number of base cases expanding dynamically as theprogram runs.
/* * CS 1337 Lab Assignment 11 * * Dynamic Programming Example * * Use dynamic programming do make the Fib() function more usable for large * values of n. This program has a timer that will calculate the time it * takes to run the function. Use that to compare the before and after times. * */#include #include #include // ...using namespace std::chrono;milliseconds get_time() { milliseconds ms = duration_cast< milliseconds >( system_clock::now().time_since_epoch() ); return ms;}using namespace std;int Fib(int n) { // Keep track of calculated values in a static array. static int values[100] = {0}; int retval; // base cases. if (n<=0) return 0; if (n==1) return 1; retval = Fib(n-1) + Fib(n-2); return retval;}/* * */int main(int argc, char** argv) { int val, n; duration time_span; high_resolution_clock::time_point start, end; cout << \"Enter a number less the 100: \"; cin >> n; start = high_resolution_clock::now(); val = Fib(n); end = high_resolution_clock::now(); time_span = end - start; cout << \"Fib(\" << n << \") is : \" << val << endl; cout << \"Elapsed time in milliseconds: \" << time_span.count() << endl; return 0;}
