Suppose a coin machine sells subway tickets (such as at the DC Metro), where eve

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

/*

check(n, k): number of ways of making change for n cents, using only the first k+1 types of coins.

*/

#include<iostream>

#include<conio.h>

using namespace std;

int C[] = {10, 25};

int check(int n, int k)

{

if (n == 0)

return 1;

if (n < 0 || k < 0)

return 0;

return check(n, k-1) + check(n-C[k], k);

}

int main() {

cout<<"Please input the price of the item in cents ";

int price;

cin>>price;

cout<<"Number of ways of output: "<<check(price,1);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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