C++ Assistance

I will provide the question I am attempting to resolve as well as post the code I am using that seems to have some errors some place. Please review the code and point out the errors.

Question:

Use an ADT list to implement the function f (n) for the following question.

Consider the following recurrence relation:

f(1) = 1; f(2) = 1; f(3) = 1; f(4) = 3; f(5) = 5; f(n) = f(n 1) + 3 X f(n 5) for all n > 5.

Compute f(n) for the following values of n: 6, 7, 12, 15.

If you were careful, rather than computing f(15) from scratch (the way a recursive C++ function would compute it), you would have computed f(6), then f(7), then f(8), and so on up to f(15), recording the values as you compute them. This ordering would have saved you the effort of ever computing the same value more than once. (Recall the iterative version of the rabbit function discussed at the end of this chapter.)

Attempted Answer:

****************************************************************************

main.cpp

****************************************************************************

// Include the needed header files

#include "ArrayList.cpp"

using namespace std;

// Define a function f_of_n() to calculate f(n)

int fof(int n)

{

// Define a arrayList variable

ArrayList lastFiveValues;

// Set f(1) = 1

lastFiveValues.insert(1, 1);

// Set f(2) = 1

lastFiveValues.insert(2, 1);

// Set f(3) = 1

lastFiveValues.insert(3, 1);

// Set f(4) = 3

lastFiveValues.insert(4, 3);

// Set f(5) = 5

lastFiveValues.insert(5, 5);

// Use for loop to check last 5

for (int it = 5; it < n; it++)

{

// Calculate the function f(i - 1) + 3 x f(i - 5)

int fiV = lastFiveValues.getEntry((it - 1) % 5 + 1) + 3 * lastFiveValues.getEntry((it - 5) % 5 + 1);

// Call ADT remove function

lastFiveValues.remove(it % 5 + 1);

// Call ADT insert function

lastFiveValues.insert(it % 5 + 1, fiV);

}

// Return result

return lastFiveValues.getEntry((n - 1) % 5 + 1);

}

// Program begins with a main function

int main()

{

// Call the function fof

cout << "Result:"; // incomplete

// Pause output

system("pause");

// Stop

return 0;

}

****************************************************************************

ArrayList.h

****************************************************************************

// Include the Header files

#ifndef _ARRAY_LIST

#define _ARRAY_LIST

// Include the header file "ListInterface.h"

#include "ListInterface.h"

// Include the header file "PrecondViolatedExcep.h"

#include "PrecondViolatedExcep.h"

// Declare the template class as arrayList

template

class ArrayList : public ListInterface

{

// Access specifier

private :

// Declare constant DEFAULT_CAPACITY

static const int DEFAULT_CAPACITY = 100;

// Declare an array of ItemType

ItemType items[DEFAULT_CAPACITY];

// Declare itemCount

int itemCount;

// Declare maxItems.

int maxItems;

// Access specifier

public :

// Default constructor

ArrayList();

// Declare isEmpty() method to check the list is clear

bool isEmpty() const;

// Declare a method getLength() to get the list size

int getLength() const;

// Declare a method insert() to entries in the list

bool insert( int newPosition, const ItemType& newEntry);

// Declare a method remove() the entries in the list

bool remove( int position );

// Declare method to clear the list

void clear();

// Declare a method getEntry() to output the position

ItemType getEntry(int position) const throw (PrecondViolatedExcep);

// Declare a method setEntry() sets the given position

void setEntry( int position, const ItemType& newEntry )

throw ( PrecondViolatedExcep );

};

#endif

****************************************************************************

ArrayList.cpp

****************************************************************************

// Include the header file "ArrayList.h"

#include "ArrayList.h"

// Define the default constructor set itemcount as 0

template

ArrayList::ArrayList():itemCount(0), maxItems(DEFAULT_CAPACITY)

{

}

// Define isEmpty() method to check the list is clear

template

bool ArrayList::isEmpty() const

{

// Return ItemCount

return itemCount == 0;

}

// Define getLength() to check number of elements in the list

template

int ArrayList::getLength() const

{

// Return the itemCount value

return itemCount;

}

// Declare a method insert() to enter entries in the list

template

bool ArrayList::insert(int newPosition, const ItemType& newEntry)

{

// Check newPosition is valid

bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1) && (itemCount < maxItems);

// If newPosition is valid

if (ableToInsert)

{

// Use for loop to make space for newEntry

for (int pos = itemCount; pos >= newPosition; pos--)

// Move elements towards array end

items[pos] = items[pos - 1];

// Place the newEntry at newPosition

items[newPosition - 1] = newEntry;

// Increase the ItemCount by 1

itemCount++;

}

// Return the ableToInsert

return ableToInsert;

}

// Delcarea method remove() to remove entries from the list

template

bool ArrayList::remove(int position)

{

// Check position is valid

bool ableToRemove = (position >= 1) && (position <= itemCount);

// If position is valid

if (ableToRemove)

{

// Use for loop to remove element at possition

for (int fromIndex = position, toIndex = fromIndex - 1; fromIndex < itemCount; fromIndex++, toIndex++)

// Move elements towards array begining

items[toIndex] = items[fromIndex];

// Decrease the itemCount value by 1

itemCount--;

}

// Return the ableToRemove

return ableToRemove;

}

// Define clear() to clear elements in the list

template

void ArrayList::clear()

{

// Assign 0 as itemCount

itemCount = 0;

}

// Define getEntry() to outputs item at the position

template

ItemType ArrayList::getEntry(int position) const throw(PrecondViolatedExcep)

{

// Check position is valid

bool ableToGet = (position >= 1) && (position <= itemCount);

// If position is valid

if (ableToGet)

// Return the item at the position

return items[position - 1];

// If position is not valid

else

{

// Create message

string message = "getEntry() called with an empty list or ";

// Add some string

message = message + "invalid position.";

// Throw the precondition violated exception with message

throw(PrecondViolatedExcep(message));

}

}

// Define setEntry() to outputs item at the position

template

void ArrayList::setEntry(int position, const ItemType& newEntry) throw(PredondViolatedExcep)

{

// Check position is valid

bool ableToSet = (position >= 1) && (position <= itemCount);

// If position is valid

if (ableToSet)

// Set the newEntry at position

items[position - 1] = newEntry;

// If position is not valid

else

{

// Create message

string message = "setEntry() called with an empty list or ";

// Add some string

message = message + "invalid position.";

// Throw the precondition violated exception with message

throw(PrecondViolatedExcep(message));

}

}

****************************************************************************

ListInterface.h

****************************************************************************

// Include the header files

#ifndef _LIST_INTERFACE

#define _LIST_INTERFACE

// Declare template class

template

class ListInterface

{

// Access Specifier

public :

// Declare isEmpty() method to check the list is clear

virtual bool isEmpty() const = 0;

// Define a method getLength to get length

virtual int getLength() const = 0;

// Define a method remove() to remove new entries to the list

virtual bool remove(int position) = 0;

// Define a method clear() = 0;

virtual void clear() = 0;

// Define a method getEntry() at position

virtual ItemType getEntry(int position) const = 0;

// Define a method setEntry() to newEntry at given position

virtual void setEntry(int position, const ItemType& newEntry) = 0;

};

#endif

****************************************************************************

PrecondViolatedExcep.h

****************************************************************************

// Header file decleration for precondition violated exception

#ifndef _PRECOND_VIOLATED_EXCEP

#define _PRECOND_VIOLATED_EXCEP

//include the needed header files

using namespace std;

// Class PrecondViolatedExcep

class PrecondViolatedExcep : public logic_error

{

// Access Specifier

public:

// Parameterized constructor decleration

PrecondViolatedExcep(const string& message = "");

// End of PrecondViolatedExcep

};

#endif

****************************************************************************

PrecondViolatedExcep.cpp

****************************************************************************

// Implementation code for PrecondViolatedExcep class

#include "PrecondViolatedExcep.h"

// Parameterized constructor

PrecondViolatedExcep::PrecondViolatedExcep(const string& message):logic_error("Precondition Violation Exception: " + message)

{

}