logo CodeStepByStep logo


Suppose you have a class Calculator that performs calculations on integers:

Member Description
Calculator(int seed) constructs a Calculator with given seed for random numbers
virtual bool isPrime(int n) returns true if n is prime
virtual int kthPrime(int k) returns the kth prime (assumes k >= 1)
virtual int fib(int n) returns the nth Fibonacci number (assumes n >= 1)
virtual int rand(int max) returns a random value between 0 and max

The class correctly computes its results, but it does so inefficiently. In particular, it often computes the same value more than once. You are to implement a technique known as "memoizing" to speed up the computation of primes. The idea behind memoizing is to remember values that have been computed previously. For example, suppose that the value kthPrime(30) is requested 100 times. There is no reason to compute it 100 different times. Instead you can compute it once and store its value, so that the 99 calls after the first simply return the "memoized" value (the remembered value).

Define a new class called MemoryCalculator that can be used in place of a Calculator to speed up the prime computation. A MemoryCalculator object should behave just like a Calculator object except that it should guarantee that the value of kthPrime(k) is computed only once for any given value k. Your class should still rely on the Calculator class to compute each value for kthPrime(k). It is simply guaranteeing that the computation is not performed more than once for any particular value of k. The isPrime method calls kthPrime, so it does not need to be memoized. You do not need to memoize the Fibonacci computation. You should not make any assumptions about how large k might be or about the order in which the method is called with different values of k.

Your class should also provide the following public member functions that will allow a client to find out how many values have been directly computed versus how many calls have been handled through memoization.

Member Description
MemoryCalculator(int seed) constructs a MemoryCalculator with given seed for random numbers
virtual int getComputeCount() returns number of values actually computed
virtual int getMemoCount() returns number of calls handled through memoization
Inheritance: Write a C++ class using inheritance.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.