Question

7. In the United States there are six coins in general circulation: 1, 5, 10, 25, 50, 100 cent coins
It is possible to make change for 10 cents in the following ways: 1 dime, 2 nickels, 1 nickel 5 pennies, 10 pennies

Write a function, make_change that accepts an integer number of cents and calculates how many different ways one can make change for that amount using any number of coins, returning the integer count. What is the answer for 2 dollars?

Answer 1

//C++ program

#include<iostream>
using namespace std;

int count( int n )
{
int i, j, x, y;
int S[] = {1,5,10,25,50,100};
int m=sizeof(S)/sizeof (int);
int table[n+1][m];
  
for (i=0; i<m; i++)
table[0][i] = 1;
  
for (i = 1; i < n+1; i++)
{
for (j = 0; j < m; j++)
{
x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

  
y = (j >= 1)? table[i][j-1]: 0;

table[i][j] = x + y;
}
}
  
return table[n][m-1];
}

int main()
{
cout<<"Total possible coin change for 2 dollar = "<<count(200);
return 0;
}

//sample output