J
jhon02148
hi
this hw have four files:
1. for the main program
2. listp.cpp (the source file)
3. listp.h (the header file)
4. exception.h
hi
iam done with my hw i still have to do one function which is the last
one on program.cpp subsetsum(int aList, int sum)so please can you help.
thanks for anybody in advance
#include <iostream>
#include <limits.h>
#include <cassert>
using std::cin;
using std::cout;
using std::endl;
using namespace std;
#define NumCities 5
#define MaxFib 100
#include "Exceptions.h"
#include "ListP.h"
#include "ListP.cpp"
void List::enterList()
// Prompt the user to enter integer values from the keyboard. Each
// value is inserted into the list. When the user enters -1, input
// from the keyboard stops. Adds the new values to the beginning of
// the current contents of list, if any.
{
ListItemType val;
int count = 1;
do
{
cout << "Enter value (-1 to end): " << count << endl;
cin >> val;
if (val != -1)
insert(count, val);
count++;
}
while (val != -1);
}
int fib(int n)
// Returns the nth Fibonacci number. The result is computed
// recursively. Does no error checking. What is the largest number
// you can compute this way?
{
if (n == 1 || n == 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
int fib2(int n, int F[])
// Returns the nth Fibonacci number. The result is computed
// recursively. Does not compute any number more than once and uses
// the array F[] to store previously computed numbers. Does no error
// checking. What is the largest number you can compute this way?
{
if (F[n] != -1)
return (F[n]);
else
if (n != 1 || n != 2)
{
F[n] = fib2(n - 1, F) + fib2(n - 2, F);
return F[n];
}
else
{
F[n] = 1;
return 1;
}
}
void testFib()
// Helper function that prompts the user to enter an integer n, and
// prints the nth Fibonacci number.
{
int n;
cout << "enter n: " << endl;
cin >> n;
cout << fib(n) << endl;
}
void testFib2()
// Helper function that prompts the user to enter an integer n, and
// prints the nth Fibonnaci number.
{
int F[MaxFib];
int n;
for (int i = 0; i < MaxFib; i++)
F = -1;
cout << "enter n: " << endl;
cin >> n;
cout << fib2(n,F) << endl;
}
int sum (int list[], int left, int right)
// Returns the sum of the numbers in array list, starting at index
// left and ending at index right. The sum is computed recursively.
{
if (left == right - 1)
return list
this hw have four files:
1. for the main program
2. listp.cpp (the source file)
3. listp.h (the header file)
4. exception.h
hi
iam done with my hw i still have to do one function which is the last
one on program.cpp subsetsum(int aList, int sum)so please can you help.
thanks for anybody in advance
#include <iostream>
#include <limits.h>
#include <cassert>
using std::cin;
using std::cout;
using std::endl;
using namespace std;
#define NumCities 5
#define MaxFib 100
#include "Exceptions.h"
#include "ListP.h"
#include "ListP.cpp"
void List::enterList()
// Prompt the user to enter integer values from the keyboard. Each
// value is inserted into the list. When the user enters -1, input
// from the keyboard stops. Adds the new values to the beginning of
// the current contents of list, if any.
{
ListItemType val;
int count = 1;
do
{
cout << "Enter value (-1 to end): " << count << endl;
cin >> val;
if (val != -1)
insert(count, val);
count++;
}
while (val != -1);
}
int fib(int n)
// Returns the nth Fibonacci number. The result is computed
// recursively. Does no error checking. What is the largest number
// you can compute this way?
{
if (n == 1 || n == 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
int fib2(int n, int F[])
// Returns the nth Fibonacci number. The result is computed
// recursively. Does not compute any number more than once and uses
// the array F[] to store previously computed numbers. Does no error
// checking. What is the largest number you can compute this way?
{
if (F[n] != -1)
return (F[n]);
else
if (n != 1 || n != 2)
{
F[n] = fib2(n - 1, F) + fib2(n - 2, F);
return F[n];
}
else
{
F[n] = 1;
return 1;
}
}
void testFib()
// Helper function that prompts the user to enter an integer n, and
// prints the nth Fibonacci number.
{
int n;
cout << "enter n: " << endl;
cin >> n;
cout << fib(n) << endl;
}
void testFib2()
// Helper function that prompts the user to enter an integer n, and
// prints the nth Fibonnaci number.
{
int F[MaxFib];
int n;
for (int i = 0; i < MaxFib; i++)
F = -1;
cout << "enter n: " << endl;
cin >> n;
cout << fib2(n,F) << endl;
}
int sum (int list[], int left, int right)
// Returns the sum of the numbers in array list, starting at index
// left and ending at index right. The sum is computed recursively.
{
if (left == right - 1)
return list
+ list
;
else
if (left == right)
return list
else
if (left == right)
return list
;
else
return list
else
return list
+ list
+ sum (list, left+1, right-1);
}
void testSum()
// Function to test the sum function
{
int list[99999];
int i = 0;
int x;
cout << "Enter numbers, enter -1 to stop" << endl;
do
{
cin >> x;
if (x != -1)
list[i++] = x;
} while (x != -1);
cout << "The sum is " << sum(list,0,i-1) << endl;
cout << endl;
}
int multiply(int m, int n)
// Returns the product of m and n. The result is computed
// recursively. Assumes that m and n are positive integers, uses no
// loops or multiplication, and does no error checking.
{
if (n == 1)
return m;
else
return multiply(m, n - 1)+ m;
}
void testMultiply()
// Function to test the multiply function.
{
int x,y;
cout << "Enter a number:" << endl;
cin >> x;
cout << "Enter a number:" << endl;
cin >> y;
cout << "The product of " << x << " and " << y << " is " <<
multiply(x,y) << endl;
}
bool findPathRecursive(int originCity, int destinationCity, bool
visited[],
int edge[][NumCities])
// Returns true if a path from originCity to destinationCity exists in
// the graph defined by edge. Paths are found using the following
// recursive algorithm: to find a path from city i to city j, check
// whether there is a path from any cities k, which are neighbors of
// i, to j. If a path exists, prints it in any order. This function
// does not use any stacks or queues.
{
if (originCity == destinationCity)
{
cout << originCity << endl;
return true;
}
else
for (int i = 0; i < NumCities; i++)
{
if (edge[originCity] && !visited)
{
visited[originCity] = true;
originCity = i;
}
if (findPathRecursive(originCity, destinationCity, visited, edge))
{
cout << originCity << endl;
return true;
}
if (i == destinationCity)
{
cout << i << endl;
return true;
}
}
return false;
}
void testFindPathRecursive()
// Helper function that prompts the user to enter source and
// destination cities, and then uses findPathRecursive to determine if
// a path exists in the graph from source to destination.
{
int edge[NumCities][NumCities] = {{0,1,0,0,0},
{0,0,1,1,0},
{0,0,0,0,1},
{0,1,0,0,0},
{0,0,0,0,0}};
int originCity, destinationCity, i;
bool visited[NumCities];
for (i = 0; i < NumCities; i++)
visited = false;
cout << "Enter origin city: ";
cin >> originCity;
cout << "Enter destination city: ";
cin >> destinationCity;
if (!findPathRecursive(originCity, destinationCity, visited, edge))
cout << "No path found" << endl;
}
//bool subsetSum(List aList, int sum)
// Return true if some subset of the integers stored in aList add up
// to sum. Uses recursion.
/*void testSubsetSum()
{
List aList;
int num;
cout << "Enter list values" << endl;
aList.enterList();
cout << "Enter a target sum" << endl;
cin >> num;
cout << "Result: " << subsetSum(aList, num) << endl;
}
*/
int main()
{
int choice;
do
{
cout << "1. fib" << endl;
cout << "2. fib2" << endl;
cout << "3. multiply" << endl;
cout << "4. sum" << endl;
cout << "5. findPathRecursive" << endl;
cout << "6. subsetSum" << endl;
cout << "Enter a number, or -1 to exit: ";
cin >> choice;
switch (choice)
{
case 1:
testFib();
break;
case 2:
testFib2();
break;
case 3:
testMultiply();
break;
case 4:
testSum();
break;
case 5:
testFindPathRecursive();
break;
// case 6:
// testSubsetSum();
break;
}
} while (choice != -1);return 0;
}
// *********************************************************
// Header file ListP.h for the ADT list.
// Pointer-based implementation.
// *********************************************************
// Must define ListItemType before compilation
#ifndef ListP_h
#define ListP_h
#include "Exceptions.h"
typedef int ListItemType;
class List
{
public:
// constructors and destructor:
List(); // default constructor
List(const List& aList); // copy constructor
~List(); // destructor
// list operations:
bool isEmpty() const;
int getLength() const;
void insert(int index, ListItemType newItem)
throw(ListIndexOutOfRangeException, ListException);
void remove(int index)
throw(ListIndexOutOfRangeException);
void retrieve(int index, ListItemType& dataItem) const
throw(ListIndexOutOfRangeException);
void enterList();
private:
struct ListNode // a node on the list
{
ListItemType item; // a data item on the list
ListNode *next; // pointer to next node
}; // end struct
int size; // number of items in list
ListNode *head; // pointer to linked list of items
ListNode *find(int index) const;
// Returns a pointer to the index-th node
// in the linked list.
}; // end class
// End of header file.
#endif
// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ListP.h"
#include "Exceptions.h"
List::List(): size(0), head(NULL)
{
} // end default constructor
List::List(const List& aList): size(aList.size)
{
if (aList.head == NULL)
head = NULL; // original list is empty
else
{
// copy first node
head = new ListNode;
assert(head != NULL); // check allocation
head->item = aList.head->item;
// copy rest of list
ListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list
// origPtr points to nodes in original list
for (ListNode *origPtr = aList.head->next;
origPtr != NULL;
origPtr = origPtr->next)
{
newPtr->next = new ListNode;
assert(newPtr->next != NULL);
newPtr = newPtr->next;
newPtr->item = origPtr->item;
} // end for
newPtr->next = NULL;
} // end if
} // end copy constructor
List::~List()
{
while (!isEmpty())
remove(1);
} // end destructor
bool List::isEmpty() const
{
return bool(size == 0);
} // end isEmpty
int List::getLength() const
{
return size;
} // end getLength
List::ListNode *List::find(int index) const
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the
// desired node.
// Postcondition: Returns a pointer to the desired
// node. If index < 1 or index > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
if ( (index < 1) || (index > getLength()) )
return NULL;
else // count from the beginning of the list
{
ListNode *cur = head;
for (int skip = 1; skip < index; ++skip)
cur = cur->next;
return cur;
} // end if
} // end find
void List::retrieve(int index,
ListItemType& dataItem) const
throw (ListIndexOutOfRangeException)
{
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: retrieve index out of range");
else
{
// get pointer to node, then data in node
ListNode *cur = find(index);
dataItem = cur->item;
} // end if
} // end retrieve
void List::insert(int index, ListItemType newItem)
throw(ListIndexOutOfRangeException, ListException)
{
int newLength = getLength() + 1;
if ((index < 1) || (index > newLength))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: insert index out of range");
else
{
// create new node and place newItem in it
ListNode *newPtr = new ListNode;
if (newPtr == NULL)
throw ListException(
"ListException: insert cannot allocate memory");
else
{
size = newLength;
newPtr->item = newItem;
// attach new node to list
if (index == 1)
{
// insert new node at beginning of list
newPtr->next = head;
head = newPtr;
}
else
{
ListNode *prev = find(index-1);
// insert new node after node
// to which prev points
newPtr->next = prev->next;
prev->next = newPtr;
} // end if
} // end if
} // end if
} // end insert
void List::remove(int index)
throw(ListIndexOutOfRangeException)
{
ListNode *cur;
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: remove index out of range");
else
{
--size;
if (index == 1)
{
// delete the first node from the list
cur = head; // save pointer to node
head = head->next;
}
else
{
ListNode *prev = find(index-1);
// delete the node after the
// node to which prev points
cur = prev->next; // save pointer to node
prev->next = cur->next;
} // end if
// return node to system
cur->next = NULL;
delete cur;
cur = NULL;
} // end if
} // end remove
// *********************************************************
// File Exceptions.h containing declarations of List and Stack
// Exceptions.
// *********************************************************
#ifndef Exceptions_h
#define Exceptions_h
#include <string>
#include <exception>
using namespace std;
class ListException
{
public:
ListException(const string &m = "")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end ListException
class ListIndexOutOfRangeException
{
public:
ListIndexOutOfRangeException(const string &m = "")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end ListIndexOutOfRangeException
class StackException
{
public:
StackException(const string & m="")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end StackException
class QueueException
{
public:
QueueException(const string & m="")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end QueueException
#endif
}
void testSum()
// Function to test the sum function
{
int list[99999];
int i = 0;
int x;
cout << "Enter numbers, enter -1 to stop" << endl;
do
{
cin >> x;
if (x != -1)
list[i++] = x;
} while (x != -1);
cout << "The sum is " << sum(list,0,i-1) << endl;
cout << endl;
}
int multiply(int m, int n)
// Returns the product of m and n. The result is computed
// recursively. Assumes that m and n are positive integers, uses no
// loops or multiplication, and does no error checking.
{
if (n == 1)
return m;
else
return multiply(m, n - 1)+ m;
}
void testMultiply()
// Function to test the multiply function.
{
int x,y;
cout << "Enter a number:" << endl;
cin >> x;
cout << "Enter a number:" << endl;
cin >> y;
cout << "The product of " << x << " and " << y << " is " <<
multiply(x,y) << endl;
}
bool findPathRecursive(int originCity, int destinationCity, bool
visited[],
int edge[][NumCities])
// Returns true if a path from originCity to destinationCity exists in
// the graph defined by edge. Paths are found using the following
// recursive algorithm: to find a path from city i to city j, check
// whether there is a path from any cities k, which are neighbors of
// i, to j. If a path exists, prints it in any order. This function
// does not use any stacks or queues.
{
if (originCity == destinationCity)
{
cout << originCity << endl;
return true;
}
else
for (int i = 0; i < NumCities; i++)
{
if (edge[originCity] && !visited)
{
visited[originCity] = true;
originCity = i;
}
if (findPathRecursive(originCity, destinationCity, visited, edge))
{
cout << originCity << endl;
return true;
}
if (i == destinationCity)
{
cout << i << endl;
return true;
}
}
return false;
}
void testFindPathRecursive()
// Helper function that prompts the user to enter source and
// destination cities, and then uses findPathRecursive to determine if
// a path exists in the graph from source to destination.
{
int edge[NumCities][NumCities] = {{0,1,0,0,0},
{0,0,1,1,0},
{0,0,0,0,1},
{0,1,0,0,0},
{0,0,0,0,0}};
int originCity, destinationCity, i;
bool visited[NumCities];
for (i = 0; i < NumCities; i++)
visited = false;
cout << "Enter origin city: ";
cin >> originCity;
cout << "Enter destination city: ";
cin >> destinationCity;
if (!findPathRecursive(originCity, destinationCity, visited, edge))
cout << "No path found" << endl;
}
//bool subsetSum(List aList, int sum)
// Return true if some subset of the integers stored in aList add up
// to sum. Uses recursion.
/*void testSubsetSum()
{
List aList;
int num;
cout << "Enter list values" << endl;
aList.enterList();
cout << "Enter a target sum" << endl;
cin >> num;
cout << "Result: " << subsetSum(aList, num) << endl;
}
*/
int main()
{
int choice;
do
{
cout << "1. fib" << endl;
cout << "2. fib2" << endl;
cout << "3. multiply" << endl;
cout << "4. sum" << endl;
cout << "5. findPathRecursive" << endl;
cout << "6. subsetSum" << endl;
cout << "Enter a number, or -1 to exit: ";
cin >> choice;
switch (choice)
{
case 1:
testFib();
break;
case 2:
testFib2();
break;
case 3:
testMultiply();
break;
case 4:
testSum();
break;
case 5:
testFindPathRecursive();
break;
// case 6:
// testSubsetSum();
break;
}
} while (choice != -1);return 0;
}
// *********************************************************
// Header file ListP.h for the ADT list.
// Pointer-based implementation.
// *********************************************************
// Must define ListItemType before compilation
#ifndef ListP_h
#define ListP_h
#include "Exceptions.h"
typedef int ListItemType;
class List
{
public:
// constructors and destructor:
List(); // default constructor
List(const List& aList); // copy constructor
~List(); // destructor
// list operations:
bool isEmpty() const;
int getLength() const;
void insert(int index, ListItemType newItem)
throw(ListIndexOutOfRangeException, ListException);
void remove(int index)
throw(ListIndexOutOfRangeException);
void retrieve(int index, ListItemType& dataItem) const
throw(ListIndexOutOfRangeException);
void enterList();
private:
struct ListNode // a node on the list
{
ListItemType item; // a data item on the list
ListNode *next; // pointer to next node
}; // end struct
int size; // number of items in list
ListNode *head; // pointer to linked list of items
ListNode *find(int index) const;
// Returns a pointer to the index-th node
// in the linked list.
}; // end class
// End of header file.
#endif
// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ListP.h"
#include "Exceptions.h"
List::List(): size(0), head(NULL)
{
} // end default constructor
List::List(const List& aList): size(aList.size)
{
if (aList.head == NULL)
head = NULL; // original list is empty
else
{
// copy first node
head = new ListNode;
assert(head != NULL); // check allocation
head->item = aList.head->item;
// copy rest of list
ListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list
// origPtr points to nodes in original list
for (ListNode *origPtr = aList.head->next;
origPtr != NULL;
origPtr = origPtr->next)
{
newPtr->next = new ListNode;
assert(newPtr->next != NULL);
newPtr = newPtr->next;
newPtr->item = origPtr->item;
} // end for
newPtr->next = NULL;
} // end if
} // end copy constructor
List::~List()
{
while (!isEmpty())
remove(1);
} // end destructor
bool List::isEmpty() const
{
return bool(size == 0);
} // end isEmpty
int List::getLength() const
{
return size;
} // end getLength
List::ListNode *List::find(int index) const
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the
// desired node.
// Postcondition: Returns a pointer to the desired
// node. If index < 1 or index > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
if ( (index < 1) || (index > getLength()) )
return NULL;
else // count from the beginning of the list
{
ListNode *cur = head;
for (int skip = 1; skip < index; ++skip)
cur = cur->next;
return cur;
} // end if
} // end find
void List::retrieve(int index,
ListItemType& dataItem) const
throw (ListIndexOutOfRangeException)
{
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: retrieve index out of range");
else
{
// get pointer to node, then data in node
ListNode *cur = find(index);
dataItem = cur->item;
} // end if
} // end retrieve
void List::insert(int index, ListItemType newItem)
throw(ListIndexOutOfRangeException, ListException)
{
int newLength = getLength() + 1;
if ((index < 1) || (index > newLength))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: insert index out of range");
else
{
// create new node and place newItem in it
ListNode *newPtr = new ListNode;
if (newPtr == NULL)
throw ListException(
"ListException: insert cannot allocate memory");
else
{
size = newLength;
newPtr->item = newItem;
// attach new node to list
if (index == 1)
{
// insert new node at beginning of list
newPtr->next = head;
head = newPtr;
}
else
{
ListNode *prev = find(index-1);
// insert new node after node
// to which prev points
newPtr->next = prev->next;
prev->next = newPtr;
} // end if
} // end if
} // end if
} // end insert
void List::remove(int index)
throw(ListIndexOutOfRangeException)
{
ListNode *cur;
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListOutOfRangeException: remove index out of range");
else
{
--size;
if (index == 1)
{
// delete the first node from the list
cur = head; // save pointer to node
head = head->next;
}
else
{
ListNode *prev = find(index-1);
// delete the node after the
// node to which prev points
cur = prev->next; // save pointer to node
prev->next = cur->next;
} // end if
// return node to system
cur->next = NULL;
delete cur;
cur = NULL;
} // end if
} // end remove
// *********************************************************
// File Exceptions.h containing declarations of List and Stack
// Exceptions.
// *********************************************************
#ifndef Exceptions_h
#define Exceptions_h
#include <string>
#include <exception>
using namespace std;
class ListException
{
public:
ListException(const string &m = "")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end ListException
class ListIndexOutOfRangeException
{
public:
ListIndexOutOfRangeException(const string &m = "")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end ListIndexOutOfRangeException
class StackException
{
public:
StackException(const string & m="")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end StackException
class QueueException
{
public:
QueueException(const string & m="")
{ message = m;}
string what() {return message;}
private:
string message;
}; // end QueueException
#endif