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.Assume we need 25 cents, and we want to make changes, how can we do it?
Naturally, we will think of first, get 1 quarter
1. 25cents
Since we only need 25 cents, so at most 1 1 quarter will be used. Then we will think of the next largest domination, dime
2. 10 + 10 + 5
Because we want to add up all coins to 25
Then we further split 1 10 cent to to 5
3. 10 + 5 + 5 + 5
Then we use all 5 cents
4. 5 + 5 + 5 + 5 +5
So each time we use one domination, and find next needed coins based on the cents left, and we can do it recursively.
public class RepresentCents { public static int makeChange(int n) { return ways(n, 25); } public static int ways(int n, int denom){ int next_denom = 0; //find the next largest denomination switch(denom) { case 25: next_denom = 10; break; case 10: next_denom = 5; break; case 5: next_denom = 1; break; //after we use the smallest denomination, //we need to check if all coins have added up to //the desired cents, if they have, return 1 way //otherwise return 0 ways case 1: if (n == 0) return 1; else return 0; } int ways = 0; //check all number of coins can be used in current denomination for (int i = 0; i * denom <= n; i++){ ways += ways(n - i * denom, next_denom); } return ways; } public static void main(String[] args) { System.out.println(makeChange(30)); } }
No comments:
Post a Comment