Write a program using C++ to answer the change making problem. At the beginning of your program you will declare an array d of coin denominations such as int d[] = { 1,3,4 };

Then you will ask the user for how many cents are needed and provide the solution as follows. Suppose user entered 6:

6 = 3 + 3

If the user enters 10:

10 = 3 + 3 + 4

Note that the order of the coins do not matter, so it is also correct if your program gives the output:

10 = 3 + 4 + 3

Q2. Develop our doubly linked list program as follows. Add the deque class to it (Chapter 5 has the answer for this). Ask the user to enter positive numbers into a deque (until the user enters a nonpositive number). Then, write a member function that splits the list in the middle. For example if the list had: [1,2,3,4,5,6] then the first list is [1,2,3] and the second list is [4,5,6]. If the list contains odd number of items then the first list will have one more item than the second list. For example if the list had: [1,2,3,4,5,6,7] then the first list is [1,2,3,4] and the second list is [5,6,7]. Your function is a member function, it will return a the second list as output but it will be modifying its data to contain the first half of the list. Show that your "split" function works.

Doubly Linked List code:

#include

#include

using namespace std;

typedef string Elem; // list element type

class DNode { // doubly linked list node

private:

Elem elem; // node element value

DNode* prev; // previous node in list

DNode* next; // next node in list

friend class DLinkedList; // allow DLinkedList access

};

class DLinkedList { // doubly linked list

public:

DLinkedList(); // constructor

~DLinkedList(); // destructor

bool empty() const; // is list empty?

const Elem& front() const; // get front element

const Elem& back() const; // get back element

void addFront(const Elem& e); // add to front of list

void addBack(const Elem& e); // add to back of list

void removeFront(); // remove from front

void removeBack(); // remove from back

int n;

private: // local type definitions

DNode* header; // list sentinels

DNode* trailer;

protected: // local utilities

void add(DNode* v, const Elem& e); // insert new node before v

void remove(DNode* v); // remove node v

};

DLinkedList::DLinkedList() : n(0) { // constructor

header = new DNode; // create sentinels

trailer = new DNode;

header->next = trailer; // have them point to each other

trailer->prev = header;

}

DLinkedList::~DLinkedList() { // destructor

while (!empty()) removeFront(); // remove all but sentinels

delete header; // remove the sentinels

delete trailer;

}

bool DLinkedList::empty() const // is list empty?

{

return (header->next == trailer);

}

const Elem& DLinkedList::front() const // get front element

{

return header->next->elem;

}

const Elem& DLinkedList::back() const // get back element

{

return trailer->prev->elem;

}

// insert new node before v

void DLinkedList::add(DNode* v, const Elem& e) {

DNode* u = new DNode; u->elem = e; // create a new node for e

u->next = v; // link u in between v

u->prev = v->prev; // ...and v->prev

v->prev->next = u;

v->prev = u;

}

void DLinkedList::addFront(const Elem& e) // add to front of list

{

add(header->next, e);

n++;

}

void DLinkedList::addBack(const Elem& e) // add to back of list

{

add(trailer, e);

n++;

}

void DLinkedList::remove(DNode* v) { // remove node v

DNode* u = v->prev; // predecessor

DNode* w = v->next; // successor

u->next = w; // unlink v from list

w->prev = u;

delete v;

n--;

}

void DLinkedList::removeFront() // remove from font

{

remove(header->next);

}

void DLinkedList::removeBack() // remove from back

{

remove(trailer->prev);

}

int main() {

DLinkedList lst;

lst.addFront("A");

cout

lst.addFront("B");

cout

lst.addBack("C");

cout

return EXIT_SUCCESS;

}