Question

Lab 11 C++

Download the attached program and run it - as is. It will prompt for a Fibonacci number then calculate the result using a recursive algorithm. Enter a number less then 40 unless you want to wait for a very long time.

Find a number that takes between 10 and 20 seconds. (10,000 - 20,000 milliseconds).

1. Modify the program to use the static array of values to "remember" previous results. Then when the function is called again with the same value, simply return the value. You might think of this as the number of base cases expanding dynamically as the program 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;
}

Answer 1

// do comment if any problem arises

// code

/*

* 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 <iostream>

#include <chrono>

#include <vector>

// ...

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};

    values[1] = 1;

    if (values[n] != 0 || n == 0)

        return values[n];

    values[n] = Fib(n - 1) + Fib(n - 2);

    return values[n];

}

/*

*

*/

int main(int argc, char **argv)

{

    int val, n;

    duration<double> 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;

}

Output using previous program:

Output using dynamic programming: