Suppose a coin machine sells subway tickets (such as at the DC Metro), where eve
ID: 3548739 • Letter: S
Question
Suppose a coin machine sells subway tickets (such as at the DC Metro), where every ticket is a multiple of 10 cents. The machine accepts only dimes and quarters (no nickels or pennies).
Determine a recursive formula that would describe how many different ways one could give this machine exact change.
For example, 50 cents can be done exactly two different ways:
two quarters in sequence, or 5 dimes in sequence.
On the other hand, 60 cents can be done four different ways:
two quarters followed by a dime; a dime followed by two quarters;
quarter, then a dime, then a quarter; or six dimes in sequence.
Hint: insert one coin at a time.
For 60 cents -- insert a dime, and there are two ways to insert 50 cents;
or insert a quarter, and there are two ways to insert 35 cents.
Explanation / Answer
#include<iostream>
using namespace std;
int quarter=25; //intializing quarter and dime values in cents
int dime=10;
char stack[20]; //stack to hold the number of changes>> q for quarter and d for dime
int top=-1;
void push(char d)//push operation on stack
{
stack[++top] = d;
}
char pop()//pop operation on stack
{
return stack[top--];
}
void display()//displaying stack at any point of time
{
for(int i=0; i<=top; i++)
{
if(stack[i] == 'q')
cout<<"quarter, ";
else
cout<<"dime, ";
}
cout<<" ";
}
void rec(int t)//recursive function to find number of changes in exponential manner
{
static int ways=0;//counting number of ways
if(t==0)
{
++ways;
cout<<"way: "<<ways<<" >> ";
display();
}
if(t >= quarter)
{
push('q');
rec(t-quarter);
}
if(t >= dime)
{
push('d');
rec(t-dime);
}
pop();
}
int main()
{
int ticket;//taking input of ticket value in cents
cout<<"Enter ticket value in cents: ";
cin >> ticket;
cout<<" ";
rec(ticket);
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.