Нахождение, является ли число кратным другому - PullRequest
Новая
       47

Нахождение, является ли число кратным другому

2 голосов
/ 20 апреля 2019

Глядя на код ниже: 

multiple(X,0).
multiple(X,Y) :- lt(0,X), lt(0,Y), diff(Y,X,D), multiple(X,D).

Случается, что-то не так. Для справки:
lt / 2 - меньше ли первый аргумент, чем второй.
diff / 3 - равен ли третий аргумент первому аргументу минус второй.
lt / 2 и diff / 3 определены правильно.

Есть ли логическая ошибка в определении? Предполагается, что 0 - это кратное каждому числу проблематично, или это логическая ошибка где-то еще? Я получаю правильные ответы, но я думаю, что запрос идет в бесконечный цикл.

EDIT:
Вот другие определения. 

natNum(0).
natNum(s(X)) :- natNum(X).

lt(0,s(X)) :- natNum(X).
lt(s(X),s(Y)) :- lt(X,Y).

sum(0,X,X).
sum(s(X),Y,s(Z)) :- sum(X,Y,Z).

diff(X,Y,Z) :- sum(Z,Y,X).

?- multiple(X, s(s(s(s(s(s(0))))))).

, где s(0) равно 1, s(s(0)) равно 2 и т. Д. Он дает все желаемые ответы для X, но после последнего ответа застревает. Я предполагаю в бесконечном рекурсивном цикле?

1 Ответ

3 голосов
/ 20 апреля 2019

Что происходит в вашей программе? Зацикливается ли он вечно, или это займет некоторое время, так как вы не обновляли свое оборудование в последние десятилетия? Мы не можем сказать. (На самом деле, мы можем сказать, посмотрев на вашу программу, но на данный момент это слишком сложно).

То, что мы можем сделать с легкостью, - это источник этих дорогостоящих усилий. И это без глубокого понимания вашей программы. Начнем с запроса: 

| ?- multiple(X, s(s(s(s(s(s(0))))))).
X = s(0) ? ;
X = s(s(0)) ? ;
X = s(s(s(0))) ? ;
X = s(s(s(s(s(s(0)))))) ? ;
** LOOPS or takes too long ***

Нет ли более простого способа сделать это? Вся эта точка с запятой. Вместо этого просто добавьте false к вашему запросу. Таким образом, найденные решения больше не показываются, и мы можем сосредоточиться на этом раздражающем цикле. И, если мы на это, вы также можете добавить false целей в вашу программу! Благодаря таким целям количество выводов может быть уменьшено (или останется неизменным). И если результирующий фрагмент (называемый ) находится в цикле, то это причина , почему ваша оригинальная программа зацикливается: 

<s>multiple(_X,0) :- <b>false</b></s>.
multiple(X,Y) :- lt(0,X), <b>false</b>, <s>lt(0,Y), diff(Y,X,D), multiple(X,D)</s>.

<s>natNum(0) :- <b>false</b></s>.
natNum(s(X)) :- natNum(X), <b>false</b>.

lt(0,s(X)) :- natNum(X), <b>false</b>.
<s>lt(s(X),s(Y)) :- <b>false</b>, lt(X,Y)</s>.

?- multiple(X, s(s(s(s(s(s(0))))))), <b>false</b>.
** LOOPS ***

Распознаете ли вы вашу программу? Остались только те части, которые нужны для петли. И на самом деле в этом случае мы имеем бесконечный цикл.

Чтобы это исправить, нам нужно что-то изменить в оставшейся видимой части. Я бы пошел на lt/2, первое предложение которого можно обобщить до lt(0, s(_)).

Но подождите! Почему нормально обобщать требование, что у нас есть натуральное число? Посмотрите на факт multiple(X,0)., который вы написали. Вы не требовали, чтобы X также являлось натуральным числом. Этот вид чрезмерных обобщений часто встречается в программах Prolog. Они улучшают свойства завершения по относительно низкой цене: иногда они являются слишком общими, но все термины, которые дополнительно вписываются в обобщение, не являются натуральными числами. Это такие термины, как any или [a,b,c], поэтому, если они где-то появляются, вы знаете, что они не относятся к решениям.

Таким образом, идея состояла в том, чтобы поместить в вашу программу цели false так, чтобы результирующая программа (fail-slice) все еще работала в цикле. В худшем случае вы помещаете false в неправильном месте, и программа завершается. Методом проб и ошибок вы получаете минимальный срез ошибки. Все те вещи, которые теперь прошли через , не имеют значения ! В частности diff/3. Так что не нужно это понимать (на данный момент). Достаточно взглянуть на оставшуюся программу.

...