Пролог: пифагорейская тройка

У меня есть этот код, который использует переменную верхней границы N, которая должна заканчиваться для X и Y пифагорейской тройки. Однако он зависает только тогда, когда достигает верхней границы. Не был уверен, как использовать разрез, чтобы остановить откат. Код:

is_int(0).
is_int(X) :- is_int(Y), X is Y+1.
minus(S,S,0).
minus(S,D1,D2) :- S>0, S1 is S-1, minus(S1,D1,D3), D2 is D3+1.

pythag(X,Y,Z,N) :- int_triple(X,Y,Z,N), Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :- is_int(S), minus(S,X,S1), X>0, X<N,
                                  minus(S1,Y,Z), Y>0, Y<N.

Будет вызываться, например, с помощью

?- pythag(X,Y,Z,20).

prolog pythagorean failure-slice
person RandellK02    schedule 09.05.2012    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Во-первых, давайте протестируем ваше решение:

?- pythag(X,Y,Z,20).
X = 4,
Y = 3,
Z = 5 ;
X = 3,
Y = 4,
Z = 5 ;
X = 8,
Y = 6,
Z = 10 ;
X = 6,
Y = 8,
Z = 10 ;
X = 12,
Y = 5,
Z = 13 ;
X = 5,
Y = 12,
Z = 13 ;
X = 12,
Y = 9,
Z = 15 ;
X = 9,
Y = 12,
Z = 15 ;
X = 15,
Y = 8,
Z = 17 ;
X = 8,
Y = 15,
Z = 17 ;
X = 16,
Y = 12,
Z = 20 ;
X = 12,
Y = 16,
Z = 20 ...

Мне кажется идеально! Все ответы являются правильными решениями! ... вплоть до этого последнего решения. После этого ваша программа зацикливается.

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

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

?- pythag(X,Y,Z,20), false.
** LOOP **

Теперь все ответы удалены из-за цели false. Остается только конечный результат: либо прекращение, либо не прекращение, либо какая-то ошибка. Ничего больше. Это должно немного облегчить наши наблюдения по поводу завершения — больше никаких ослепляющих ответов, прокручивающихся на экране. Обратите внимание, что это не решает проблему в целом. В конце концов, сколько долго мы готовы ждать? 1с? 1м?

Истинную причину отказа можно лучше всего понять, взглянув на соответствующий срез сбоя. Это фрагмент программы, незавершение которого подразумевает незавершение всей программы. Дополнительные сведения см. в этом ответе . Вот соответствующий срез вашей программы для запроса pythag(X,Y,Z,20), false:

pythag(X,Y,Z,N) :-
   int_triple(X,Y,Z,N), false,
   Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :-
   is_int(S), false,
   minus(S,X,S1), X>0, X<N,
   minus(S1,Y,Z), Y>0, Y<N.

is_int(0) :- false.
is_int(X) :-
   is_int(Y), false,
   X is Y+1.

Обратите внимание, что от вашей программы осталось не так много вещей. Например, фактическое уравнение исчезло (это более или менее логическая часть...). Тем не менее, этот фрагмент актуален. И пока вы ничего не измените в этом фрагменте, проблема не исчезнет! Это гарантировано для чистой монотонной программы, такой как эта...

Вот мое предпочтительное решение: оно использует length/2 и between/3, два часто поддерживаемых предиката Пролог Пролога.

pythag2(X,Y,Z,N) :-
   length(_, N),
   between(1,N,X),
   between(1,N,Y),
   between(1,N,Z),
   Z*Z =:= X*X + Y*Y.
person false    schedule 09.05.2012
comment
Спасибо чувак! Очень информативно. Хотел реализовать это без встроенных функций, но победа есть победа. - person RandellK02; 10.05.2012
comment
@ RandellK02: и length/2, и between/3 могут быть реализованы в Прологе. Тем не менее, есть много крошечных хитрых случаев, на которые стоит обратить внимание. Так что лучше придерживайтесь существующего (надеюсь, проверенного) кода библиотеки. - person false; 10.05.2012

arrow_upward
3
arrow_downward

Недавно я тоже думал о решении на Прологе для нахождения пифагорейских троек. Я придумал немного другой код. Предположим, у нас есть функция:

isqrt(a) = floor(sqrt(a))

Тогда достаточно перечислить x и y и проверить, является ли x*x+y*y квадратом некоторого z. А именно проверить:

h = x*x+y*y, z = isqrt(h), z*z = h ?

Функцию isqrt можно реализовать с помощью деления пополам. Для нарушения симметрии мы можем перечислить y после x. Предполагая, что N = 99, результирующий код:

% between(+Integer, +Integer, -Integer)
between(Lo, Hi, _) :-
   Lo > Hi, !, fail.
between(Lo, _, Lo).
between(Lo, Hi, X) :-
   Lo2 is Lo+1, between(Lo2, Hi, X).

% bisect(+Integer, +Integer, +Integer, -Integer)
bisect(Lo, Hi, X, Y) :-
    Lo+1 < Hi, !,
    M is (Lo+Hi) // 2,
    S is M*M,
    (S > X -> bisect(Lo, M, X, Y);
     S < X -> bisect(M, Hi, X, Y);
     M = Y).
bisect(Lo, _, _, Lo).

% pythago(-List)
pythago(X) :-
   X = [A,B,C],
   between(1, 99, A),
   between(A, 99, B),
   H is A*A+B*B,
   bisect(0, H, H, C),
   C =< 99, H =:= C*C.

Таких троек Пифагора должно быть 50, см. также Sloan A046083:

?- findall(-, pythago(_), L), length(L, N).
N = 52.

Можно было бы провести перекрестную проверку со следующим решением CLP(FD).

:- use_module(library(clpfd)).

% pythago3(-List)
pythago3(X) :-
   X = [A,B,C],
   X ins 1..99,
   A*A+B*B #= C*C,
   A #=< B,
   label(X).

Это дает одинаковое количество решений:

?- findall(-, pythago3(_), L), length(L, N).
N = 50.
person Mostowski Collapse    schedule 31.08.2013