Предикат Пролог - бесконечный цикл
Мне нужно создать предикат Пролога для степени 2 с натуральными числами. Натуральные числа: 0, s(0), s(s(0)) и т. Д.
Например:
?- pow2(s(0),P).
P = s(s(0));
false.
?- pow2(P,s(s(0))).
P = s(0);
false.
Это мой код:
times2(X,Y) :-
add(X,X,Y).
pow2(0,s(0)).
pow2(s(N),Y) :-
pow2(N,Z),
times2(Z,Y).
И это прекрасно работает с первым примером, но во втором бесконечный цикл.
Как я могу это исправить?
2 ответа
Это происходит из-за порядка вычисления pow2. Если вы переключите порядок pow2, у вас будет первый пример, застрявший в бесконечном цикле. Таким образом, вы можете сначала проверить, является ли Y var
или же nonvar
,
Вот так:
times2(X,Y) :-
add(X,X,Y).
pow2(0,s(0)).
pow2(s(N),Y) :-
var(Y),
pow2(N,Z),
times2(Z,Y).
pow2(s(N),Y) :-
nonvar(Y),
times2(Z,Y),
pow2(N,Z).
Вот версия, которая заканчивается для первого или второго связываемого аргумента:
pow2 (E, X): - pow2 (Е, X, X). pow2 (0, s (0), s (_)). pow2 (s (N), Y, s (B)): - pow2 (N, Z, В), Добавить (Z, Z, Y).
Вы можете определить условия его прекращения с помощью cTI.
Итак, как я придумал это решение? Идея состояла в том, чтобы найти способ, каким образом второй аргумент может определять размер первого аргумента. Основная идея заключается в том, что для всех i ∈ N: 2 i > i.
Поэтому я добавил еще один аргумент, чтобы выразить это отношение. Может быть, вы можете усилить это немного дальше?
И вот причина, почему оригинальная программа не заканчивается. Я даю причину как неудача-кусочек. Смотрите тег для более подробной информации и других примеров.
? - pow2 (P, s (s (0))), ложно.pow2 (0, s (0)): - неверно. pow2(s(N),Y):- pow2(N,Z), ложь,времена 2 (Z, Y).
Именно этот крошечный фрагмент является источником для прекращения! смотреть на Z
которая является новой новой переменной! Чтобы решить проблему, этот фрагмент должен быть как-то изменен.
И вот причина, почему решение @Keeper не заканчивается для pow2(s(0),s(N))
,
? - pow2 (s (0), s (N)), false.добавить (0,Z,Z):- неверно. добавить (s(X),Y,s(Z)):- добавить (X,Y,Z), ложь. времена2(X,Y):- добавить (X,X,Y), ложь.pow2 (0, s (0)): - неверно.pow2 (s (N), Y): - неверно,вар (Y),pow2 (N, Z),времена 2 (Z, Y). pow2 (s (N), Y): - nonvar (Y) времена2 (Z, Y), ложь,pow2 (N, Z).