Представление суммы денег с конкретными счетами - PullRequest
Новая
       68

Представление суммы денег с конкретными счетами

0 голосов
/ 29 апреля 2018

Я хочу написать в Racket функцию, которая берет сумму денег и список конкретных значений счетов, а затем возвращает список с количеством счетов, использованных для каждого типа, чтобы получить данную сумму в общей сложности. Например, (calc 415 (list 100 10 5 2 1)) должно вернуть '(4 1 1 0 0).

Я попробовал это таким образом, но это не работает: / Я думаю, я не до конца понял, что вы можете / не можете сделать с set! в Racket, если честно. 

(define (calc n xs)
  (cond ((null? xs) (list))
        ((not (pair? xs)) 
          (define y n) 
          (begin (set! n (- n (* xs (floor (/ n xs)))))
                 (list (floor (/ y xs))) ))
        (else (append (calc n (car xs))
                      (calc n (cdr xs))))))

Ответы [ 4 ]

0 голосов
/ 30 апреля 2018

Я думаю, что это первая программа, которую я написал, изучая Фортран! Вот версия, которая не скрывает использования всего, что может предложить Racket (или, по крайней мере, всего, что я знаю). Таким образом, это, вероятно, ужасное домашнее решение, и оно, конечно, красивее, чем Фортран, который я написал в 1984 году.

Обратите внимание, что эта версия не выполняет поиск, поэтому она будет получать остатки, даже когда в этом нет необходимости. Конечно, он никогда не получит остаток, если наименьший номинал равен 1. 

(define/contract (denominations-of amount denominations)
  ;; split amount into units of denominations, returning the split
  ;; in descending order of denomination, and any remainder (if there is
  ;; no 1 denomination there will generally be a remainder).
  (-> natural-number/c (listof (integer-in 1 #f))
      (values (listof natural-number/c) natural-number/c))
  (let handle-one-denomination ([current amount]
                                [remaining-denominations (sort denominations >)]
                                [so-far '()])
    ;; handle a single denomination: current is the balance,
    ;; remaining-denominations is the denominations left (descending order)
    ;; so-far is the list of amounts of each denomination we've accumulated
    ;; so far, which is in ascending order of denomination
    (if (null? remaining-denominations)
        ;; we are done: return the reversed accumulator and anything left over
        (values (reverse so-far) current)
        (match-let ([(cons first-denomination rest-of-the-denominations)
                     remaining-denominations])
          (if (> first-denomination current)
              ;; if the first denomination is more than the balance, just
              ;; accumulate a 0 for it and loop on the rest
              (handle-one-denomination current rest-of-the-denominations
                                       (cons 0 so-far))
              ;; otherwise work out how much of it we need and how much is left
              (let-values ([(q r)
                            (quotient/remainder current first-denomination)])
                ;; and loop on the remainder accumulating the number of bills
                ;; we needed
                (handle-one-denomination r rest-of-the-denominations
                                         (cons q so-far))))))))
0 голосов
/ 29 апреля 2018

Я решил это теперь так:) 

(define (calc n xs)
  (define (calcAssist n xs usedBills)
    (cond ((null? xs) usedBills)
          ((pair? xs) 
            (calcAssist (- n (* (car xs) (floor (/ n (car xs))))) 
                        (cdr xs) 
                        (append usedBills 
                                (list (floor (/ n (car xs)))))))
          (else 
            (if ((= (- n (* xs (floor (/ n xs)))) 0)) 
               (append usedBills (list (floor (/ n xs))))
               (display "No solution")))))

  (calcAssist n xs (list)))

Тестирование: 

> (calc 415 (list 100 10 5 2 1))
'(4 1 1 0 0)
0 голосов
/ 29 апреля 2018

Ваша процедура делает слишком много, и вы используете мутацию, которая является ненужной. Если вы разделили проблему. 

(define (calc-one-bill n bill)
  ...)

;; test 
(calc-one-bill 450 100) ; ==> 4
(calc-one-bill 450 50)  ; ==> 9

Тогда вы можете сделать: 

(define (calc-new-n n bill amount)
  ...)

(calc-new-n 450 100 4) ; ==> 50
(calc-new-n 450 50 9)  ; ==> 0

Тогда вы можете уменьшить исходную реализацию следующим образом: 

(define (calc n bills)
  (if (null? bills)
      (if (zero? n)
          '()
          (error "The unit needs to be the last element in the bills list"))
      (let* ((bill (car bills))
             (amount (calc-one-bill n bill)))
        (cons amount
              (calc (calc-new-n n bill amount)
                    (cdr bills))))))

Это всегда выберет решение с наименьшим количеством счетов, как это делает ваша версия. Обе версии требуют, чтобы последний элемент в переданном bill был единицей 1. Для более сложного метода, который работает с (calc 406 (list 100 10 5 2)) и который потенциально может найти все комбинации решений, см. Will will answer .

0 голосов
/ 29 апреля 2018

Эта проблема требует некоторого простого рекурсивного недетерминированного программирования.

  • Мы начинаем с определенной суммы и данного списка счетов номиналов , с неограниченными суммами каждого счета, по-видимому (в противном случае это была бы другая проблема).
  • В каждый момент времени мы можем использовать самый большой счет или нет.
  • Если мы его используем, общая сумма уменьшается на на сумму счета.
  • Если итоговое значение равно 0, у нас есть решение!
  • Если сумма отрицательна, она недействительна, поэтому мы должны отказаться от этого пути.

Код здесь будет следовать за другим моим ответом , который определяет общее количество решений (которые * больше, чем один, для вашего примера также). Нам просто нужно будет поддерживать и сами решения, тогда как код, упомянутый выше, учитывает их только.

Мы можем закодировать эту процедуру как рекурсивную процедуру обратного отслеживания с обратным вызовом, который вызывается для каждого успешно найденного решения: 

(define (change sum bills callback)
  (let loop ((sum sum) (sol '()) (bills bills))     ; "sol" for "solution"
    (cond
       ((zero? sum) (callback sol))
       ((< sum 0) #f)
       ((null? bills) #f)
       (else (apply
              (lambda (b . bs)
                (loop (- sum b) (cons b sol) bills) ; either use the first denomination,
                (loop sum sol bs))                  ;  or backtrack, and don't!
              bills)))))

Это должно быть вызвано одним из 

(define (first-solution proc . params)
  (call/cc (lambda (return)
             (apply proc (append params
                                 (list (lambda (sol) 
                                         (return sol))))))))

(define (n-solutions n proc . params)     ; n assumed an integer
  (let ([res '()])                        ; n <= 0 gets ALL solutions
    (call/cc (lambda (break)
               (apply proc (append params
                                   (list (lambda (sol)
                                           (set! res (cons sol res))
                                           (set! n (- n 1))
                                           (cond ((zero? n) (break)))))))))
    (reverse res)))

Тестирование 

> (first-solution change 406 (list 100 10 5 2))

'(2 2 2 100 100 100 100)

> (n-solutions 7 change 415 (list 100 10 5 2 1))

'((5 10 100 100 100 100)
  (1 2 2 10 100 100 100 100)
  (1 1 1 2 10 100 100 100 100)
  (1 1 1 1 1 10 100 100 100 100)
  (5 5 5 100 100 100 100)
  (1 2 2 5 5 100 100 100 100)
  (1 1 1 2 5 5 100 100 100 100))

Относительно того, как этот код структурирован, ср. Как генерировать все перестановки элементов в списке по одному в Лиспе? Создает вложенные циклы с решением, доступным в теле самого внутреннего цикла.

Относительно того, как кодировать недетерминированный алгоритм (делая все возможные варианты сразу) правильным функциональным способом, см. Как сделать powerset в DrRacket? и Как найти разделы списка в схеме .

...