Изменение пролога на 100 центов

Я новичок в Прологе и хочу написать функцию, которая возвращает все различные способы внесения сдачи за доллар (100 центов). У нас есть 2-центовые монеты, 11-центовые монеты, 38-центовые монеты и, что интересно, -8-центовые монеты (монета стоимостью -8 центов). Кроме того, всего у нас есть только 10 монет номиналом «-8» центов. (нет верхней границы для других видов монет)

Вот моя попытка:

change100([P2, P11, P38, Pn8]):- 
    Pn8 =< 10,
    Pn8 >= 0,
    P2 >= 0, P11 >= 0, P38 >= 0,
    D is 2 * P2 + 11 * P11 + 38 * P38 - 8 * Pn8,
    D = 100.

Но это не работает. Когда я запускаю его и запрашиваю

?- change100(A).

я получил сообщение

ERROR:

=< /2: Arguments are not sufficiently instantiated.

Почему это? Как я могу это исправить?

Первоначальная постановка задачи:

Есть 4 вида монет: монета в 2 цента, монета в 11 центов, монета в 38 центов и, что интересно, монета в 8 центов (монета стоимостью -8 центов). Что еще более интересно, всего когда-либо было создано всего 10 -8-центовых произведений, поэтому вам не нужно беспокоиться о ситуациях с более чем 10 -8-центовыми произведениями.

Сколькими способами можно разменять доллар (100 центов)?

Например, один из способов получить сдачу на 100 центов — использовать 4 монеты по 2 цента, 8 монет по 11 центов, 2 монеты по 38 центов и 9 монет по 8 центов.

Возможно иметь 0 некоторых монет, например. 50 монет по 2 цента — это один из способов разменять доллар.

Напишите на Прологе функцию change100(Coins), которая начинается так:

  change100([P2, P11, P38, Pn8]) :-
       % ...

P2 — количество монет номиналом 2 цента, P11 — количество монет номиналом 11 центов и так далее. Имейте в виду, что, как указано в описании задачи, Pn8 не больше 10.


prolog clpfd coin-change
person MicM    schedule 19.03.2014    source источник
comment
Давным-давно я написал огромный пост в блоге о проблеме внесения изменений в Prolog. Вот оно… /" rel="nofollow noreferrer">xor0110.wordpress.com/2010/06/04/   -  person dividebyzero    schedule 26.04.2015

Ответы (1)


arrow_upward
1
arrow_downward

Для использования в числовых неравенствах переменные в Прологе должны быть конкретизированы.

Ваш код пытается арифметически сравнить неконкретизированные переменные, это не то, что может сделать Пролог.

Но вы можете использовать так называемое "программирование логики ограничений" - расширение Пролога, которое решает эту проблему.

Вот код в SWI-Prolog (почти такой же, как ваш исходный код):

:- use_module(library(clpfd)).
change100([P2, P11, P38, Pn8]):- 
    Pn8 #=< 10,
    Pn8 #>= 0,
    P2 #>= 0, P11 #>= 0, P38 #>= 0,
    D #= 2 * P2 + 11 * P11 + 38 * P38 - 8 * Pn8,
    D #= 100,
    label([P2, P11, P38, Pn8]).

Обновить

Можно убедиться, что с помощью этой программы вы получаете 195 различных решений.

Вы упомянули, что должно быть 108 различных решений. Это количество решений может быть получено при неверном предположении, что количество монет, умноженное на номинал монеты, должно быть меньше или равно 100 (т.е. не более 100/2=50 монет достоинством 2). Это предположение было бы правильным, если бы у нас были только положительные монеты, но для задачи это предположение приведет к пропуску, например, «90 * 2 + 0 * 11 + 0 * 38 - 10 * 8».

Чтобы эмулировать эту неправильную логику и получить 108 решений, вы можете добавить в программу 2 * P2 #=< 100, 11 * P11 #=<100, 38 * P38 #=< 100, строку. Но, пожалуйста, возразите, что на самом деле существует 195 решений.

person Sergii Dymchenko    schedule 19.03.2014
comment
Большое спасибо. Но если я протестирую код, я получу 195 возвратов, тогда как правильный ответ должен быть 108 разных возвратов. Я думаю, мне нужно добавить еще несколько ограничений в функцию. - person MicM; 19.03.2014
comment
@ user3221327 действительно существует 195 различных решений, и я думаю, что это правильно для проблемы, сформулированной в вопросе. Может быть, вы упустили какую-то важную деталь из условия задачи? - person Sergii Dymchenko; 19.03.2014
comment
Да, может быть. Мне нужно это проверить. Кстати, если вам интересно, я обновил исходную постановку задачи. - person MicM; 19.03.2014
comment
@user3221327 user3221327 Я вижу, что вопрос обновлен. Я бы сказал, что 195 разных ответов — это правильное число для задачи. Как вы думаете, почему должно быть только 108? Вы можете распечатать все ответы и вручную попытаться найти хотя бы один неверный. Если на самом деле 108 правильных ответов, почти половина из 195 будет неправильными, так что найти один из них не составит труда. Но я думаю, что все 195 правильны. - person Sergii Dymchenko; 19.03.2014
comment
Ха, я нашел, как можно получить 108 (что неверно). Смотрите мой обновленный ответ. - person Sergii Dymchenko; 19.03.2014