Page 1 of 1

Need advice/suggestion with recursive java program

Posted: Sat Feb 03, 2007 10:26 pm
by matt1019
Hi guys,

I would very much appreciate if someone can point me in the right direction with this assignment. I do not want the full-fledge code to solving this... i have gone half the distance already. only the recursive part I DO NOT UNDERSTAND :(

OK, here's the problem statement:
Write a recursive program which enumerates all the ways to give the change in coins (quarters,
dimes, nickels, pennies) for a given amount of money. That is, given a target sum s it should
produce a collection of arrays of size 4 (e.g., [8, 3, 1, 2], [9, 0, 2, 2], ... for a target amount of 2.37)
giving the number of coins of each type. The input to the program will be a single number given on
the standard input. The output will be a sequence of lines, where each line is a quadruple enclosed
in square brackets and the 4 numbers are separated by commas and denote the number of coins of
each denomination (quarter,dime,nickel,penny).
What I have done so far - (basically everything except the recursive method):
take the input from the user [using Scanner]
and pass it to the recursive method.

However, if someone can explain the workings of this darn method, that would be very helpful.

Thanks.

-Matt

Posted: Sat Feb 03, 2007 10:39 pm
by feyd
I would probably have a mapping of the various least number of coins constant a particular coin can break down into.. for example, a quarter into two dimes and a nickel; a dime into two nickels; etc etc.

Then find the least coin variant of the amount.. then recurse into breaking them down from there iteratively until it reaches the maximum number of coins.

Posted: Sun Feb 04, 2007 1:52 am
by Chris Corbyn
Yeah you want to get the highest multiple each coin makes, then find the "highest common factor" between your desired sum of money, and each type of coin. If you get a HCF, you need that many coins, then recurse down all the coin types collecting the HCFs as you go until you've got no money left.

You'll want to get rid of any decimal places by turning everything into units of the smallest amount first because the decimal will make it a nightmare to do bitwise operations.

Here's a function to get Highest Common Factors:

Code: Select all

function getHcf($value, $factor)
{
        return ($value - ($value % $factor));
}

Posted: Sun Feb 04, 2007 5:44 am
by volka
d11wtq wrote:Yeah you want to get the highest multiple each coin makes, then find the "highest common factor" between your desired sum of money, and each type of coin. If you get a HCF, you need that many coins, then recurse down all the coin types collecting the HCFs as you go until you've got no money left.
That's a greedy algorithm for the least amount of coins. But
problem statement wrote:Write a recursive program which numerates all the ways to give the change in coins (quarters, dimes, nickels, pennies) for a given amount of money.
That sounds like backtracking (i suppose you already had greedy and the next topic will be branch-and-bound).

You have a (remaining) amount of money, a set of coins to choose from and something that keeps track of what's been done until now. If your amount is 0 you have a possible way. You can pick each coin with a value less or equal to the remaining amount. Test each coin. If it is it less or equal to the remainig amount pick it and repeat the procedure with [amount minus coin's value].
e.g. the remaining amount is 7. You can't take a quarter: 7-25<0 :arrow: not feasible. You can't take a dime: 7-10 nf. (a) You can pick a nickel, remaining amount 2. Or (b) you can pick a penny, remaining amount 6

Code: Select all

7 - 25 f
7 - 10 nf
7 - 5 -> pick a nickel (a)
  2 - 25 nf
  2 - 10 nf
  2 - 5 nf
  2 - 1 -> pick a penny
    1 - 25 nf
    1 - 10 nf
    1 - 5 nf
    1 - 1 -> pick a penny
      0 -> possible way (n,p,p)
7 - 1 -> pick a penny (b)
  6 - 25 nf
  6 - 10 nf
  6 - 5 -> pick a nickel
    1 - 25 nf
    1 - 10 nf
    1 - 5 nf
    1 - 1 -> pick a penny
      0 possible way (p,n,p)
  6 - 1 -> pick a penny
    5 - 25 nf
    5 - 10 nf
    5 - 5 -> pick a nickel
      0 possible way(p,p,n)
    5 - 1 -> pick a penny
      4 - 25 nf
      ...
              0 possible way(p,p,p,p,p,p,p)

php demonstration

Code: Select all

<?php
function foo($remainingAmount, $sequence) {
	/*static */ $coins = array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1);
	
	/* If your amount is 0 you're done. */
	if ( 0==$remainingAmount ) {
		echo "possible sequence: ", $sequence, "\n";
		return;
	}

	/* You can pick each coin with a value less or equal to the remaining amount.
	Test each coin. */
	foreach($coins as $coinSymbol=>$coinValue) {
		/* If it is it less or equal to the remainig amount */
		if ( $remainingAmount>=$coinValue ) {
			/* pick it and repeat the procedure (amount minus coin's value) */
			foo($remainingAmount-$coinValue, $sequence.$coinSymbol);
		}
	}
}

foo(7, '', 1);
?>
possible sequence: npp
possible sequence: pnp
possible sequence: ppn
possible sequence: ppppppp
The first three ways are semantically the same - the customer gets two pennies and a nickel.
Possible solution: only allow coins with values equal or less to the current coin for following steps. If you just picked a dime do not try to pick a quarter afterwards but try a dime or a nickel or a penny.
crude php demonstration (that really isn't a good example. sorry)

Code: Select all

<?php
function foo($remainingAmount, $coins, $sequence) {
	if ( 0==$remainingAmount ) {
		echo "possible sequence: ", $sequence, "\n";
		return;
	}

	reset($coins);
	while( list($coinSymbol,$coinValue)=each($coins) ) {
		if ( $remainingAmount>=$coinValue ) {
			foo($remainingAmount-$coinValue, $coins, $sequence.$coinSymbol);
		}
		array_shift($coins);
	}
}


foo(7, array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1), '');
?>

Posted: Sun Feb 04, 2007 11:09 am
by matt1019
volka wrote:
d11wtq wrote:Yeah you want to get the highest multiple each coin makes, then find the "highest common factor" between your desired sum of money, and each type of coin. If you get a HCF, you need that many coins, then recurse down all the coin types collecting the HCFs as you go until you've got no money left.
That's a greedy algorithm for the least amount of coins. But
problem statement wrote:Write a recursive program which numerates all the ways to give the change in coins (quarters, dimes, nickels, pennies) for a given amount of money.
That sounds like backtracking (i suppose you already had greedy and the next topic will be branch-and-bound).

You have a (remaining) amount of money, a set of coins to choose from and something that keeps track of what's been done until now. If your amount is 0 you have a possible way. You can pick each coin with a value less or equal to the remaining amount. Test each coin. If it is it less or equal to the remainig amount pick it and repeat the procedure with [amount minus coin's value].
e.g. the remaining amount is 7. You can't take a quarter: 7-25<0 :arrow: not feasible. You can't take a dime: 7-10 nf. (a) You can pick a nickel, remaining amount 2. Or (b) you can pick a penny, remaining amount 6

Code: Select all

7 - 25 f
7 - 10 nf
7 - 5 -> pick a nickel (a)
  2 - 25 nf
  2 - 10 nf
  2 - 5 nf
  2 - 1 -> pick a penny
    1 - 25 nf
    1 - 10 nf
    1 - 5 nf
    1 - 1 -> pick a penny
      0 -> possible way (n,p,p)
7 - 1 -> pick a penny (b)
  6 - 25 nf
  6 - 10 nf
  6 - 5 -> pick a nickel
    1 - 25 nf
    1 - 10 nf
    1 - 5 nf
    1 - 1 -> pick a penny
      0 possible way (p,n,p)
  6 - 1 -> pick a penny
    5 - 25 nf
    5 - 10 nf
    5 - 5 -> pick a nickel
      0 possible way(p,p,n)
    5 - 1 -> pick a penny
      4 - 25 nf
      ...
              0 possible way(p,p,p,p,p,p,p)

php demonstration

Code: Select all

<?php
function foo($remainingAmount, $sequence) {
	/*static */ $coins = array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1);
	
	/* If your amount is 0 you're done. */
	if ( 0==$remainingAmount ) {
		echo "possible sequence: ", $sequence, "\n";
		return;
	}

	/* You can pick each coin with a value less or equal to the remaining amount.
	Test each coin. */
	foreach($coins as $coinSymbol=>$coinValue) {
		/* If it is it less or equal to the remainig amount */
		if ( $remainingAmount>=$coinValue ) {
			/* pick it and repeat the procedure (amount minus coin's value) */
			foo($remainingAmount-$coinValue, $sequence.$coinSymbol);
		}
	}
}

foo(7, '', 1);
?>
possible sequence: npp
possible sequence: pnp
possible sequence: ppn
possible sequence: ppppppp
The first three ways are semantically the same - the customer gets two pennies and a nickel.
Possible solution: only allow coins with values equal or less to the current coin for following steps. If you just picked a dime do not try to pick a quarter afterwards but try a dime or a nickel or a penny.
crude php demonstration (that really isn't a good example. sorry)

Code: Select all

<?php
function foo($remainingAmount, $coins, $sequence) {
	if ( 0==$remainingAmount ) {
		echo "possible sequence: ", $sequence, "\n";
		return;
	}

	reset($coins);
	while( list($coinSymbol,$coinValue)=each($coins) ) {
		if ( $remainingAmount>=$coinValue ) {
			foo($remainingAmount-$coinValue, $coins, $sequence.$coinSymbol);
		}
		array_shift($coins);
	}
}


foo(7, array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1), '');
?>
Holy cow! Thanks volka!!

Now the only thing to do is to translate this into Java and make necessary tweaks :)

By tweaks I mean this:

You script currently displays "ppppppp" for 7 pennies. Translate that into "7" (so basically no letters, just the # of each type...)

example:
lets use your "7"

this should output:
[# of Quarters, # of dimes, # of nickels, # of pennies]
[0, 0, 1, 2]
[0, 0, 0, 7]


I will post my Java results in the evenin' (or after midnight)

Thanks once again. Looking at the PHP solution made things much clearer!

-Matt

Posted: Mon Feb 05, 2007 12:06 am
by matt1019
damn.

i am too tired working at this :(

I officially hate Java!

I will give it a go again tomorrow (or should I say, later today :? ).

-Matt