Heres some example code ( this is an algorithm I adapted from “Data structures and Problem Solving Using C++” by Mark Allen West ). The code is in C++ , but you can adapt it ( I like to program most things in C++ , but without the use of OPP ). Anyway , heres the code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | <br /> /****************************************************************<br /> * File Name : c:programshelpshell.cpp<br /> * Date : January,3,1980<br /> * Comments : new project<br /> * Compiler/Assembler : visual c++ 6.0<br /> * Program Shell Generated At: 3:29:12 a.m.<br /> =-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/<br /> <br /> #include < iostream ><br /> //#include < string.h ><br /> //#include < conio.h ><br /> //#include < math.h ><br /> //#include < iomanip ><br /> //#include < ctype.h ><br /> using namespace std;<br /> <br /> //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@<br /> void makeChange ( int * bills , int differentBills , int change , int *& billsUsed , int *& addedBill );<br /> void outputResults ( int change , int * billsUsed , int * billsAdded );<br /> //##################################################################################<br /> <br /> //main function ******************************<br /> int main ( )<br /> {<br /> int bills [ 5 ] = { 1 , 5 , 10 , 20 , 50 };<br /> int * billsUsed = 0; //bills used for various amounts<br /> int * addedBill = 0; //bill added to make new total<br /> <br /> <br /> cout << "enter an amount ";<br /> int amount;<br /> cin >> amount;<br /> makeChange ( bills , 5 , amount , billsUsed , addedBill );<br /> outputResults ( amount , billsUsed , addedBill );<br /> delete billsUsed;<br /> delete addedBill;<br /> return 0 ;<br /> }<br /> <br /> /******************************* FUNCTION DEFINITION ******************************<br /> Name : makeChange<br /> Parameters :<br /> bills a(n) int * ( int * ) ,<br /> billsOutput a(n) int ( int ) ,<br /> change a(n) int ( int )<br /> <br /> Returns: user defined type , int<br /> Comments:<br /> <br /> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br /> void makeChange ( int * bills , int differentBills , int change , int *& billsUsed , int *& addedBill )<br /> {<br /> <br /> <br /> billsUsed = new int [ change + 1 ];<br /> addedBill = new int [ change + 1 ];<br /> <br /> billsUsed [ 0 ] = 0; //zero bills used to change zero dollars<br /> addedBill [ 0 ] = 1;<br /> <br /> int dollars = 1;<br /> while ( dollars <= change )<br /> {<br /> int minimumBills = dollars; //assume all ones at first<br /> int newBill = 1; //try to use one's first<br /> int j = 0;<br /> while ( j < differentBills )<br /> {<br /> <br /> //current bill is too large to make change<br /> if ( bills [ j ] > dollars )<br /> {<br /> j ++;<br /> continue;<br /> }<br /> //check if bill makes a new minimum bill total<br /> if ( billsUsed [ dollars - bills [ j ] ] + 1 < minimumBills )<br /> {<br /> //save new minimum along with bill used to make it<br /> minimumBills = billsUsed [ dollars - bills [ j ] ] + 1;<br /> newBill = bills [ j ];<br /> }<br /> j ++; //try next bill<br /> }<br /> billsUsed [ dollars ] = minimumBills;<br /> addedBill [ dollars ] = newBill;<br /> dollars ++;<br /> }<br /> }<br /> /******************************* FUNCTION DEFINITION ******************************<br /> Name : outputResults<br /> Parameters :<br /> change a(n) int ( int ) ,<br /> billsUsed a(n) int * ( int * ) ,<br /> billsAdded a(n) int * ( int * )<br /> <br /> Returns: user defined type , void<br /> Comments:<br /> <br /> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br /> void outputResults ( int change , int * billsUsed , int * billsAdded )<br /> {<br /> <br /> cout << endl << endl;<br /> cout << "The number of bills needed to change " << change;<br /> cout << " is " << billsUsed [ change ] << endl << endl;<br /> cout << "The bills used are:" << endl;<br /> int total = 0;<br /> int i = change;<br /> while ( total != change )<br /> {<br /> <br /> cout << "tone ";<br /> <br /> switch ( billsAdded [ i ] )<br /> {<br /> case 1:<br /> {<br /> cout << "dollar" << endl;<br /> };<br /> break;<br /> case 5:<br /> {<br /> cout << "five" << endl;<br /> };<br /> break;<br /> case 10:<br /> {<br /> cout << "ten" << endl;<br /> };<br /> break;<br /> case 20:<br /> {<br /> cout << "twenty" << endl;<br /> };<br /> break;<br /> case 50:<br /> {<br /> cout << "fifty" << endl;<br /> };<br /> break;<br /> }<br /> total += billsAdded [ i ];<br /> i -= billsAdded [ i ];<br /> }<br /> return;<br /> }<br /> |
and heres some output examples:
enter an amount 88
The number of bills needed to change 88 is 7
The bills used are:
one dollar
one dollar
one dollar
one five
one ten
one twenty
one fifty
Press any key to continue
enter an amount 77
The number of bills needed to change 77 is 5
The bills used are:
one dollar
one dollar
one five
one twenty
one fifty
Press any key to continue
sorry for the alignment , this forum messes up my tabing….
