Last active
December 23, 2015 20:59
-
-
Save chihuahua/6693081 to your computer and use it in GitHub Desktop.
Calculates the number of ways to make change for x cents using half dollars, quarters, dimes, nickels, pennies.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * makeChange.c | |
| * Calculates the number of ways to make change for x cents | |
| * using half dollars, quarters, dimes, nickels, pennies. | |
| * | |
| * @author Chi Zeng ([email protected]) | |
| * Sep. 24, 2013 | |
| */ | |
| #include <stdio.h> | |
| // Helper function for @numWaysForChange. | |
| int numWaysForChangeHelper(int cents, int denom) { | |
| // Find the next smallest denomination. | |
| int nextDenom; | |
| if (denom == 50) { | |
| nextDenom = 25; | |
| } if (denom == 25) { | |
| nextDenom = 10; | |
| } else if (denom == 10) { | |
| nextDenom = 5; | |
| } else if (denom == 5) { | |
| nextDenom = 1; | |
| } else if (denom == 1) { | |
| // Our base case: We can only make change using only pennies in 1 way. | |
| return 1; | |
| } | |
| // Add up the different ways. | |
| int ways = 0; | |
| for (int i = 0; i * denom <= cents; ++i) { | |
| int centsLeft = cents - i * denom; | |
| ways += numWaysForChangeHelper(centsLeft, nextDenom); | |
| } | |
| return ways; | |
| } | |
| /** | |
| * Determines the number of ways to make change. | |
| * @param cents the number of cents to make change for. | |
| * @return the number of ways to make change. | |
| */ | |
| int numWaysForChange(int cents) { | |
| return numWaysForChangeHelper(cents, 50); | |
| } | |
| // Lets see how many ways there are to make change for a dollar. | |
| int main() { | |
| int cents = 100; | |
| int numWays = numWaysForChange(cents); | |
| printf("You can make change for %d cents in %d ways.\n", cents, numWays); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment