Algol 68 Genie

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

Deze website is gearchiveerd door de KB, nationale bibliotheek.

This website is archived by the National Library of the Netherlands.