// Программа разменивает сумму советскими копейками
// Используется "жадный" алгоритм - отнимается по максимуму наибольший,
// что для произвольного набора монет может приводить к неразмененному остатку
// Copyleft Alexey Kuzminov (с) 2016

// количество копеек + падеж от копейки
// ВНИМАНИЕ: требуется сортировка по убыванию и наличие 1 копейки в списке
let coins = [
  (50, "копеек")
  (20, "копеек")
  (10, "копеек")
  (5, "копеек")
  (3, "копейки")
  (2, "копейки")
  //(1, "копейке") // !!! закомментирована для демонстрации эффекта неразмена
]

// рекурсивный пробег по списку, откусывая по одному элементу с начала
// возвращает количество монет, которыми разменивается сумма монетами списка
let rec exchange_tail (sum: int byref) list =
  match list with 
  | head :: tail ->
    let (value, text) = head // просто парсим кортеж
    let count = sum / value
    sum <- sum - count * value
    if count > 0 then printfn "  %d по %d %s" count value text
    count + exchange_tail &sum tail
  | [] -> 0

// функция размена
let exchange sum =
  let mutable total = sum
  printfn "\nРазмен суммы %d:" total
  printfn "Итого монет %d" (exchange_tail &total coins)
  if (total > 0) then printfn "Осталось неразменена сумма %d" total

// для проверки
exchange 14
exchange 98