How do I complete the code for the void initMemo() {} section and the unsigned long long mfib(int n)} section where it says ADD CODE? Fibonacci Sequence Coding using Memoization C PROGRAM HELP...

How do I complete the code for the void initMemo() {} section and the unsigned long long mfib(int n)} section where it says ADD CODE?

Fibonacci Sequence Coding using Memoization C PROGRAM HELP Details:

- Create the
mfib() function
to calculate Fibonacci using memoization

- Also create the initMemo() function to clear out memoization table(s) at the beginning of each
mfib()
run

The output of the program will record the relative amount of time required from the start of each function calculation to the end.

Note the speed difference between
fib and mfib!

Turn in your commented program and a screen shot of the execution run of the program.

Do not be alarmed as the non-memoization Fibonacci calls take a long time to calculate, especially the higher values.

Be patient. It should finish.

Given Code:

#include

#include

#include

#include

#include

// max number of inputs

#define MAX_FIB 200

// result of call to fib function

unsigned long long result;

//loop variable

int i;

// ========================== MEMO DEFINITIONS ==========================

unsigned long long memo[MAX_FIB]; // array to hold computed data values

bool valid[MAX_FIB]; // array to hold validity of data

// make all entries in the memoization table invalid

void initMemo() {

// ***** ADD YOUR INITIALIZATION CODE HERE *****

// ***** ADD YOUR INITIALIZATION CODE HERE *****

// ***** ADD YOUR INITIALIZATION CODE HERE *****

// ***** ADD YOUR INITIALIZATION CODE HERE *****

// ***** ADD YOUR INITIALIZATION CODE HERE *****

return;

}

// ===================== TIME DEFINITIONS ===============

// timer functions found in time.h

// time_t is time type

time_t startTime;

time_t stopTime;

// get current time in seconds from some magic date with

// t = time(NULL);

// or

// time(&t);

// where t is of type time_t

//

// get difference in secs between times (t1-t2) with

// d = difftime(t1, t2);

// where d is of type double

// ========================== NAIVE FIB =========

unsigned long long fib(int n) {

if (n < 1)="">

return 0;

} else if (n == 1) {

return 1;

} else {

return fib(n-2) + fib(n-1);

}

}

// ========================== MEMOIZED FIB ==========================

unsigned long long mfib(int n) {

// ***** ADD YOUR MFIB CODE HERE *****

// ***** ADD YOUR MFIB CODE HERE *****

// ***** ADD YOUR MFIB CODE HERE *****

// ***** ADD YOUR MFIB CODE HERE *****

// ***** ADD YOUR MFIB CODE HERE *****

return 0; // replace this return with real computation

}

// ========================== MAIN PROGRAM ==========================

int main() {

for (i = 0; i < 55;="" i+="5)">

// get start time

time(&startTime);

// call fib

result = fib(i);

// get stop time

time(&stopTime);

printf("fib of %d = %llu\n", i, result);

printf("time taken (sec) = %lf\n\n", difftime(stopTime, startTime));

}

printf("\n\n\n");

for (i = 0; i < 90;="" i+="5)">

// get start time

time(&startTime);

printf("fib of %d = %llu\n", i, result);

printf("time taken (sec) = %lf\n\n", difftime(stopTime, startTime));

}

printf("\n\n\n");

for (i = 0; i < 90;="" i+="5)">

// get start time

time(&startTime);

// call mfib

initMemo();

result = mfib(i);

// get stop time

time(&stopTime);

printf("mfib of %d = %llu\n", i, result);

printf("time taken (sec) = %lf\n\n", difftime(stopTime, startTime));

}

return 0;

}

Sample output:

Extracted text: fib of 0 = 0 time taken (sec) = 0.000000 mfib of 15 = 0 time taken (sec) = 0.000000 mfib of 75 = 0 time taken (sec) = 0.000000 fib of 5 = 5 time taken (sec) = 0.000000 mfib of 20 = 0 time taken (sec) = 0.000000 mfib of 80 = 0 time taken (sec) = 0.000000 fib of 10 = 55 time taken (sec) = 0.000000 mfib of 25 = 0 time taken (sec) = 0.000000 mfib of 85 = 0 time taken (sec) = 0.000000 fib of 15 = 610 time taken (sec) = 0.000000 mfib of 36 = 0 time taken (sec) = 0.000000 fib of 20 = 6765 time taken (sec) = 0.000000 fib of 25 = 75025 time taken (sec) = 0.000000 mfib of 35 = 0 time taken (sec) = 0.000000 fib of 30 = 832040 time taken (sec) = 0.000000 mfib of 40 = 0 time taken (sec) = 0.000000 fib of 35 = 9227465 time taken (sec) = 0.000000 Fib of 45 = 0 time taken (sec) = 0.000000 fib of 40 = 102334155 time taken (sec) = 1.000000 fib of 45 = 1134903170 time taken (sec) = 9.000e00 mfib of 50 = 0 time taken (sec) = 0.000000 fib of 50 = 12586269025 time taken (sec) = 108.00000 mfib of 55 = 0 time taken (sec) = 0.0000e0 mfib of 60 = 0 time taken (sec) = 0.000000 mfib of e = 0 time taken (sec) = 0.000000 mfib of 65 = 0 time taken (sec) = 0.000000 mfib of 5 = 0 time taken (sec) = 0.000e00 mfib of 10 = 0 time taken (sec) = 0.00e000 mfib of 70 = 0 time taken (sec) = 0.000000