Results 1 to 7 of 7
  1. #1
    Kore is offline Member
    Join Date
    May 2012
    Posts
    3
    Rep Power
    0

    Default 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.

    Please read what the project is.
    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
    PHP 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
    Last edited by Kore; 05-29-2012 at 12:54 AM. Reason: Added comments to help make it understandable

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Creating a program to determine least amount of coins with values that aren't fac

    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
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    Kore is offline Member
    Join Date
    May 2012
    Posts
    3
    Rep Power
    0

    Default Re: Creating a program to determine least amount of coins with values that aren't fac

    Quote Originally Posted by Norm View Post
    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.

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default 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.
    If you don't understand my response, don't ignore it, ask a question.

  5. #5
    Kore is offline Member
    Join Date
    May 2012
    Posts
    3
    Rep Power
    0

    Default 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

    PHP 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

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default 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.
    If you don't understand my response, don't ignore it, ask a question.

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,365
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Creating an amount of variables based on user input
    By HDInfinity in forum New To Java
    Replies: 4
    Last Post: 04-11-2012, 08:23 AM
  2. Replies: 11
    Last Post: 11-01-2011, 02:47 AM
  3. Replies: 0
    Last Post: 03-18-2011, 08:48 PM
  4. Replies: 4
    Last Post: 11-03-2010, 06:17 PM
  5. Replies: 0
    Last Post: 08-21-2008, 01:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •