# Creating a program to determine least amount of coins with values that aren't factors

• 05-28-2012, 06:59 PM
Kore
Creating a program to determine least amount of coins with values that aren't factors
Sorry for having to post code for such a beginner program, but I can't find the error.

I have a problem determining the least amount of coins and in an early version, have compiled a working model, but the values are off. I have found the error to be in the two methods findAmount & findAmountCoin to do with finding the value of the arrays trungir, and throan.
Due to the odd values of the coins I attempted to calculate all outcomes and then would find the least. Right now I output all the info to find the error.
If you look at it, I tried to add 1 trungir and minus 100 grumbles then calculate throans. Then find the least amount of total coins, but I return a value of zero.

Thank you,

Here was the project: a bit sloppy
Code:

```/* Problem: Middle Earth * * Contrary to popular belief, hobbits and other inhabitants of Middle Earth had a thriving commercial system. * They used both coins and paper currency like ours, but theirs had strange (to us) relative values. Instead of dollars, they used trungirs. Instead of cents they had grumbles. * They used powers-of-two trungirs for their notes (i.e. 1, 2, 4, 8, 16...), and had various odd coins worth different numbers of grumbles. * Happily, there were 100 grumbles to the trungir. In addition to the 1-grumble coin (called grunt), there were groans, moans, whevs, and throans. * * 1 groan = 3 grumbles * 1 moan = 11 grumbles * 1 whev = 22 grumbles * 1 throan = 47 grumbles * 1 trungir = 100 grumbles * * Although there were no McDonald's in Middle Earth, many hobbits made extra cash by running little chafes (hobbit cafes) that sold breakfasts (and second breakfasts) and takeout for other meals, * since it is well known that hobbits love to eat. You've been transported back to the times of Middle Earth, and it is your job to minimize the number of pieces of currency that the proprieter * of a chafe returns in change, for a given order. Since hobbits are always hungry they always have a spare 8-trungir bill with them to pay for their order, which is never more than 8 trungirs. * Write a program that inputs two integer values (n1, n2) which represents the total cost of the order: n1 trungirs plus n2 grumbles. * Output the correct change, assuming the customer pays with an 8-trungir bill, minimizing the pieces of currency that have to be returned. * For example, if the bill comes to 3 trungirs and 49 grumbles, the change will be a 4-trungir note, a throan, a groan, and a grunt. * * Me: in early stages of developing system to caculate lowest value * Caculates all values for 1 to grumbles */ public class Hobbit {                 // variables placed in different methods to find value of trungir and throans throughout proccess         static int t1 = 0;         static int g1 = 0;         static int t2 = 0;         static int g2 = 0;         static int t3 = 0;         static int g3 = 0;         // arrays placed in findAmount line 164 to take the sum of each loop of the arrays coin and var         static int[] sumI = new int[10];         static int[] sumG = new int[10];                 public static void main(String[] args)         {                         // unused variables         int trungir1 = 0, trungir2 = 0, trungir4 = 0, trungir8 = 0;         int  throan = 0, whev = 0, moan = 0, groan = 0, grumbles = 0;                         // arrays that return the value of array var from findAmount each var# based off         int [] var0 = new int[6];         int [] var1 = new int[6];         int [] var2 = new int[6];         int [] var3 = new int[6];         int [] var4 = new int[6];         int [] var5 = new int[6];         int [] var = new int [6];         final int GRUMBLES = grumbles;                 // loops 800 times for all the possible values         // arrays that return the value of array var from findAmount each var# based off the value of each piece of currency, second value given         // i is value of grumbles         for (int i = 0; i <= 800; i ++)         {         grumbles = i;         var0 = findAmount(i, 100);         var1 = findAmount(i, 47);         var2 = findAmount(i, 22);         var3 = findAmount(i, 11);         var4 = findAmount(i, 3);         var5 = findAmount(i, 1);                                 //output                         // sum of the var#         var[0] = var0[0]+var0[1]+var0[2]+var0[3]+var0[4]+var0[5];         var[1] = var1[0]+var1[1]+var1[2]+var1[3]+var1[4]+var1[5];         var[2] = var2[0]+var2[1]+var2[2]+var2[3]+var2[4]+var2[5];         var[3] = var3[0]+var3[1]+var3[2]+var3[3]+var3[4]+var3[5];         var[4] = var4[0]+var4[1]+var4[2]+var4[3]+var4[4]+var4[5];         var[5] = var5[0]+var5[1]+var5[2]+var5[3]+var5[4]+var5[5];                 // finds the sum that is least then prints. Next prints amount that of i when passed to findAmount;                 if (var[0]<=var[1]&&var[0]<=var[2]&&var[0]<=var[3]&&var[0]<=var[4]&&var[0]<=var[5])                 {                 System.out.println("var0: "+grumbles);                        }                 else if (var[1]<=var[2]&&var[1]<=var[3]&&var[1]<=var[4]&&var[1]<=var[5]) {                 System.out.println("var1: "+grumbles);                        }                 else if (var[2]<=var[3]&&var[2]<=var[4]&&var[2]<=var[5]) {                 System.out.println("var2: "+grumbles);                        }                 else if (var[3]<=var[4]&&var[3]<=var[5]) {                 System.out.println("var3: "+grumbles);                 }                 else if(var[4]<=var[5])  {                 System.out.println("var4: "+grumbles);                        }                 else  {                 System.out.println("var5: "+grumbles);                        }                         // each individual coin value: trungir then throan...whev...moan...groan...grumble.......and finally the value of i again         System.out.println(var0[0]+"  "+var0[1]+"  "+var0[2]+"  "+var0[3]+"  "+var0[4]+ "  "+ var0[5]  + "\t" + GRUMBLES + grumbles);         System.out.println(var1[0]+"  "+var1[1]+"  "+var1[2]+"  "+var1[3]+"  "+var1[4]+ "  "+ var1[5]  + "\t" + GRUMBLES + grumbles);         System.out.println(var2[0]+"  "+var2[1]+"  "+var2[2]+"  "+var2[3]+"  "+var2[4]+ "  "+ var2[5]  + "\t" + GRUMBLES + grumbles);         System.out.println(var3[0]+"  "+var3[1]+"  "+var3[2]+"  "+var3[3]+"  "+var3[4]+ "  "+ var3[5]  + "\t" + GRUMBLES + grumbles);         System.out.println(var4[0]+"  "+var4[1]+"  "+var4[2]+"  "+var4[3]+"  "+var4[4]+ "  "+ var4[5]  + "\t" + GRUMBLES + grumbles);         System.out.println(var5[0]+"  "+var5[1]+"  "+var5[2]+"  "+var5[3]+"  "+var5[4]+ "  "+ var5[5]  +  "\t" + GRUMBLES + grumbles);         // sum of arrays coin and var around line 161, for each of the time it loops         System.out.println(sumI[0]+"  "+sumI[1]+"  "+sumI[2]+"  "+sumI[3]+"  "+sumI[4]+ "  "+ sumI[5]  + "  "+ sumI[6]+"  "+sumI[7]+"  "+sumI[8]+"  "+sumI[9]);         System.out.println(sumG[0]+"  "+sumG[1]+"  "+sumG[2]+"  "+sumG[3]+"  "+sumG[4]+ "  "+ sumG[5]  + "  "+ sumG[6]+"  "+sumG[7]+"  "+sumG[8]+"  "+sumG[9]);         // scattered values printed of throans and trungirs used to tell where error is.         System.out.println(g1 + "g1 " + t1 + "t1 " + t2 + "t2 " + g2 + "g2 "+ t3 + "t3 " + g3 + "g3 ");         }                         } // end main method                         public static int[] findAmount(int a, int b)         {                 // to keep value of entered grumbles or 1 cents                 final int G = a;                                                 int[] throan = new int[9];                 throan[0] = 0; throan[1] = 0; throan[2] = 0; throan[3] = 0; throan[4] = 0; throan[5] = 0; throan[6] = 0; throan[7] = 0; throan[8] = 0; // used only if b == 100                 int[] var = new int[5];                        // returned array                 var = throan;                 int[] trungir = new int[9];                // used in calculating trungirs and throans if b == 100;                 trungir = throan;                 int[] grumble = new int[9];                // repeat                 grumble = throan;                 int[] coin = new int[5];                // sum of all used to compare next value to previous value in loop finding lowest value of coins. only if b ==100                 coin = throan;                 int count = 0;                                        // used to count while loop                 int sumOf1 = 0;                                        // sum of var                 int sumOf2 = 0;                                        // sum of coin                 if(b==100)                 {                         var[0] = a/b;                                // not crucial                         a = a%b;                                        // for caculating similar to else in beginning of findAmountCoin                         t1 = var[0];                                                 int h = G;                                        // variable created not to corrupt value of a that should be passed since this is a test                         while(h > 0)                         {                                                                         throan[count] = h/47;        // find possible amount of 47 cent for each loop                                 grumble[count] = h%100; // find possible amount of 1 cent for each loop                                                                 count ++;                // counter                                                                 if (count>0) // ex. of what is trying to be done. 800 grumbles passed total value of throan and grumbles caculated. total grumbles - 100, loop again grumbles and                                                         // throans are caculated, but 1 coin value is added to trungir                                 {                                 trungir[count] += 1;                                 }                                 h -= 100;                         } // end while(a > 0)                                                 int cont = 0; // another count variable                                         t3 = trungir[0]; // variable to display value at this point                         g2 = throan[0];                                         while (cont<=8)                         {                                 b = 22;                                 var[0] = trungir[cont];// var is passed and trungir/throan/grumble value add with counter changing with array variable is chosen, b = 27 to skip throan value since it has                                 var[1] =throan[cont];        // been calculated                                        coin = findAmountCoin( grumble[cont], b , var);                                                                 sumOf1 =  var[0]+var[1]+var[2]+var[3]+var[4]+var[5]; // sum of total var, compared to total coin, var will be previous value while coin is next value tested to see                                 sumOf2 = coin[0]+coin[1]+coin[2]+coin[3]+coin[4]+coin[5]; // which is largier                                 sumI[cont] = sumOf2;                                 sumG[cont] = sumOf1;                                                                 if (sumOf1 > sumOf2) { // determines if the sum of var is greater than coin to determine if it needs to change the value of var to value of the leastest amount of coins                                 var = coin;                                        }                                                                                 //t3 = var[0];                                 //g2 = var[1];                                                                        cont ++; // counter                         }                                         }                 else                  {                         var = findAmountCoin(a, b, var); // if value isn't equal to 100, no problems seen value is used over  b ==100                 }                                                 return var; // returns var                         }                 public static int[] findAmountCoin(int a, int b, int[] c)         {         if (c[0]*100+c[1]*47==a) // determines if b was equivalent to 100         {                         }                else // else the amount of trungir is calculated then all other coin values         {         c[0]=a/100;         a = a%100;                }         if(b == 47)                // if used to determine what was passed down from findAmount, orginally main method                 {                                                 g3 = c[1];                         c[1] = a%b;                         b = 22;                 }         if(b == 22)                 {                         c[2] = a/b;                         a = a%b;                         b = 11;                 }         if(b == 11)                 {                         c[3] = a/b;                         a = a%b;                         b = 3;                 }         if (b == 3)                 {                         c[4] = a/b;                         a = a%b;                         b = 1;                 }         if (b == 1)                 {                         c[5] = a/b;                         a = a%b;                 }                                                 return c; // // returns: var = c                                 } // end method findAmountCoin         } // end class Hobbit```
• 05-28-2012, 09:03 PM
Norm
Re: Creating a program to determine least amount of coins with values that aren't fac
Quote:

I return a value of zero.
Can you show the console from when you execute the program? Add some comments to it to show what you want the output to be.

Do you understand integer math? 4/5 = 0 vs 4.0/5 = 0.8
• 05-29-2012, 12:03 AM
Kore
Re: Creating a program to determine least amount of coins with values that aren't fac
Quote:

Originally Posted by Norm
Can you show the console from when you execute the program? Add some comments to it to show what you want the output to be.

Do you understand integer math? 4/5 = 0 vs 4.0/5 = 0.8

I do understand integer math that the value is rounded down when the value is not a whole number, but what are you referring to. The common equation is a/b then a%b, which is 99/47 = 2, then 99%47 = 5 which would be passed on and the process would be repeated with the next values. which would be 5/22 = 0 then 5%22 = 5.

I am confused with what you mean about show the console from when you execute the program. I really couldn't, I wouldn't know since it prints,several thousand lines, I don't know how to show that. I'm also confused with how I would add comments, since the program runs ever value 1 to 800, and 5 different ways it would be hard to find the actual value for the 800. The error is specific to lines 131 to 171 and the method it calls, and the arrays trungir, throan, coin, and var have all their values set to zero (new to arrays) when they should return the amount of the specific currency piece. If you run it, you will see a line with the variable with the leastest amount of coins, which is always var0, due to it always equaling zero, then the amount of 1 value currency. The next lines are the amount of trungirs first, then throans, then whevs, next moans, then groans, and finally grumbles, then the starting amount of grumbles or amount of 1 value currency. Next lines are the sum of the coin array and var array in the findAmount method. And finally the value of trungirs and throans at increments during the test.
• 05-29-2012, 12:20 AM
Norm
Re: Creating a program to determine least amount of coins with values that aren't fac
Without guidance from you that shows where the output is wrong and says what it should be, it can be a waste of time running a program if there is not something specific to look for.

You need to add some special code to your program for testing so that when it executes it prints out a few lines that shows the problem. I don't want to run a program that generates 1000s of lines of output.
• 05-29-2012, 01:55 AM
Kore
Re: Creating a program to determine least amount of coins with values that aren't fac
I narrowed down the output to print what the value should equal and it will only test the variable twice

Code:

```public class Hobbit {         public static void main(String[] args)         {                 // arrays that return the value of array var from findAmount each var# based off         int [] var0 = new int[6];         int [] var = new int [6];                 // test 1         int i = 799;                        var0 = findAmount(i, 100);                 var[0] = var0[0]+var0[1]+var0[2]+var0[3]+var0[4]+var0[5];                 System.out.println(var0[0]+"==7 Trungirs    "+var0[1]+"==2 Throans "+var0[2]+"==0 Whevs "+var0[3]+"==0 Moans "+var0[4]+ "==1 Groan "+ var0[5]  + "==2 Grumbles \t" + i + " is the total");                 // test 2         i = 141;                         var0 = findAmount(i, 100);                         var[0] = var0[0]+var0[1]+var0[2]+var0[3]+var0[4]+var0[5];                         System.out.println(var0[0]+"==0 Trungirs    "+var0[1]+"==3 Throans "+var0[2]+"==0 Whevs "+var0[3]+"==0 Moans "+var0[4]+ "==0 Groans "+ var0[5]  + "==0 Grumbles \t" + i + " is the total");         } // end main method                         public static int[] findAmount(int a, int b)         {                 // to keep value of entered grumbles or 1 cents                 final int G = a;                                                 int[] throan = new int[9];                 throan[0] = 0; throan[1] = 0; throan[2] = 0; throan[3] = 0; throan[4] = 0; throan[5] = 0; throan[6] = 0; throan[7] = 0; throan[8] = 0; // used only if b == 100                 int[] var = new int[5];                        // returned array                 var = throan;                 int[] trungir = new int[9];                // used in calculating trungirs and throans if b == 100;                 trungir = throan;                 int[] grumble = new int[9];                // repeat                 grumble = throan;                 int[] coin = new int[5];                // sum of all used to compare next value to previous value in loop finding lowest value of coins. only if b ==100                 coin = throan;                 int count = 0;                                        // used to count while loop                 int sumOf1 = 0;                                        // sum of var                 int sumOf2 = 0;                                        // sum of coin                                                                         int h = G;                                        // variable created not to corrupt value of a that should be passed since this is a test                         while(h > 0)                         {                                                                         throan[count] = h/47;        // find possible amount of 47 cent for each loop                                 grumble[count] = h%100; // find possible amount of 1 cent for each loop                                                                 count ++;                // counter                                                                 if (count>0) // ex. of what is trying to be done. 800 grumbles passed total value of throan and grumbles caculated. total grumbles - 100, loop again grumbles and                                                         // throans are caculated, but 1 coin value is added to trungir                                 {                                 trungir[count] += 1;                                 }                                 h -= 100;                         } // end while(a > 0)                                                 int cont = 0; // another count variable                                                         while (cont<=8)                         {                                 b = 22;                                 var[0] = trungir[cont];// var is passed and trungir/throan/grumble value add with counter changing with array variable is chosen, b = 27 to skip throan value since it has                                 var[1] =throan[cont];        // been calculated                                        coin = findAmountCoin( grumble[cont], b , var);                                                                 sumOf1 =  var[0]+var[1]+var[2]+var[3]+var[4]+var[5]; // sum of total var, compared to total coin, var will be previous value while coin is next value tested to see                                 sumOf2 = coin[0]+coin[1]+coin[2]+coin[3]+coin[4]+coin[5]; // which is largier                                                                         if (sumOf1 > sumOf2) { // determines if the sum of var is greater than coin to determine if it needs to change the value of var to value of the leastest amount of coins                                 var = coin;                                        }                                 cont ++; // counter                         }                                                         return var; // returns var                         }                 public static int[] findAmountCoin(int a, int b, int[] c)         {                 if(b == 47)                // if used to determine what was passed down from findAmount, orginally main method                 {                         c[1] = a%b;                         b = 22;                 }         if(b == 22)                 {                         c[2] = a/b;                         a = a%b;                         b = 11;                 }         if(b == 11)                 {                         c[3] = a/b;                         a = a%b;                         b = 3;                 }         if (b == 3)                 {                         c[4] = a/b;                         a = a%b;                         b = 1;                 }         if (b == 1)                 {                         c[5] = a/b;                         a = a%b;                 }                                                 return c; // // returns: var = c                                 } // end method findAmountCoin         } // end class Hobbit```
• 05-29-2012, 02:25 AM
Norm
Re: Creating a program to determine least amount of coins with values that aren't fac
Can you post the code's output and explain what is wrong with it?
Also Show what it should be.
• 05-29-2012, 12:47 PM
JosAH
Re: Creating a program to determine least amount of coins with values that aren't fac
Suppose you have a monetary system of 1, 3, 7 and 8 (values of the coins); for this particual monetary system chopping off as many of the largest coins as possible and continue the process with the rest of the amount doesn't work; i.e. you don't end up with the least amount of coins; example: 10 == 8+1+1 but 10 == 7+3 is a 'better' solution. You have to check if your monetary system posesses this property.

kind regards,

Jos