Problem
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent),
write code to calculate the number of ways of representing n cents.
Solution
#include <iostream>
using namespace std;
// if next_change is set, cannot use a coin with high number
static int coins[4] = {25, 10, 5, 1};
static int total_ways = 0;
static void print_changes(int changes[], int times, int next_change, int n)
{
if(n < 0){
return;
}
else if(n == 0){
for(int i = 0; i < times; i ++){
cout << changes[i] << " ";
}
cout << endl;
total_ways ++;
return;
}
if(n >= 25 && next_change == 25){
for(int i = 0; i < 4; i++){
changes[times] = coins[i];
print_changes(changes, times + 1, coins[i], n - coins[i]);
}
}
if((n >= 10 && next_change == 10) || (n >= 10 && n < 25 && next_change > 10)){
for(int i = 1; i < 4; i++){
changes[times] = coins[i];
print_changes(changes, times + 1, coins[i], n - coins[i]);
}
}
if((n >= 5 && next_change == 5) || (n >= 5 && n < 10 && next_change > 5)){
for(int i = 2; i < 4; i++){
changes[times] = coins[i];
print_changes(changes, times + 1, coins[i], n - coins[i]);
}
}
if((n >= 1 && next_change == 1) || (n >= 1 && n < 5 && next_change > 1)){
for(int i = 3; i < 4; i++){
changes[times] = coins[i];
print_changes(changes, times + 1, coins[i], n - coins[i]);
}
}
}
static int make_change2(int n, int denom) {
int next_denom = 0;
switch (denom){
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int ways = 0;
for (int i = 0; i * denom <= n; i++) {
ways += make_change2(n - i * denom, next_denom);
}
return ways;
}
int main(int argc, char* argv[])
{
int changes[100];
print_changes(changes, 0, 25, 41);
cout << total_ways << endl;
cout << make_change2(41, 25) << endl;
return 0;
}
Output
25 10 5 1
25 10 1 1 1 1 1 1
25 5 5 5 1
25 5 5 1 1 1 1 1 1
25 5 1 1 1 1 1 1 1 1 1 1 1
25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 10 10 10 1
10 10 10 5 5 1
10 10 10 5 1 1 1 1 1 1
10 10 10 1 1 1 1 1 1 1 1 1 1 1
10 10 5 5 5 5 1
10 10 5 5 5 1 1 1 1 1 1
10 10 5 5 1 1 1 1 1 1 1 1 1 1 1
10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 5 5 5 5 5 5 1
10 5 5 5 5 5 1 1 1 1 1 1
10 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1
10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5 5 1
5 5 5 5 5 5 5 1 1 1 1 1 1
5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
31
31