2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Первые шаги в ПРОЛОГе
Сообщение04.05.2014, 12:19 
Аватара пользователя
Пытаюсь найти сумму целых чисел в интервале от А до В.
Используется синтаксис 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.
Пожалуйста, укажите в чём ошибка.

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение04.05.2014, 13:43 
Если исходный вызов имеет вид 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.
 

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение04.05.2014, 22:25 
Аватара пользователя
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).
 

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение04.05.2014, 22:46 
(В любом случае, пролог или не пролог, если есть функция предикат с дополнительным параметром, должен быть и определяемый через него предикат без такого параметра, чтобы пользователя не путать — ведь он не обязан знать, какое значение давать тому лишнему параметру.)

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение04.05.2014, 23:07 
SamGold в сообщении #859100 писал(а):
Не уверен, что понял о чём речь. Аргументы 1 и 2 теперь одинаковые. Почему игнорируется первое предложение?

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение06.05.2014, 14:41 
Аватара пользователя
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 писал(а):
обнаруживается, что у Вас перепутана кириллица и латиница в обозначениях переменных

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение06.05.2014, 15:30 
SamGold в сообщении #859853 писал(а):
Если я правильно Вас понял, то имелось в виду нечто вроде этого
Ага.

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение06.05.2014, 17:32 
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.

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение07.05.2014, 11:53 
Аватара пользователя
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).
 

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение07.05.2014, 17:45 
Аватара пользователя
Составить программу, осуществляющую подбор
партнера и партнерши в бальных танцах на основании
следующих правил:
Рост мальчика >роста девочки, но не более, чем на 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.
 

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение08.05.2014, 00:43 
SamGold в сообщении #860120 писал(а):
Спасибо за наводку на мысль, но код не корректный.
Да, вредно писать код прямо в форуме без проверки. :oops:

SamGold в сообщении #860120 писал(а):
Разве хвостовая рекурсия не предпочтительнее тем, что при оптимизации компилятором превращается в итерацию, тем самым спасая стек от возможного переполнения?
Это все-таки Пролог, тут с компиляторами туго (если не считать Turbo/PDC/Visual Prolog, который, в частности, из-за этого не совсем Пролог). Да и практическая глубина рекурсии в этой задаче такая, что проблем не возникнет.

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

SamGold в сообщении #860120 писал(а):
Проблема с разложением синуса в ряд Маклорена.
Есть одна чисто вычислительная ошибка - при подсчете очередного члена надо было делить на 2*I-2, а не умножать. А в остальном вроде все в порядке, только очень громоздко.

-- 08.05.2014, 00:48 --

SamGold в сообщении #860208 писал(а):
Проблема в том, что на выводе у меня списки вместо строк.

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

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение08.05.2014, 07:42 
Аватара пользователя
Pphantom в сообщении #860404 писал(а):
Есть одна чисто вычислительная ошибка - при подсчете очередного члена надо было делить на 2*I-2, а не умножать

Спасибо. Долго бы ещё мучался, наверное :P.
Pphantom в сообщении #860404 писал(а):
только очень громоздко

Наверное виной опять моё неравнодушие к хвостовой рекурсии :D . На досуге подумаю как поправить.
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).

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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение09.05.2014, 13:56 
Аватара пользователя
А тут код, который выполняет разложение для любого аргумента из $\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).

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение10.05.2014, 10:28 
Аватара пользователя
Вот мои каракули по теме "Работа со списками":
код: [ скачать ] [ спрятать ]
Используется синтаксис 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).
 


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

 
 
 
 Re: Первые шаги в ПРОЛОГе
Сообщение10.05.2014, 13:01 
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 писал(а):
Уже долго думаю над тем, как найти медиану списка,
Банальный вариант - сортировка и значение со средним номером - не годятся? Или Вы пытаетесь написать линейную?

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group