Algorithm X.1: Making change in Canada

Describe the algorithm for making change when a person is paying for an item that costs $m and n¢ in Canada. Assume the customer has given $M and N¢ where this amount is assumed to be more than sufficient to pay for the item. Your goal is to give the minimum number of bills and coins required to give the correct change. You may assume that the note amounts are $100, $50, $20, $10 and $5; and that the coins are $2, $1, 25¢, 10¢ and 5¢.

Algorithm X.2: Making change in the United States

Modify your algorithm for making change when a person is paying for an item in American dollars. You may assume that the note amounts are $100, $50, $20, $10, $5 and $1; and that the coins are 25¢, 10¢, 5¢ and 1¢.

Algorithm X.3: Making change in the euro area¹

Modify your algorithm for making change when a person is paying for an item in the European Union. You may assume that the note amounts are €500, €200, €100, €50, €20, €10 and €5; and that the coins are €2, €1, 50¢, 20¢, 10¢, 5¢, 2¢ and 1¢.

Of course, in the latter two cases, if your algorithm is well designed, it should be essentially trivial to modify the algorithm. Instead, however, suppose we are at Hogwarts where you can pay in Dumbledores that allow you to pay in D100, D81, D64, D49, D36, D25, D16, D9, D4 and D1. Does your algorithm give the optimal change for, say, D72?

¹ Also known colloquially as the eurozone.