(define (count-change amount) 
  (cc amount 5)) 
(define (cc amount kinds-of-coins) 
  (cond ((= amount 0) 1) 
        ((or (<; amount 0) (= kinds-of-coins 0)) 0) 
        (else (+ (cc amount (- kinds-of-coins 1)) 
                 (cc (- amount (first-denomination kinds-of-coins)) 
                     kinds-of-coins))))) 
(define (first-denomination kinds-of-coins) 
  (cond ((= kinds-of-coins 1) 1) 
        ((= kinds-of-coins 2) 5) 
        ((= kinds-of-coins 3) 10) 
        ((= kinds-of-coins 4) 25) 
        ((= kinds-of-coins 5) 50)))

How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

let coins = [|1;5;10;25;50|];;

let rec ways n sum cursum nways con = 
  if n=0 then con 1 else   
  if cursum > sum then con nways else
  ways (n-1) (sum - cursum) 0 0 (fun w->ways n sum (cursum + coins.(n)) (w + nways) con);;

ways 4 100 0 0 print_int;;

coins = [1,5,10,25,50]

ways 0 = 1
ways amount = sum [ ways (amount-coin) | coin <- coins, coin <= amount ]

ways amount = all_ways !! amount

all_ways = 1 : [ ways' amount | amount <- [1..] ] where
  ways' amount = sum [ ways (amount-coin) | coin <- coins, coin <= amount ]

ways amount = ways_since 0 [1] where
  ways_since a ws | a==amount = last ws
                  | otherwise = ways_since (a+1) ws++[w] where
                                  w = sum [ws !! (a-coin) | coin<-coins, coin<=amount]

coins = [50,25,10,5,1] -- сортируем в обратном порядке

ways a = ways' a coins where
  ways' 0 _ = 1
  ways' _ [] = 0
  ways' a (c:cs) | c>a = ways' a cs
                 | otherwise = (ways' a cs) + (ways' (a-c) (c:cs))

ways a = ways' a coins_sorted_up where
  ways' 0 _  = 1
  ways' _ [] = 0
  ways' a (c:cs) | a<c = 0 -- дальше ковырять список смысла нет
                 | otherwise = (ways' (a-c) (c:cs)) + (ways' a cs)

ways a = ways' 0 [(a,coins_sorted_up)] where
  ways' n [] = n
  ways' n (0,_):jobs = ways' (n+1) jobs
  ways' n (_,[]):jobs = ways' n jobs
  ways' (a,(c:cs)):jobs =
    if a<c then ways' n jobs
           else ways' n ((a-c,c:cs):(a,cs):jobs)

(define (count-change amount) 
  (cc amount 5 0 0 (lambda (x) (display x))))

(define (cc amount kinds-of-coins cursum nways con) 
  (cond ((= kinds-of-coins 1) (con 1)) 
        ((<; amount cursum) (con nways))
        (else (cc (- amount cursum) (- kinds-of-coins 1) 0 0
                  (lambda (w) (cc amount kinds-of-coins 
                          (+ cursum (first-denomination kinds-of-coins))
                          (+ w nways) con))))))
                       
(define (first-denomination kinds-of-coins) 
  (cond ((= kinds-of-coins 1) 1) 
        ((= kinds-of-coins 2) 5) 
        ((= kinds-of-coins 3) 10) 
        ((= kinds-of-coins 4) 25) 
        ((= kinds-of-coins 5) 50)))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))
(define (cc amount kinds-of-coins)
  (cond ((or (= kinds-of-coins 1) (= amount 0)) 1)        
        ((<; amount 0) 0)
        (else (+ (cc amount (- kinds-of-coins 1))
                 (cc (- amount (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (count-change amount)
  (cc amount 5))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))
(define (cc amount kinds-of-coins con)
  (cond ((or (= kinds-of-coins 1) (= amount 0)) (con 1))        
        ((<; amount 0) (con 0))
        (else 
         (cc amount (- kinds-of-coins 1) 
             (lambda (c1)
                 (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins
                     (lambda (c2) (con (+ c1 c2))))))         
         )))
(define (count-change amount)
  (cc amount 5 (lambda (x) x)))

let coins = [|1;5;10;25;50|];;

let rec cc amount kinds con =
  if kinds = 0 || amount = 0 then con 1 else
  if amount < 0 then con 0 else
  cc amount (kinds-1) (fun c1 -> cc (amount - coins.(kinds)) kinds (fun c2 -> con (c1+c2)));; 

cc 2000 4 print_int;;

-- start a cs = (ns,e) где ns с максимальными значениями в голове, e - признак точного совпадения (1 если совпало, 0 если нет)

start a [] = ([], if a==0 then 1 else 0)
start a (c:cs) = (n:ns,e) where
    n = a`div`c
    (ns,e) = start (a`mod`c) cs

-- next a cs ns = Just (ns',e) где ns' - лексикографически меньший вектор, e - признак точного совпадения

next a [] [] = Nothing -- действительно, есть единственный пустой вектор, дальше уж некуда
next a (c:cs) (0:ns) = -- текущий разряд уже меньше некуда
    case next a cs ns of -- пробуем скрутить дальше
        Just (ns',e) -> Just (0:ns',e)
    |    Nothing -> Nothing -- остальные тоже, видать, скручены
next a (c:cs) (n:ns) =
    let (ns',e) = start (a-c*(n-1)) cs -- скрутив текущий разряд, порождаем максимальный хвост
    in Just ((n-1):ns',e)

-- ну что, побежали!
ways a cs = ways' 0 (start a cs) where
    ways' w (ns,e) =
        let w' = w+e in
        case next a cs ns of
            Just nse' -> ways w' nse
        |    Nothing -> w'

coins = [1,5,10,25,50]

ways a con = ways' a coins con where
  ways' 0 _  con = con 1
  ways' _ [] con = con 0
  ways' a (c:cs) con | a<c = con 0 
                     | otherwise = ways' (a-c) (c:cs) (\c1 -> ways' a cs (\c2 -> con (c1+c2)))

main = ways 100 print

coins = [1,5,10,25,50]

DM>ways a con = ways' a coins con where
DM>  ways' 0 _  con = con 1
DM>  ways' _ [] con = con 0
DM>  ways' a (c:cs) con | a<c = con 0 
DM>                     | otherwise = ways' (a-c) (c:cs) (\c1 -> ways' a cs (\c2 -> con (c1+c2)))

DM>main = ways 100 print
DM>

DM>Для 100 выводит верный ответ. На 1000 задумался, съел больше гига памяти (сколько было свободно), результата я не дождался.

ways' 1000 coins print =
ways' 999 coins (\x1->...print) =
ways' 998 coins (\x2->...(\x1->...print)) =
.....
ways' 0 coins (\x1000->.....(\x2->...(\x1->...print))...) =

let coins = [|1;5;10;25;50|]

let rec cc amount kinds con =
  if kinds = 0 || amount = 0 then con 1 else
  if amount < 0 then con 0 else
  cc amount (kinds-1) (fun c1 -> cc (amount - coins.[kinds]) kinds (fun c2 -> con (c1+c2)))
  
cc 2000 4 (printfn "%d")

v=.0:`1:`(1:`(($:}.)+((-{.)$:]))@.(1:<#@]))@.(1:+*@[)
2000 v 50 25 10 5 1

ways _ 0 = 1
ways [] _ = 0
ways (c:cs) s = sum [ways cs (s-m) | m <- [0, c .. s]]

main = do putStrLn $ show $ ways [1,5,10,25,50] 2000

ways _ 0 = 1
ways [] _ = 0
ways cs s | noSolve cs s = 0  -- нет смысла копать глубже, решений нет
ways (c:cs) s = sum [ways cs (s-m) | m <- [0, c .. s]]

noSolve cs s = rem s (foldl1 gcd cs) /= 0  -- true, если не существует решений диофантова уравнения с коэффициентами cs и свободным членом s

main = do putStrLn $ show $ ways [1,5,10,25,50] 2000

let foldl1 f lst = match lst with 
  | [] -> failwith "empty list in foldl1"
  | x::xs -> List.fold_left f x xs;;

let rec gcd a b = if b = 0 then a else gcd b (a mod b);;

let nosolve cs s = s mod (foldl1 gcd cs) <> 0;;

let rec ways s coins = 
  if s = 0 then 1 else
  match coins with
  | [] -> 0
  | cs when nosolve cs s -> 0
  | c::cs -> Enum.fold (+) 0 (Enum.init (s/c + 1) (fun i-> ways (s-i*c) cs));; 

print_int (ways 2000 [1;5;10;25;50]);;

(defun cc-5 (amount coins)
  (labels ((make-tagged-amount (kinds amount)
         (cons kinds amount))
       
       (get-kinds (tagged-amount)
         (car tagged-amount))
       
       (get-amount (tagged-amount)
         (cdr tagged-amount))

       (merge-tagged-amount-lists (a b result)
         (if (and a b)
         (let ((amount-a (get-amount (car a)))
               (amount-b (get-amount (car b))))
           (cond ((< amount-a amount-b) (merge-tagged-amount-lists (cdr a) b (cons (car a) result)))
             ((> amount-a amount-b) (merge-tagged-amount-lists a (cdr b) (cons (car b) result)))
             ((= amount-a amount-b)
              (merge-tagged-amount-lists (cdr a)
                             (cdr b)
                             (cons (make-tagged-amount (+ (get-kinds (car a))
                                          (get-kinds (car b)))
                                           amount-a)
                               result)))))
         (if (or a b)
             (append (nreverse result) (or a b))
             (nreverse result))))
         
       (get-tagged-amount-list (kinds amount coin result)
         (cond ((> amount 0) (get-tagged-amount-list kinds
                             (- amount coin)
                             coin
                             (cons (make-tagged-amount kinds amount)
                                   result)))
           ((= amount 0) (cons (make-tagged-amount kinds amount)
                       result))
           (t result)))

       (sum (tagged-amount-list coin cur-sum result)        
         (if tagged-amount-list
         (let ((tagged-amount (car tagged-amount-list)))
           (cond ((= (get-amount tagged-amount) cur-sum) (sum tagged-amount-list
                                      coin
                                      (+ cur-sum coin)
                                      (+ result (get-kinds tagged-amount))))
             ((< (get-amount tagged-amount) cur-sum) (sum (cdr tagged-amount-list)
                                      coin
                                      cur-sum
                                      result))
             ((> (get-amount tagged-amount) cur-sum) (sum tagged-amount-list
                                      coin
                                      (+ cur-sum coin)
                                      result))))
         result))
            
       (process-coin (tagged-amount-list coins)
         (if (cdr coins)
         (process-coin (reduce #'(lambda (a b)
                       (merge-tagged-amount-lists a
                                      (get-tagged-amount-list (get-kinds b)
                                                  (get-amount b)
                                                  (car coins)
                                                  nil)
                                      nil))
                       (cdr tagged-amount-list)
                       :initial-value (get-tagged-amount-list (get-kinds (car tagged-amount-list))
                                          (get-amount (car tagged-amount-list))
                                          (car coins)
                                          nil))
                   (cdr coins))
         (sum tagged-amount-list (car coins) 0 0))))
    (if coins
    (process-coin (list (make-tagged-amount 1 amount)) coins)
    0)))

;; CL-USER> (time (cc-5 50000 '(50 25 10 5 1)))
;; Evaluation took:
;;   14.433 seconds of real time
;;   14.068879 seconds of user run time
;;   0.396025 seconds of system run time
;;   [Run times include 2.192 seconds GC run time.]
;;   0 calls to %EVAL
;;   0 page faults and
;;   2,790,509,272 bytes consed.
;; 4182519842501

#include <iostream>

// немножко чистоты типов - просто чтоб различать, кто есть ху
typedef int money_t; // суммы денег
typedef int count_t; // количество монет

// номиналы монет
money_t const coins[] =
#if 0
    { 1, 5, 10, 25, 50 };
#else
    { 50, 25, 10, 5, 1 }; // удобнее, когда крупными монетами вперёд - меньше промахов (а с учётом 1-копейки, их вообще нет)
#endif 
size_t const num_coins = _countof(coins);

// сумма, которую будем разменивать
money_t const target = 1000;

// переменная цикла состоит из
count_t amount[num_coins]; // кошелька (сколько монет каждого номинала?)
bool exact; // и признака, что в кошельке точная сумма

// процедура заполнения кошелька, начиная с монет номинала номер k
void complete(money_t sum, size_t const k)
{
    for(size_t i = k; i != num_coins; ++i)
    {
        money_t const coin = coins[i];
        amount[i] = sum / coin; // процедура детерминированная: заполняем данным номиналом по максимуму
        sum %= coin;
    }
    exact = sum==0;
}

// функция нахождения хвоста из нулей
size_t find_tail_zeros()
{
    // возвращает k : для всех i таких, что k<=i<n-1, a[i]==0
    
    size_t k = num_coins-1; // маленькая хитрость: не учитываем последний номинал (см.ниже)
    while(k > 0 && amount[k-1] == 0)
        --k;
    return k;
}

money_t sum_head(size_t const k)
{
    money_t sum = 0;
    for(size_t i = 0; i != k; ++i)
        sum += amount[i] * coins[i];
    return sum;
}

//////////////////
// первая итерация

void init()
{
    complete(target, 0); // просто заполняем кошелёк, получая лексикографический максимум
}

/////////////////////
// следующая итерация

bool next() // возвращает признак того, что итерация удалась
{
    // наша задача - получить лексикографического соседа (следующий по убыванию)

    size_t const k = find_tail();
    if(k==0)
        return false; // весь кошелёк состоит из нулей, скручивать нечего
    
    // скручиваем a[k] - даём хвосту шанс измениться
    --amount[k-1];
    
    // считаем, сколько у нас денег осталось на заполнение хвоста - и заполняем его
    complete(target - sum_head(k), k);
    
    return true;
}

int main()
{
    // ведём статистику: сколько всего итераций, и сколько из них успешных
    int attempts = 0, success = 0;
    for(bool go = (init(),true); go; go = next())
    {
        ++attempts;
        if(exact)
            ++success;

        // чтобы юзер не скучал...
#if 0
        std::cout << "попытка " << attempts << ": ";
        for(size_t i = 0; i != num_coins; ++i)
            std::cout << coins[i] << "*" << amount[i] << " ";
        if(exact)
            std::cout << "попал! " << success;
        std::cout << std::endl;
#else
        if(attempts % 100 == 0)
            std::cout << attempts << " попыток, " << success << " попаданий ...\r";
#endif
    }
    std::cout << std::endl;
    std::cout << attempts << " попыток, " << success << " попаданий" << std::endl;
}

#include <iostream>

const int coins[] = {50, 25, 10, 5, 1};

const size_t num_coins = sizeof(coins)/sizeof(int);

int amounts[num_coins];

int target = 100;

int main()
{
    int i = 0;
    int success = 0;
    amounts[0] = target;
    
    while (amounts[0] > 0)
    {

    if (amounts[i] > 0)
    {
        if (i < num_coins - 1)
        {
        amounts[i+1] = amounts[i];
        i++;
        }
        else
        amounts[i] -= coins[i];
    }
    else
    {
        if (amounts[i] == 0) ++success;
        if (i > 0)
        {
        i--;
        amounts[i] -= coins[i];
        }
    }
    }

    if (amounts[0] == 0)
    success++;

    std::cout << success << std::endl;
}

(defun cc-6 (amount coins)
  (let ((last_coin_index (1- (length coins)))
    (amounts (make-list (length coins) :initial-element 0)))

    (setf (elt amounts 0) amount)
    
    (labels ((iter (i result)
           (if (> (elt amounts i) 0)
           (progn
             (if (< i last_coin_index)
             (progn
               (setf (elt amounts (1+ i)) (elt amounts i)) ; i.e. amounts[i+1]=amounts[i]
               (iter (1+ i) result))
             (progn
               (decf (elt amounts i) (elt coins i))    ; i.e. amounts[i]-=coins[i]
               (iter i result))))
           (let ((dt (if (= (elt amounts i) 0) 1 0)))
             (if (> i 0)
             (progn
               (decf (elt amounts (1- i)) (elt coins (1- i))) ; i.e. amounts[i-1]-=coins[i-1]
               (iter (1- i) (+ result dt)))
             (+ result dt))))))
      (iter 0 0))))

;; CL-USER> (cc-6 1000 '(50 25 10 5 1))
;; 801451

hub>;(define (cc amount kinds-of-coins) 
hub>;  (cond ((= amount 0) 1) 
hub>;        ((or (< amount 0) (= kinds-of-coins 0)) 0) 
hub>;        (else (+ (cc amount (- kinds-of-coins 1)) 
hub>;                 (cc (- amount (first-denomination kinds-of-coins)) 
hub>;                     kinds-of-coins))))) 
hub>;

(define (cc amount kinds-of-coins count) 
   (cond ((= kinds-of-coins 1) 1)
         ((< amount 0) count)
         (else (cc (- amount (first-denomination kinds-of-coins))
                    kinds-of-coins 
                    (+ count (cc amount (- kinds-of-coins 1) 0))))))  

(define (count-change amount) 
   (cc amount 5 0))

> (count-change 1000)
801451