Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 19:48

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Решение задачи на Prolog'e
СообщениеДобавлено: Пт янв 28, 2011 11:47 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
решение задачи на Prolog'e viewtopic.php?f=19&t=2698
раскрасить не получилось, но в Bred3 есть подсветка, иначе трудно разобрать
Код:
lists_of_pair(A,B,[], [[1, [A,B] ] ] ) .
lists_of_pair(A,B,[C|D], [E|F] ) :-
   C = [ G, [A,B] ], ! , H is G + 1 , E =  [ H, [A,B] ] , F = D
   ;        E = C , lists_of_pair( A, B, D, F ) .

pair_or_no(A, B, Sp, List_before, List_after) :-
   B == Sp , ! , List_before = List_after;  A == Sp , ! , List_before = List_after; 
   lists_of_pair(A,B,List_before, List_after ).

min_max( A , Space, Pairs_before, Pairs_after ) :- A = [] , Pairs_after = Pairs_before .
min_max([A|B] , Space, Pairs_before, Pairs_after ) :- B = [] , Pairs_after = Pairs_before .
min_max( [A|B] , Space, Pairs_before, Pairs_after ) :-    B = [C|D] ,  pair_or_no(A, C, Space, Pairs_before, P) , min_max( B , Space, P, Pairs_after ) .

count(A,B,C) :- A = [], B = C.
count(A,B,C) :- A =[L1|L2], L1 = [ G, [E,F] ], C = [ H, [I,K]], H >= G, count(L2,B,C) .
count(A,B,C) :- A =[L1|L2], L1 = [ G, [E,F] ], C = [ H, [I,K]], H < G, count(L2,B,L1) .

symbols( [], [] ).   
symbols([A|B], List_2):- member(A,B), ! , symbols(B, List_2) ;    List_2 = [A|D]  ,  symbols(B,D) .   

run_with_symbols(A , [] , Result , Temp, Rest,Rtemp) :- Result = Temp, Rest=Rtemp.
run_with_symbols( A , [B|C] , Result, Temp, Rres, Rtemp) :- /*  [B|C]  - Space symbols */
   min_max( A , B, [], Pairs_after ), 
   count(Pairs_after, R, [ 0 , [ _ , _ ] ] ), R = [ D , [ E , F ] ] , Temp = [[ G , [ H , I ], Symbol ] | _ ],
   (
      var(G) -> Temp2 =  [ [ D , [ E , F ], B ]  ] , Rtemp2 =  Rtemp  ;
      D > G -> Temp2 = Temp , Rtemp2 = [ [ D , [ E , F ], B ]  |  Rtemp ]  ;
      D = G -> Temp2 =[  [ D , [ E , F ], B  ] | Temp ] , Rtemp2 = Rtemp  ;
      D < G -> Temp2 = [ [ D , [ E , F ], B ]  ] ,  append(Temp, Rtemp,  Rtemp2) 
   ) , run_with_symbols( A, C,  Result, Temp2, Rres, Rtemp2) .
/*              comment    writelist4/1 and run/1 if no SWI  */
writelist4( List4) :- List4 = [] ;
   List4 = [ [ D , [ E , F ], B ]  |  L4Rest ], writef(' For symbol %w pair %w %w found %w times\n\n' , [B, E,F,D]),
   writelist4( L4Rest) .
run(List) :-  symbols( List, Symbols ) , run_with_symbols( List , Symbols , Result, [[ Temp_value , [ _ , _ ] , _]] , Rresult, []) ,
   write('\n\nSOLUTIONS\n--------------------\n'),    writelist4(Result),
   write('\n\nNO SOLUTIONS\n--------------------\n'), writelist4(Rresult).

   
/*              uncomment  next   writelist4/1 and run/1 if GNU-Prolog used */
/*
writelist4( List4) :- List4 = [] ;
   List4 = [ [ D , [ E , F ], B ]  |  L4Rest ], format(' For symbol %d pair %d %d found %d times\n\n' , [B, E,F,D]),
   writelist4( L4Rest) .
run(List) :-  symbols( List, Symbols ) , run_with_symbols( List , Symbols , Result, [[ Temp_value , [ _ , _ ] , _]] , Rresult, []) ,
   format('\n\nSOLUTIONS\n--------------------\n', [] ),    writelist4(Result),
   format('\n\nNO SOLUTIONS\n--------------------\n',[] ), writelist4(Rresult).   
*/   
   

его нужно запустить либо из-под SWI-Prolog'a либо можно из-под GNU-Prolog'a. Отличаются только функции вывода. Нужно раскомментировать соответствующую. Решение не самое изящное :( но я уложился в 37 строк как и Antender на Euphoria
из него понятно, что нужно.
Задачу :( нужно вводить в виде run( [ 1,2,3,2,1,2,3,2,1,2,3,2,1,2,3,2,1,2,3 ]).
Строка в заглавном сообщении выдаст

Цитата:
SOLUTIONS
--------------------
For symbol 2 pair 5 4 found 2 times

For symbol 3 pair 2 1 found 2 times



NO SOLUTIONS
--------------------
For symbol 1 pair 3 2 found 4 times

For symbol 6 pair 3 2 found 4 times

For symbol 5 pair 3 2 found 4 times

For symbol 4 pair 3 2 found 4 times

For symbol 7 pair 3 2 found 4 times


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Пт янв 28, 2011 13:17 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
вопрос писал(а):
Решение не самое изящное :(

Да уж :D Способно отпугнуть от пролога тех, кто не знает возможности этого языка.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Пт янв 28, 2011 15:02 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
dynamic-wind писал(а):
Да уж :D Способно отпугнуть от пролога тех, кто не знает

Предложите своё, задача простая для Prolog'a


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Пт янв 28, 2011 21:54 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
задача простая для Prolog'a

Почему так много текста? Пролог так не лаконичен?

Для какой исходной последовательности приведено решение?

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Пт янв 28, 2011 22:20 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
chess писал(а):
вопрос писал(а):
задача простая для Prolog'a

Почему так много текста? Пролог так не лаконичен?

Для какой исходной последовательности приведено решение?

Prolog не лаконичен и не не лаконичен. Исходник содержит ровно столько, сколько содержит логика решения задачи для данного алгоритма.
Но я думаю, что существует более изящное решение. А это - такое, какое виделось мне. Это полный перебор для "задачи поиска минимума среди максимальных показателей с сохранением полной информации о поиске"


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 12:57 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Вот, может подсказкой будет следующий код на Прологе...
Код:
%**********************************************************************
% написать предикат p(L,S) - истинный тогда и только тогда,
% когда L - список списков, а S - предикат объединяющий все эти списки.
%**********************************************************************


%**********************************************************************
% проверка на то, что элемент является списком
%**********************************************************************
listp([]).
listp([_|_]).

%**********************************************************************


%**********************************************************************
% конкатенация двух произвольных списков
%**********************************************************************
append([],L,L).
append([H1|T1],L2,[H1|T3]) :- append(T1,L2,T3).

%**********************************************************************


%**********************************************************************
% разработанный предикат - сопоставление списков
%**********************************************************************

p([],[]). % пустой список сопоставим сам с собой
p([H|T],S) :-
    listp(H),  % элементом списка должен быть список

    % вычисление списка S1,
    % который необходимо добавить к первому элементу списка - H,
    % чтобы получить конечный список S
    append(H,S1,S),

    p(T,S1).  % сопоставить хвост списка - T с полученным списком S1

%**********************************************************************


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 12:59 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
И вот еще
Код:
%**********************************************************************
% написать предикат p(L,N) - истинный тогда и только тогда,
% когда N - число различных элементов списка L.
%**********************************************************************


%**********************************************************************
% проверка на то, что элемент Х уже пристутсвует в списке
%**********************************************************************
member(X,[X|_]) :- !.
member(X,[_|T]) :- member(X,T).

%**********************************************************************


%**********************************************************************
% вычисление длины списка
%**********************************************************************
length(L,R) :- length(L,0,R), !.

length([],R,R). % длина пустого списка не влияет на длину всего списка
length([_|T],C,R) :- C1 is C+1, length(T,C1,R).

%**********************************************************************


%**********************************************************************
% Удаление повторяющихся элементов из списка
%**********************************************************************
removed(L,R) :- removed(L,[],R), !.

removed([H|T],L,R) :-
    % если H не элемент списка L, то выполняется
    % следующее за этим определение
    member(H,L), !,

    % удалить из хвоста списка T список L
    removed(T,L,R).

removed([H|T],L,[H|R]) :-
    % формирование списка результата без повторяющихся данных
    removed(T,[H|L],R).

removed([],_,[]).

%**********************************************************************


%**********************************************************************
% Предикат
%**********************************************************************
p(L,N) :-
    removed(L,L1),  % удаление повторных вхождений в списке L
    length(L1,N).   % вычисление длины списка

%**********************************************************************


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 13:03 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
ну так, на всякий случай
Код:
%**********************************************************************
% написать предикат p(L,S) - истинный тогда и только тогда,
% когда список S есть циклическая перестановка списка L.
%**********************************************************************


%**********************************************************************
% конкатенация двух произвольных списков
%**********************************************************************
append([],L,L).
append([H1|T1],L2,[H1|T3]) :- append(T1,L2,T3).

%**********************************************************************

%**********************************************************************
% обращение списка
%**********************************************************************
reverse([],[]).
reverse([H|T],S) :- reverse(T,L), append(L,[H],S).

%**********************************************************************

%**********************************************************************
% разработанный предикат - циклический сдвиг
%**********************************************************************

% сдвиг влево
shiftl([H|T],S) :- append(T,[H],S).
% сдвиг вправо
shiftr(L,S) :- reverse(L,S1), shiftl(S1,S2), reverse(S2,S).

%**********************************************************************


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 13:21 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Интересно, к чему это подсказки?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 14:50 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
вопрос писал(а):
Интересно, к чему это подсказки?

Ну может программа попроще станет, чем она в самом первом посту темы :shuffle;

Просто мне лень в чужом коде копаться когда нет алгоритма оформленного отдельно.
Иногда неясно что хочет автор особенно обращаю внимание на множестов отсечений !. применение точек с запятой в Прологе приводит к непониманию особенно больших последовательностей преобразований, - лучше лишнее определение написать, скорость от этог не изменится


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 15:43 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Вот первый пример сопоставление списка списков с простым списком можно применить для получения возможных комбинаций последовательноси входных символов. Вызов предиката p([X,_],[1,2,3,4]) для инициализации значений путем сопоставления даст результаты
Код:
p([X,_],[1,2,3,4]).
X = [] ;
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4] ;
false.

Дальше можно начальный список повернуть на один элемент влево (взять из последнего примера предикат shiftl) и повторить получения значений. Для удобства еще операторы bagof и findall существуют. И представление данных - возможные наборы разделителй и число их появлений связать термом вида список/число вхождений.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Сб фев 05, 2011 16:58 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хм, я не знаю, как комментировать?
Вообще, например member в SWI или GNU Prolog
это встроенный предикат и в исходном тексте он там есть.
так же как reverse и append

Да, это всё хорошо, несомненно.

Это решение было для того, чтобы можно было запустить и проверить правильность решения задачи на Forth или Euphoria a не для того. чтобы демонстрировать возможности Prolog'a

В любом случае я рад, что Prolog стал предметом обсуждения. :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Вт фев 08, 2011 17:35 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
вот по-моему решение попроще (SWI-Prolog)
входная строка задается атомом,
which_char/1 -- для печати сразу всех решений
which_char/2 -- для перебора по одному

:- dynamic pair/3.

which_char(S) :-
setof(C, which_char(S, C), Cs),
repeat, ( member(X,Cs), print(X), nl, fail; true ).

which_char(S, C) :-

cleanup,
name(S, L),
collect_pairs(L),
min_max(L, Code),
name(C, [Code]).

cleanup :- retractall(pair(_,_,_)).

min_max(L, Code) :-
maxes(L, Ms),
min(Ms, Code).

maxes(L, Ms) :-
setof( (C, M),
( member(C, L), max(C, M) ),
Ms ).

max(C, M) :- max(C, M, 0).
max(C, M, N) :-
pair(X, Y, K),
X \= C, Y \= C, K > N, !,
max(C, M, K).
max(_, M, M).

min([T| L], Code) :-
min(L, T, (Code, _)).
min([], M, M).
min([ (C, N) | L ], (C1, N1), M) :-
N = N1, % (проверка на равенство -- для поиска всех решений)
( min( L, (C1, N1), M )
; min( L, (C, N), M )).
min([ (C, N) | L ], (_, N1), M) :-
N < N1, !,
min( L, (C, N), M ).
min([ _ | L ], T, M) :-
min(L, T, M).

collect_pairs([X, Y| L]) :-

pair(X, Y, N), !,
N1 is N + 1,
retract(pair(X, Y, N)),
assert(pair(X, Y, N1)),
collect_pairs([Y| L]).

collect_pairs([X, Y| L]) :-

assert(pair(X, Y, 0)),
collect_pairs([Y| L]).

collect_pairs(_).


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Вт фев 08, 2011 19:14 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Да. это решение более изящное :) :idea:

Моё могло б похвастать в сравнении с этим только более информативным выводом :) (это нужно было для проверки решений задачи на форте)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Решение задачи на Prolog'e
СообщениеДобавлено: Вт фев 08, 2011 19:59 
Не в сети

Зарегистрирован: Вт фев 08, 2011 07:15
Сообщения: 18
Откуда: Беларусь
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
спасибо а не могли бы вы рассказать про свой алгоритм?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB