backtracking.a68
1 COMMENT
2
3 @section Synopsis
4
5 Split an amount of money in coins, by backtracking.
6
7 How many ways are there to split 5 euros in coins of
8 2 euro, 1 euro, 50 ct, 20 ct, 10 ct, 5 ct?
9
10 COMMENT
11
12 BEGIN [] INT values = (5, 10, 20, 50, 100, 200);
13
14 PROC count = (INT rest, max) INT:
15 IF rest = 0
16 THEN 1 # Just right, combination found #
17 ELIF rest < 0
18 THEN 0 # Invalid, subtracted too much #
19 ELSE INT combinations := 0;
20 FOR i TO UPB values
21 WHILE values[i] <= max
22 DO combinations +:= count (rest - values[i], values[i])
23 OD;
24 combinations
25 FI;
26
27 INT amount = 500 # ct #;
28 print (("Number of ways to split ", whole (amount, 0), " into coins: ",
29 whole (count (amount, amount), 0), new line))
30 END
