Первые шаги в ПРОЛОГе

[SamGold]

Пытаюсь найти сумму целых чисел в интервале от А до В.

Используется синтаксис Prolog

sum(B,B,S):-!.
sum(А,B,S):-
 А1 is A+1,
 S is A+A1,
 sum(A1,B,S).
 

В дальнейшем a,b некоторые целочисленные константы.
В ответ на запрос sum(а,b,X). компилятор выдаёт true если а=b, в остальных случаях false.
Пожалуйста, укажите в чём ошибка.

[Pphantom]

Если исходный вызов имеет вид sum(3,3,X) (например), то сразу же удовлетворяется первая альтернатива для предиката sum (при этом, правда, переменная X не конкретизируется) и Вы получаете true.

Если же исходный вызов имел вид sum(3,4,X), то результат выглядит так. Поскольку первые два аргумента различаются, то сначала выбирается вторая альтернатива, A1 становится равным 4, а S - 7. Затем выполняется вызов sum(4,4,7). По той же причине снова выбирается вторая альтернатива, но тут уже переменная S конкретизирована, поэтому попытка выполнения S is A+A1 оказывается неудачной: 7 is 4+5 возвращает false.

К тому же Вы явно запутались в том, какой из аргументов предиката должен быть "служебным" (чтобы в нем накапливался результат), а какой предназначен для возврата итогового значения. Код написан в расчете на то, что итог должен появляться во втором аргументе, но тогда вызов вроде sum(3,4,X) лишен смысла.

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

Используется синтаксис Prolog

sum(A,A,A).
sum(A,B,S):-A1 is A+1,sum(A1,B,S1), S is S1+A.
 

Тут первые два аргумента - нижняя и верхняя границы интервала, третий - возвращаемое значение.

[SamGold]

Pphantom в сообщении #858812 писал(а):

Затем выполняется вызов sum(4,4,7). По той же причине снова выбирается вторая альтернатива

Не уверен, что понял о чём речь. Аргументы 1 и 2 теперь одинаковые. Почему игнорируется первое предложение?

А вот мой вариант с 4-мя переменными, как Вы предлагали:

Используется синтаксис Prolog

sum(B,B,S,R):-R is S+B,!.
sum(A,B,S,R):-
 S1 is S+A,
 A1 is A+1,
 sum(A1,B,S1,R).
 

Меня не покидает чувство, что написано коряво. Буду рад услышать комментарии и советы.

[arseniiv]

(В любом случае, пролог или не пролог, если есть функция предикат с дополнительным параметром, должен быть и определяемый через него предикат без такого параметра, чтобы пользователя не путать — ведь он не обязан знать, какое значение давать тому лишнему параметру.)

[Pphantom]

SamGold в сообщении #859100 писал(а):

Не уверен, что понял о чём речь. Аргументы 1 и 2 теперь одинаковые. Почему игнорируется первое предложение?

Да, я тут увлекся, взявшись объяснять вывод. Но на самом деле Вы тоже "постарались" - при внимательной проверке обнаруживается, что у Вас перепутана кириллица и латиница в обозначениях переменных, что и привело к такому забавному эффекту.

[SamGold]

arseniiv в сообщении #859129 писал(а):

предикат с дополнительным параметром, должен быть и определяемый через него предикат без такого параметра

Если я правильно Вас понял, то имелось в виду нечто вроде этого:

Используется синтаксис Prolog

sum(B,B,S,R):-R is S+B,!.
sum(A,B,S,R):-
 S1 is S+A,
 A1 is A+1,
 sum(A1,B,S1,R).

sum(A,B,R):-sum(A,B,0,R).
 

?

Ещё два вопроса, но уже по другой задаче. Нужно возвести вещественное число в целочисленную степень. Вот моя реализация:

Используется синтаксис Prolog

pow(A,0,P,R):-R is P.
pow(A,N,P,R):-
 N>=1,
 P1 is P*A,
 N1 is N-1,
 pow(A,N1,P1,R),
 !.
pow(A,N,P,R):-
 P1 is P/A,
 N1 is N+1,
 pow(A,N1,P1,R).

pow(A,N,R):-pow(A,N,1,R).
 

1. Хотелось бы улучшить программу таким образом, чтобы возведение в чётную степень происходило по такой схеме $a^{2n}=a^{n}\cdot a^{n}$
2. Опять же приветствуются замечания и пожелания по поводу корявости предложенного кода.

-- 06.05.2014, 13:45 --

Pphantom в сообщении #859156 писал(а):

обнаруживается, что у Вас перепутана кириллица и латиница в обозначениях переменных

Прошу прощения за свой промах.

[arseniiv]

SamGold в сообщении #859853 писал(а):

Если я правильно Вас понял, то имелось в виду нечто вроде этого

Ага.

[Pphantom]

SamGold в сообщении #859853 писал(а):

1. Хотелось бы улучшить программу таким образом, чтобы возведение в чётную степень происходило по такой схеме $a^{2n}=a^{n}\cdot a^{n}$

Можно добавить вторую альтернативу к pow/4, например, такого вида:

Используется синтаксис Prolog

pow(A,N,_,R):- Z is N mod 2, Z=0, N1 is N/2, pow(A,N1,1,R1), R is R1*R1.

SamGold в сообщении #859853 писал(а):

2. Опять же приветствуются замечания и пожелания по поводу корявости предложенного кода.

В первой альтернативе стоит заменить A на подчеркивание - значение все равно не требуется. Ну и, в принципе, можно отказаться от "интерфейсного" предиката, если убрать хвостовую рекурсию:

Используется синтаксис Prolog

pow(_,0,1).
pow(A,N,R):- Z is N mod 2, Z=0, N1 is N/2, pow(A,N1,1,R1), R is R1*R1.
pow(A,N,R):- N>0, N1 is N-1, pow(A,N1,R1), R is R1*A.
pow(A,N,R):- N1 is N+1, pow(A,N1,R1), R is R1/A.

[SamGold]

Pphantom в сообщении #859894 писал(а):

Можно добавить вторую альтернативу к pow/4, например, такого вида:

Спасибо за наводку на мысль, но код не корректный. Вот мой вариант рабочего кода:

Используется синтаксис Prolog

pow(_,0,P,R):-R is P.
pow(A,N,P,R):-
 Z is N mod 2,
 Z=0,
 N1 is N/2,
 pow(A,N1,1,R1),
 R is P*R1*R1,
 !.
pow(A,N,P,R):-
 N>=1,
 P1 is P*A,
 N1 is N-1,
 pow(A,N1,P1,R),
 !.
pow(A,N,P,R):-
 P1 is P/A,
 N1 is N+1,
 pow(A,N1,P1,R).

pow(A,N,R):-pow(A,N,1,R).
 

Pphantom в сообщении #859894 писал(а):

убрать хвостовую рекурсию

Разве хвостовая рекурсия не предпочтительнее тем, что при оптимизации компилятором превращается в итерацию, тем самым спасая стек от возможного переполнения? (Код без хвостовой рекурсии не рабочий)

-- 07.05.2014, 10:57 --

Проблема с разложением синуса в ряд Маклорена. В результате запроса получаю гигантскую серию приближений, оканчивающиуюся 1-чкой. Прошёлся по шагам алгоритма с карандашиком, но не могу найти ошибку.

Используется синтаксис Prolog

sinus(X,E,I,C,S,R):-
 abs(C)>E,
 C1 is -1*C*X*X/(2*I-1)*(2*I-2),
 I1 is I+1,
 S1 is S+C1,
 sinus(X,E,I1,C1,S1,R).

sinus(X,E,I,C,S,R):-
 R is S.

sinus(X,E,R):-
 sinus(X,E,2,X,X,R).
 

[SamGold]

Составить программу, осуществляющую подбор
партнера и партнерши в бальных танцах на основании
следующих правил:
Рост мальчика >роста девочки, но не более, чем на 10 см
Танцевальный класс мальчика выше или равен классу
девочки

Используется синтаксис Prolog

guy("Bob",175,"C").
guy("Enthony",180,"B").
guy("Pol",160,"D").
guy("Nick",160,"E").
guy("Fred",176,"A").
doll("Luise",165,"D").
doll("Nataly",168,"C").
doll("Claudie",158,"A").
doll("Mary",172,"B").
doll("Ann",170,"C").
pair(X,Y,R1,R2):-
 guy(X,H1,P1),
 doll(Y,H2,P2),
 H1>H2,
 H1 - H2 =< 10,
 P1=<P2,
 R1 = X,
 R2 = Y.
 

Проблема в том, что на выводе у меня списки вместо строк. Пока не нашёл как осуществить преобразования внутренними средствами ПРОЛОГа.

[Pphantom]

SamGold в сообщении #860120 писал(а):

Спасибо за наводку на мысль, но код не корректный.

Да, вредно писать код прямо в форуме без проверки.

SamGold в сообщении #860120 писал(а):

Разве хвостовая рекурсия не предпочтительнее тем, что при оптимизации компилятором превращается в итерацию, тем самым спасая стек от возможного переполнения?

Это все-таки Пролог, тут с компиляторами туго (если не считать Turbo/PDC/Visual Prolog, который, в частности, из-за этого не совсем Пролог). Да и практическая глубина рекурсии в этой задаче такая, что проблем не возникнет.

SamGold в сообщении #860120 писал(а):

Код без хвостовой рекурсии не рабочий)

Его надо исправить в одном месте: во второй альтернативе при вызове pow убрать третий аргумент (единицу). Это опять-таки следствие правки кода прямо в форуме без проверки.

SamGold в сообщении #860120 писал(а):

Проблема с разложением синуса в ряд Маклорена.

Есть одна чисто вычислительная ошибка - при подсчете очередного члена надо было делить на 2*I-2, а не умножать. А в остальном вроде все в порядке, только очень громоздко.

-- 08.05.2014, 00:48 --

SamGold в сообщении #860208 писал(а):

Проблема в том, что на выводе у меня списки вместо строк.

Все тривиально: замените везде двойные кавычки на одинарные.

Впрочем, есть и еще один способ: если Вам зачем-то нужна строка сначала именно как список символов (в данном случае это излишне), а потом ее нужно вывести, то можно воспользоваться встроенным предикатом name(A,B) - первый аргумент это строка в "нормальном" представлении, второй - список символов. В обратном направлении он тоже работает.

[SamGold]

Pphantom в сообщении #860404 писал(а):

Есть одна чисто вычислительная ошибка - при подсчете очередного члена надо было делить на 2*I-2, а не умножать

Спасибо. Долго бы ещё мучался, наверное .

Pphantom в сообщении #860404 писал(а):

только очень громоздко

Наверное виной опять моё неравнодушие к хвостовой рекурсии . На досуге подумаю как поправить.

Pphantom в сообщении #860404 писал(а):

Все тривиально: замените везде двойные кавычки на одинарные.

Опять же, долго бы пришлось искать. Спасибо.

Pphantom в сообщении #860404 писал(а):

встроенным предикатом name(A,B)

Хорошо, что написали и об этом. Уже предчувствую, что он будет мне не раз полезен в дальнейшем изучении.
Вот исправленный код для разложения синуса:

Используется синтаксис Prolog

sinus(X,E,I,C,S,R):-
 abs(C)=<E,
 R is S,
 !.
sinus(X,E,I,C,S,R):-
 C1 is -1*C*X*X/((2*I-1)*(2*I-2)),
 I1 is I+1,
 S1 is S+C1,
 sinus(X,E,I1,C1,S1,R).

sinus(X,E,R):-
 sinus(X,E,2,X,X,R).

Сходится достаточно точно для любых аргументов из диапазона.

[SamGold]

А тут код, который выполняет разложение для любого аргумента из $\mathbb{R}$:

Используется синтаксис Prolog

sinus(_,E,_,C,S,R):-
 abs(C)=<E,
 R is S,
 !.
sinus(X,E,I,_,_,R):-
 X > 6.28,
 X1 is X-6.28,
 sinus(X1,E,I,X1,X1,R),
 !.
sinus(X,E,I,_,_,R):-
 X < -6.28,
 X1 is X+6.28,
 sinus(X1,E,I,X1,X1,R),
 !. 
sinus(X,E,I,C,S,R):-
 C1 is -1*C*X*X/((2*I-1)*(2*I-2)),
 I1 is I+1,
 S1 is S+C1,
 sinus(X,E,I1,C1,S1,R).

sinus(X,E,R):-
 sinus(X,E,2,X,X,R).

[SamGold]

Вот мои каракули по теме "Работа со списками":

Используется синтаксис Prolog

%Максимум из 2-х чисел
max(X,Y,Z):-
 X >= Y,
 Z is X,
 !.
max(_,Y,Z):-
 Z is Y.
max(X,Y):-
 max(X,Y,Z),
 write(Z).

%Максимум списка
fmax([],Z,R):-
 R is Z.
fmax([H|T],Z,R):-
 max(H,Z,Z1),
 fmax(T,Z1,R).

fmax([H|T],R):-
 fmax([H|T],0,R).

%Удаление всех вхождений элемента
% из списка
removeall([],_,[]).
removeall([X|T],X,L):-
 removeall(T,X,L),
 !.
removeall([Y|T],X,[Y|L]):-
 X=\=Y,
 removeall(T,X,L).

%Удаление всех вхождений максимального
% элемента списка
removemax(X,L):-
 fmax(X,M),
 removeall(X,M,L).

%Нумерация элементов списка
fn([],_,_,_).
fn([H|_],H,N,R):-R is N.
fn([_|T],V,N,R):-
 N1 is N+1,
 fn(T,V,N1,R).
fn([H|T],V,R):-
 fn([H|T],V,1,R).

%Номер максимального элемента списка
fnmax([],_).
fnmax(L,N):-
 fmax(L,Z),
 fn(L,Z,R),
 N is R,
 !.

%Среднее арифметическое списка
mean([],0,_,R):-
 R is 0,
 !.
mean([],S,N,R):-
 R is S/N,
 !.
mean([X|T],S,N,R):-
 X =:= 0,
 mean(T,S,N,R),
 !.
mean([X|T],S,N,R):-
 S1 is S+X,
 N1 is N+1,
 mean(T,S1,N1,R).
mean([X|T],R):-
 mean([X|T],0,0,R).

%Среднее арифметическое списка
% из которого исключены все 
% элементы равные максимальному
fmean(L1,R):-
 removemax(L1,Z),
 mean(Z,R).
 

Жду и надеюсь на критику.
И ещё кое-что. Уже долго думаю над тем, как найти медиану списка, но "зараза императивного программирования" не даёт мне придумать хоть что-нибудь похожее на код на ПРОЛОГе. Намекните хотя бы от чего отталкиваться. Спасибо.

[Pphantom]

SamGold в сообщении #861237 писал(а):

Жду и надеюсь на критику.

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

Используется синтаксис Prolog

max(X,Y,X):-X >= Y.
max(_,Y,Y).
 

Аналогично и максимум списка можно записать короче, причем сразу, без изпользования максимума двух чисел:

Используется синтаксис Prolog

fmax([X],X).
fmax([X|T],Y):-fmax(T,Y),Y>X.
fmax([X|_],X).
 

Попробуйте при продумывании реализации того или иного предиката сначала описать его определение "математическим" образом - не в виде алгоритма, а в виде некоторого определения (с кванторами и т.п.), и потом пытайтесь реализовывать именно его. Обычно это сильно упрощает дело.

SamGold в сообщении #861237 писал(а):

Уже долго думаю над тем, как найти медиану списка,

Банальный вариант - сортировка и значение со средним номером - не годятся? Или Вы пытаетесь написать линейную?