• API
• FAQ
• Tools
• Archive
daily pastebin goal
51%
SHARE
TWEET

# Untitled

a guest Mar 22nd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package edu.miracosta.cs113.change;
2.
3. import java.io.File;
4. import java.io.FileWriter;
5. import java.io.IOException;
6. import java.io.PrintWriter;
7. import java.util.ArrayList;
8.
9. /**
10.  * ChangeCalculator : Class containing the recursive method calculateChange, which determines and prints all
11.  * possible coin combinations representing a given monetary value in cents.
12.  * <p>
13.  * Problem derived from Koffman & Wolfgang's Data Structures: Abstraction and Design Using Java (2nd ed.):
14.  * Ch. 5, Programming Project #7, pg. 291.
15.  * <p>
16.  * NOTE: An additional method, printCombinationsToFile(int), has been added for the equivalent tester file to
17.  * verify that all given coin combinations are unique.
18.  */
19. public class ChangeCalculator {
20.
21.
22.     //coin value
23.     static int[] coins = {1, 5, 10, 25};
24.
25.     //combination of array.
26.     /*
27.         Example. "15"
28.         1 1 1 1 1 1 1... (15 times) pennnies
29.         2 2 2 2 2 ( nickel and  10 pennies ) 3 3 3 3 3 (2nickel 5 pennies) 4 4 4 4 4(3nickel 0 penny)
30.         5 5 5 5 5 (dime and 5penny) 6 6 6 6 6 (dime nickel)
31.
32.
33.      */
34.     static int[] combinations;
35.
36.     /*
37.     ArrayList to track the combinations in string
38.      */
39.     private static ArrayList<String> combos = new ArrayList<>();
40.
41.
42.     public static void main(String[] args) {
43.         System.out.println(calculateChange(15));
44.
45.     }
46.
47.     /**
48.      * Wrapper method for determining all possible unique combinations of quarters, dimes, nickels, and pennies that
49.      * equal the given monetary value in cents.
50.      * <p>
51.      * In addition to returning the number of unique combinations, this method will print out each combination to the
52.      * console. The format of naming each combination is up to the user, as long as they adhere to the expectation
53.      * that the coins are listed in descending order of their value (quarters, dimes, nickels, then pennies). Examples
54.      * include "1Q 2D 3N 4P", and "[1, 2, 3, 4]".
55.      *
56.      * @param cents a monetary value in cents
57.      * @return the total number of unique combinations of coins of which the given value is comprised
58.      */
59.     public static int calculateChange(int cents) {
60.         //Create a static variable that holds the amount of cents. Include one more for empty value.
61.         combinations = new int[cents + 1];
62.
63.         //Set the first element to zero because there's only one way to make 0cents. i.e 0 coints.
64.         combinations[0] = 1;
65.
66.         // Iterate with the number of coins we have
67.         for (int i = 0; i < coins.length; i++) {
68.
69.             // Once its higher than its value we can store it and make a counter.
70.             for (int j = 0; j < combinations.length; j++) {
71.                 if (coins[i] <= j)  //once its value is bigger than the loop we can keep expanding our count. recursively using an array.
72.                     // Update the array by grabbing its old value and adding to it with the new number
73.                     combinations[j] += combinations[j - coins[i]];
74.
75.             }
76.         }
77.
78.
79.
80.
81.         // return the value at the position of cents (last index)
82.         makeChange(cents, 0, 0, 0, cents);
83.         printCombinationsToFile(cents);
84.         return combinations[cents];
85.     }
86.
87.
88.     public static void makeChange(int total, int q, int d, int n, int p) {
89.
90.         final int QUARTER = coins[3], DIME = coins[2], NICKEL = coins[1], PENNY = coins[0];
91.
92.         if (q * QUARTER + d * DIME + n * NICKEL + p * PENNY > total) {
93.             return;
94.         }
95.
96.         //Combination in string
97.         String s = "[" + q + ", " + d + ", " + n + ", "
98.                 + p + "]";
99.
100.         if (!combos.contains(s))
102.
103.
104.         // Recursive Cases
105.         if (p >= 5)
106.             makeChange(total, q, d, n + 1, p - 5);
107.         if (p >= 10)
108.             makeChange(total, q, d + 1, n, p - 10);
109.         if (p >= 25)
110.             makeChange(total, q + 1, d, n, p - 25);
111.     }
112.
113.     /**
114.      * Calls upon calculateChange(int) to calculate and print all possible unique combinations of quarters, dimes,
115.      * nickels, and pennies that equal the given value in cents.
116.      * <p>
117.      * Similar to calculateChange's function in printing each combination to the console, this method will also
118.      * produce a text file named "CoinCombinations.txt", writing each combination to separate lines.
119.      *
120.      * @param cents a monetary value in cents
121.      */
122.     public static void printCombinationsToFile(int cents) {
123.         // TODO:
124.         // This when calculateChange is complete. Note that the text file must be created within this directory.
125.         try {
126.             PrintWriter pw = new PrintWriter(new FileWriter(new File(System.getProperty("user.dir") + "\\src\\edu.miracosta.cs113\\change\\CoinCombinations.txt")));
127.             for (String s : combos) {
128.                 pw.println(s);
129.             }
130.             pw.close();
131.         } catch (IOException e) {
132.             e.printStackTrace();
133.         }
134.     }
135.
136. } // End of class ChangeCalculator
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top