Consider the problem of making changes for n cents using coins of various denomi

Question

Consider the problem of making changes for n cents using coins of various denominations. The goal is to make the change using the least number of coins possible. Develop and present an algorithm for making changes using quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), assuming there is an unlimited supply of coins for each denomination. Design your algorithm to ensure that the smallest number of coins is used to make changes for any given amount. Show the changes made by your algorithm for 31 cents, 42 cents, and 57 cents. What are the basic operations used in your algorithm? How many basic operations are performed for making changes for n > 0 cents?

Will your algorithm still work if the supply of some coins is limited? For example, if nickels are completely unavailable in the denominations above, will your algorithm still produce the least number of coins for making changes? Again, show what changes are made by your algorithm for 31 cents, 42 cents, and 57 cents with no nickels.

Explanation / Answer

<code>

/* -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.
Life is complex. It has both real and imaginary part -- Newton
* File Name : pow.cpp
_._._._._._._._._._._._._._._._._._._._._.*/

#include<bits/stdc++.h>
using namespace std;
int main()
{

   int coins[] = {1,5,10,25};
   int x;
   cout<<"Enter the amount for change: ";
   cin >> x;
   if(x <= 0){
       cout<<"NO change available"<<endl;
   }else{
       int n = x;
       int x_tfive = x/25;;
       x %= 25;
       int x_ten = x/10;
       x %= 10;
       int x_five = x/5;
       x %= 5;
       cout<< n <<" :"<<"25 *"<<x_tfive<< "+ 10 *"<<x_ten<<"+ 5 *"<<x_five<<"+ 1 *"<<x<<endl;
   }
   return 0;
}

</code>

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.