How Does the Modulus Operator Work in Coin Change Algorithms?

[jonroberts74]

only had a brief intro to algorithms like this

Given an amount of money A between.01 and .99, this determines the breakdown of A into quarters (q) dimes (d) nickels (n) pennies (p)


q:=A div 25
A:=A mod 25
d:= A div 10
A:= A mod 10
n:= A div 5
p:= A mod 5

I have to trace the algorithm for A=27

 

[STEMucator]

only had a brief intro to algorithms like this

Given an amount of money A between.01 and .99, this determines the breakdown of A into quarters (q) dimes (d) nickels (n) pennies (p)


q:=A div 25
A:=A mod 25
d:= A div 10
A:= A mod 10
n:= A div 5
p:= A mod 5

I have to trace the algorithm for A=27

So simply plug $A = 27$ in. Take note that the mod operator only works with integers.

$q := A/25 = 2$
$A := 27 \space mod \space 25 = 2$

Can you continue?

 

[jonroberts74]

q:=A div 25 =1
A:=A mod 25 = 2
d:= A div 10 = 2
A:= A mod 10 =5
n:= A div 5 = 5
p:= A mod 5 = 2

??

 

[STEMucator]

q:=A div 25 =1
A:=A mod 25 = 2
d:= A div 10 = 2
A:= A mod 10 =5
n:= A div 5 = 5
p:= A mod 5 = 2

??

Yes sorry for the typo in my prior post. I meant $q := 1$.

I have bolded where you have made a slight error. It should read $A := 2 \mod 10 = 2$.

EDIT: Also, while it hasn't been mentioned yet, the line for $p$ should actually read something different. Is this for a programming class? If so the line for $d$ might also be wrong.

 

[STEMucator]

The proper algorithm should be this regardless though:

A = 27

q:= A div 25 = 1
A:= A mod 25 = 2
d:= A div 10 = 0
A:= A mod 10 = 2
n:= A div 5 = 0
p:= A mod 1 = 2

 

[jonroberts74]

Its for a discrete math class

why is it A:= 2 mod 10 = 2 ?

A becomes the value from the previous line??

 

[cpscdave]

Its for a discrete math class

why is it A:= 2 mod 10 = 2 ?

A becomes the value from the previous line??

The mod operator gives you the remainder from doing a division.
so for example (% being the mod operator)
1%5 = 1
2%5 = 2
3%5 = 3
4%5 = 4
5%5 = 0
6%5 = 1 etc