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))
  101.             combos.add(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. OK, I Understand
 
Top