I\'ve made a .cpp file earlier that ask the user to input an amount and then out

Question

I've made a .cpp file earlier that ask the user to input an amount and then outputs the possibilities a change can be given, but it was not done with a recursive algorithm. Please help me with how to make changes recursively. Below are the instruction.

create a recursive algorithm that looks at all the possible combinations of coins in order to find the best combination of coins for a given amount of change. The program should take inputs of the amount of cents for which to make change and the maximum number of coins to give as change.

The main algorithm should exhaustively try all possible combinations of coins for a given amount and then report the best combination of coins. The program should also report if there is no given solution to a given set of inputs.

The following types of coins can be used for making changes: $1 coin , 50 cent piece, 25 cent piece, 10 cent piece, 5 cent piece, and 1 cent.    

Please have the user input any amount cents they wish to compute then output the possibilites a change can be given.   also report if there are no solutions for making the change.                                                                                              

Explanation / Answer

#include<iostream>

using namespace std;

const int N0_SOLUTION = 1000;

void coinchange(int,int,int[],int);

int coins[6]= {1,50,25,10,5,1};

int Usedcoins[100];

int numusedcoins = N0_SOLUTION, numposib = 0, numcoins;

int main()

{

int usedcoins[100];

int numofcoinsused = 0;

int total;

cout<<"coins in cents : ";

for(int i=0; i<5; i++)

cout<<coins[i]<<" ";

cout<<endl;

cout<<" Enter amount :";

cin>>total;

cout<<" Enter number of coins to give as change ";

cin>>numcoins;

coinchange(numcoins,total,usedcoins,numofcoinsused);

cout<<" Number of posible combinations are : " <<numposib;

cout<<" And best combination is : ";

if(numusedcoins == N0_SOLUTION)

cout<<" No solution";

else {

for(int j=0;j<numusedcoins;j++)

cout<<Usedcoins[j]<<" ";

}

cout<<endl;

system("pause");

return 0;

}

void coinchange(int leftcoins, int total, int usedcoins[], int numofcoinsused )

{

int position,totalcount;

if(leftcoins == 0)

return;

else if(total < 0)

return;

else if(total == 0)

{

if(numofcoinsused < numusedcoins)

{

for(totalcount = 0; totalcount < numofcoinsused;totalcount++)

Usedcoins[totalcount] = usedcoins[totalcount];

numusedcoins = numofcoinsused;

}

numposib++;

return;

}

position = numcoins - leftcoins;

usedcoins[numofcoinsused] = coins[position];

numofcoinsused++;

coinchange(leftcoins, total - coins[position], usedcoins, numofcoinsused );

numofcoinsused--;

coinchange(leftcoins -1, total , usedcoins, numofcoinsused );

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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