So I have to make a greedy algorithm to find the fewest number of coins needed to make change for any n cents. I have an infinite number of quarters(25 cents), dimes (10 cents), nickles (5 cents), and pennies (1 cent). This is the algorithm I came up with, it works fine but I was wondering whether this is the best solution?
make_change(int change)
{
while(change > 25)
{
change = change - 25;
quarters++;
}
while(change > 10)
{
change = change - 10;
dimes++;
}
while(change > 5)
{
change = change - 5;
nickles++;
}
while(change >= 1)
{
change = change - 1;
pennies++;
}
return 1;
}
I am having some trouble with coming up with a function to find the number of operations performed to make change for any n>0 cents. I know that for each coin there is a check to see if we should make change in that denomination, and if so there is a subtraction and an addition. But I don't know how to turn that into some sort of function to calculate the number of operations performed. Any hints? Thanks a bunch for any help.