# need help with a math formula for programming project please



## meanwhile (Dec 13, 2007)

Hello - This is "Meanwhile's" son and she did give me permission to use her User Name and ask for some computer/programming help. 

I am working on a project and am trying to create a program that will calculate all the combinations for making change for a dollar (including using silver dollars and half dollars). I was just going to have the program just add a coin over and over again and remember all the possibilities but it is way too slow. 

I have not had calculus yet but through online research I can see there is a math formula that is supposed to calculate it but I do not know the formula or when I do see a reference to the formula, I do not know how to use it.

I am using PHP 


Any help appreciated -

This is where I am so far in the project BUT it is too slow and it already times my browser out. When I reach the dimes, it already times out.

<html>
<head>
<title>Change</title>
<link rel ="stylesheet" type="text/css" href="sample.css" >
</head>
<body>

<?php
$penny = 1;
$nickel = 5;
$dime = 10;
$quarter = 25;
$halfdollar = 50;
$dollarCoin = 100;
$change = 0;
$dollar = 100;
$count = 0;
$p_count = 0;
$n_count = 0;
$d_count = 0;
$q_count = 0;
$hd_count = 0;
$dc_count = 0;
$maxP = 0;
$maxN = 0;
$maxD = 0;
$maxQ = 0;
$maxHD = 0;
$maxDC = 0;
print("<table border= \"2\"> ");
print("<tr><td>Dollar Coins</td><td>Half-dollars</td><td>Quarters</td><td>Dimes</td><td>Nickels</td><td>Pennies</td>");
while ($change < 100) // penny counter
{
$p_count ++ ;
$maxP = $p_count;
$change = ($penny * $p_count);
print("$maxP,,,$change,,,");
}
print ("<tr> <td>$dc_count</td> <td>$hd_count</td> <td>$q_count</td> <td>$d_count</td> <td>$n_count</td> <td>$p_count</td></p>");
$p_count -= $nickel;
$change = ($nickel * $n_count);
$n_count ++;
while ($change <= 100) // penny and nickel counter
{
if($p_count >= 0 and $change <= 100)
{
print ("<tr> <td>$dc_count</td> <td>$hd_count</td> <td>$q_count</td> <td>$d_count</td> <td>$n_count</td> <td>$p_count</td></p>");
}
$p_count -= 5;
$change = ($nickel * $n_count);
$n_count ++;
}
$n_count = 0;
$p_count = $maxP;
$p_count -= $dime;
$change = ($dime * $d_count);
$d_count ++;
while ($change <= 100) // penny and dime counter
{
if($p_count >= 0 and $change <= 100)
{
print ("<tr> <td>$dc_count</td> <td>$hd_count</td> <td>$q_count</td> <td>$d_count</td> <td>$n_count</td> <td>$p_count</td></p>");
}
$p_count -= 10;
$change = ($dime * $d_count);
$d_count ++;
}

?>
</body>
</html>


----------



## Gary in ohio (May 11, 2002)

The formula is (1-x)(1-x5)(1-x10)(1-x25)(1-x50)(1-x100)
and that will give you 293 possible combinations.


----------



## meanwhile (Dec 13, 2007)

Thank you very much. I have that formula but I have not taken calculus then I don't quite understand how it works. Thus, I do not know how to get the formula into my code. Is "X" supposed to be the number of coins? Or what would the "1-" be? 

Thank you for any pointers. I appreciate the help.


----------



## OntarioMan (Feb 11, 2007)

Somewhat of a "brute force" method below - not so elegant but simple. 

for($p = 0; $p <= 100; $p+=5) { // pennies
for($n = 0; $n <= 20; $n++) { // nickles
for($d = 0; $d <=10; $d++) { // dimes
for($q = 0; $q <=4; $q++) { // quarters
for($h = 0; $h <=2; $h++) { // half dollars
for($dd = 0; $dd <= 1; $dd++) { // dollars
if( ($p + 5*$n + 10*$d + 25*$q + 50*$h + 100*$dd) == 100) {
echo "$p pen, $n nic, $d dim, $q quar, $h halfs, $dd dols<br>";
}
}
}
}
}
}
}


----------



## meanwhile (Dec 13, 2007)

Thank you - this was helpful and he also had a friend teach him the calculus quickly and so he is back on track. Thanks!


----------

