Предикат Пролог - бесконечный цикл

Мне нужно создать предикат Пролога для степени 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.

Итак, как я придумал это решение? Идея состояла в том, чтобы найти способ, каким образом второй аргумент может определять размер первого аргумента. Основная идея заключается в том, что для всех iN: 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).
Другие вопросы по тегам