Генерация сдачи с учетом суммы наличных и списка валют

Я пытаюсь написать программу на Прологе, которая делает две вещи:

  1. Принимает два аргумента, целое число и список целых чисел.
  2. Удовлетворительно, если изменение для первого аргумента может быть сделано из некоторой комбинации элементов из второго

Я придумал решение этой проблемы, которое позволяет унифицировать правило изменения для создания фактов как таковых:

coin(quarter, 25).
coin(dime,10).
coin(nickel,5).
coin(penny,1).

change(0, []).
change(A, [(C, Num)|L]) :- 
    coin(C, V), 
    A >= V, 
    Num is floor(A / V), 
    B is A mod V, 
    change(B, L).

Кроме того, если вы передадите что-то вроде change(27,L) интерпретатору, он сгенерирует все возможные комбинации четвертаков, десятицентовиков, пятицентовиков и пенни, которые можно использовать для внесения сдачи, например:

?- change(27,L).
L = [(quarter, 1),  (penny, 2)] ;
L = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
L = [(dime, 2),  (penny, 7)] ;
L = [(nickel, 5),  (penny, 2)] ;
L = [(penny, 27)] ;
false.

Однако у меня возникли проблемы с тем, как это можно решить, просто передав список валют, например [25,10,5,1], в сдачу, сделав вызов похожим на изменение (27, [25,10,5, 1], л). Возможно ли это, и если да, то как это можно сделать?


prolog coin-change
person Josh    schedule 15.04.2019    source источник
comment
Не та же проблема. Я пытаюсь генерировать сдачу без ограничения количества доступных монет каждого типа и на любую сумму.   -  person Josh    schedule 15.04.2019
comment
Ты прав. Это должно быть что-то вроде change(27, [25,10,5,1] , L).   -  person Josh    schedule 15.04.2019
comment
Да, изменить(27,[25,10,5,1], L). является правильным. Это не домашнее задание.   -  person Josh    schedule 15.04.2019
comment
Я пытаюсь адаптировать программу, изначально написанную на стандартном ML, поэтому инструкции не точны.   -  person Josh    schedule 15.04.2019
comment
Да, это тоже правильно. Списку не нужно название монеты, только монеты, необходимые для внесения сдачи, например, change(27, [25,10,5,1] , L) может просто вернуть [25,1,1] или [10 ,10,5,1,1].   -  person Josh    schedule 15.04.2019
comment
Было бы принято использовать параметр (назовем его Coinage), например [quarter=25, dime=10, nickel=5, penny=1], в качестве аргумента, а затем просто изменить coin(C, V) на member(C=V, Coinage).   -  person Daniel Lyons    schedule 15.04.2019
comment
так что среди результатов у вас [ (10, 2), (5, 1), (1, 2) ], но [ (10, 1), (5, 3), (1, 2) ] тоже решение...   -  person Will Ness    schedule 17.05.2020

Ответы (1)


arrow_upward
3
arrow_downward

Так что вы на самом деле довольно близко. Это в основном комментарий, который я оставил, расширенный. Добавим еще один аргумент для типов чеканки.

change(0, _, []).
change(A, Coinage, [(C, Num)|L]) :- 
    member(C=V, Coinage), 
    A >= V, 
    Num is floor(A / V), 
    B is A mod V, 
    change(B, Coinage, L).

Я заменил coin(C, V) этим термином member(C=V, Coinage). member/2 — отличный способ сделать вашу программу на Прологе более динамичной, потому что вместо того, чтобы обращаться к хранилищу фактов, вы можете генерировать решения из списка. Взгляните на результат:

?- change(27, [quarter=25, dime=10, nickel=5, penny=1], Change).
Change = [(quarter, 1),  (penny, 2)] ;
Change = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
Change = [(dime, 2),  (penny, 7)] ;
Change = [(nickel, 5),  (penny, 2)] ;
Change = [(penny, 27)] ;
false.

Давайте посмотрим, стоит ли нам добавить 3-центовую монету, возможно, с изображением лица недавнего президента:

?- change(27, [quarter=25, dime=10, nickel=5, thripenny=3, penny=1], Change).
Change = [(quarter, 1),  (penny, 2)] ;
Change = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
Change = [(dime, 2),  (thripenny, 2),  (penny, 1)] ;
Change = [(dime, 2),  (penny, 7)] ;
Change = [(nickel, 5),  (penny, 2)] ;
Change = [(thripenny, 9)] ;
Change = [(penny, 27)] ;

Похоже, это была бы отличная идея!

person Daniel Lyons    schedule 15.04.2019
comment
Спасибо! Это делает то, что я хочу. Как я уже говорил, я пытаюсь подобрать Prolog из Standard ML. Поскольку в этом решении нет базы фактов, значит ли это, что Пролог ничего не объединяет? - person Josh; 16.04.2019
comment
@JoshB Нет, унификация происходит всякий раз, когда Пролог привязывает значение к переменной. В последовательности member(C=V, Coinage), A >= V Пролог сначала унифицирует C=четверть, V=25. Затем он попытается выполнить A ›= V. Если A меньше V, произойдет сбой, произойдет откат, а затем повторная попытка вызова члена с C=dime, V=10. (На самом деле это объединение C=V с quarter=25, но объединение является рекурсивным по структуре термина.) - person Daniel Lyons; 16.04.2019