Question

1 Approved Answer

Posted on Sep 22, 2024

I must use the pseudo-code to below Read Me File: Top-down Approach The top-down approach is a technique of saving values that have already been

I must use the pseudo-code to below

Read Me File:

Top-down Approach

The top-down approach is a technique of saving values that have already been calculated, a technique that is referred to as memoization. With this technique we first break the problem up into sub-problems and then calculate and store values. To facilitate this approach we can use a map structure. A map is also known as an "associative array" in which "keys" are associated with "values." The arrays you have worked with thus far could be thought of as an associative map wherein the "key" is an integer (i.e., the index into the array), and of course, the "value" is the contents of the array at that index (key). Fortunately for us, the standard template library includes such a structure. The program Demo.cpp in this repo demonstrates the use of a map, and is shown below:

#include  #include  #include  #include  int main() { std::map grade_list; // Assign "John" a grade of 'C' grade_list["John"] = 'C'; std::cout << "John's grade = " << grade_list["John"] << std::endl; // Raise his grade grade_list["John"] = 'B'; std::cout << "After raising his grade, " << std::endl; // Find an entry in the map. The member function find(key) returns an // iterator; end() is an iterator that points to the "end" of the map. // If we haven't "reached" the end of the map, the key is in the map. if (grade_list.find("John") != grade_list.end()) { std::cout << "John's grade = " << grade_list["John"] << std::endl; } // On the other hand, if we have reached the "end" of the map using find(key) // then the key isn't in the map. if (grade_list.find("Jim") == grade_list.end()) { std::cout << "Jim wasn't found in the map" << std::endl; } else { std::cout << "Jim's grade = " << grade_list["Jim"] << std::endl; } // Let's associate another key/value pair in the map: grade_list["Sue"] = 'A'; // Iterators "point" to elements in the map. Each element in the map has // a key/value pair named "first" (the key) and "second" (the value). Two // common iterators are begin() and end(). NOTE: end() doesn't point to // anything // "John" <- 'A' <- grade_list.begin() points here // "Sue" <- 'A' // <- grade_list.end() points here, i.e. just after // the last item in the map. Trying to access items // pointed to by end() will result in a Segmentation // fault and will dump the core. std::cout << "grade_list.begin()->first = " << grade_list.begin()->first << std::endl; std::cout << "grade_list.begin()->second = " << grade_list.begin()->second << std::endl; // We can use these pointers to iterator through the map std::cout << "Mappings in grade_list:" << std::endl; for (std::map::iterator it = grade_list.begin(); it != grade_list.end(); ++it) { std::cout << std::setw(4) << it->first << " <-- " << it->second << std::endl; } // A map that maps integers to integers std::map m; m[0] = 1; m[1] = 1; for (std::map::iterator it = m.begin(); it != m.end(); ++it) { std::cout << it->first << " <-- " << it->second << std::endl; } return EXIT_SUCCESS; }

Compiling and running (in a Cygwin terminal) this program would look like (where '$' is the command-line prompt and not typed):

$ g++ map_demo.cpp $ ./a.exe John's grade = C After raising his grade, John's grade = B Jim wasn't found in the map grade_list.begin()->first = John grade_list.begin()->second = B Mappings in grade_list: John <-- B Sue <-- A 0 <-- 1 1 <-- 1

For more details and a quick tutorial on using the map found in the STL, see STL Maps -- Associative Arrays.

With this understanding of the map object, let us return to the top-down approach to finding the nth Fibonacci number using a map.

Suppose we have a simple map object, m, which maps each Fibonacci number calculated that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(n) time instead of exponential time (but requires O(n) space):

// This, of course, is just pseudo-code map m m[0] = 1 m[1] = 1 function fib(n) if key n is not in map m m[n] = fib(n - 1) + fib(n - 2) return m[n]

$ cd generator $ cmake -G "Unix Makefiles" .. ... lots of output $ make ... more output $ ../out/lab03.exe This program computes the nth Fibonacci number. To end this program, enter a negative value for n. n = -1 Program has ended successfully. Good bye... $ ../out/lab03.exe This program computes the nth Fibonacci number. To end this program, enter a negative value for n. n = 9 Top-down approach: fib(9) = 0 Bottom-up approach: fib(9) = 0 n = 2 Top-down approach: fib(2) = 0 Bottom-up approach: fib(2) = 0 n = -1 Program has ended successfully. Good bye...

Clearly, the values are not being calculated correctly. This is because the functions are merely stubbed out.

Below I must use the above Pseudo-code in the program below. I am completely lost as to what I need to write.

/**
	* CSC232 Data Structures with C++
	* Missouri State University, Spring 2019
	*
	* @file TopDownFibCalculator.cpp
	* @authors Jim Daehn
	* Your Name
	* @brief Definition of TopDownFibCalculator.
	*/

	#include "TopDownFibCalculator.h"

	int TopDownFibCalculator::nthFibonacciNumber(int n) const {
	// TODO: Implement me using the algorithm shown in the README.md file of this project.
	return 0;
	}