Forth http://fforum.winglion.ru/ |
|
Решение задачи на Prolog'e http://fforum.winglion.ru/viewtopic.php?f=12&t=2704 |
Страница 1 из 2 |
Автор: | вопрос [ Пт янв 28, 2011 11:47 ] |
Заголовок сообщения: | Решение задачи на Prolog'e |
решение задачи на 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 |
Автор: | dynamic-wind [ Пт янв 28, 2011 13:17 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
вопрос писал(а): Решение не самое изящное Да уж Способно отпугнуть от пролога тех, кто не знает возможности этого языка. |
Автор: | вопрос [ Пт янв 28, 2011 15:02 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
dynamic-wind писал(а): Да уж Способно отпугнуть от пролога тех, кто не знает Предложите своё, задача простая для Prolog'a |
Автор: | chess [ Пт янв 28, 2011 21:54 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
вопрос писал(а): задача простая для Prolog'a Почему так много текста? Пролог так не лаконичен? Для какой исходной последовательности приведено решение? |
Автор: | вопрос [ Пт янв 28, 2011 22:20 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
chess писал(а): вопрос писал(а): задача простая для Prolog'a Почему так много текста? Пролог так не лаконичен? Для какой исходной последовательности приведено решение? Prolog не лаконичен и не не лаконичен. Исходник содержит ровно столько, сколько содержит логика решения задачи для данного алгоритма. Но я думаю, что существует более изящное решение. А это - такое, какое виделось мне. Это полный перебор для "задачи поиска минимума среди максимальных показателей с сохранением полной информации о поиске" |
Автор: | Alexander [ Сб фев 05, 2011 12:57 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Вот, может подсказкой будет следующий код на Прологе... Код: %**********************************************************************
% написать предикат 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 %********************************************************************** |
Автор: | Alexander [ Сб фев 05, 2011 12:59 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
И вот еще Код: %**********************************************************************
% написать предикат 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). % вычисление длины списка %********************************************************************** |
Автор: | Alexander [ Сб фев 05, 2011 13:03 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
ну так, на всякий случай Код: %**********************************************************************
% написать предикат 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). %********************************************************************** |
Автор: | вопрос [ Сб фев 05, 2011 13:21 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Интересно, к чему это подсказки? |
Автор: | Alexander [ Сб фев 05, 2011 14:50 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
вопрос писал(а): Интересно, к чему это подсказки? Ну может программа попроще станет, чем она в самом первом посту темы Просто мне лень в чужом коде копаться когда нет алгоритма оформленного отдельно. Иногда неясно что хочет автор особенно обращаю внимание на множестов отсечений !. применение точек с запятой в Прологе приводит к непониманию особенно больших последовательностей преобразований, - лучше лишнее определение написать, скорость от этог не изменится |
Автор: | Alexander [ Сб фев 05, 2011 15:43 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Вот первый пример сопоставление списка списков с простым списком можно применить для получения возможных комбинаций последовательноси входных символов. Вызов предиката 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 существуют. И представление данных - возможные наборы разделителй и число их появлений связать термом вида список/число вхождений. |
Автор: | вопрос [ Сб фев 05, 2011 16:58 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Хм, я не знаю, как комментировать? Вообще, например member в SWI или GNU Prolog это встроенный предикат и в исходном тексте он там есть. так же как reverse и append Да, это всё хорошо, несомненно. Это решение было для того, чтобы можно было запустить и проверить правильность решения задачи на Forth или Euphoria a не для того. чтобы демонстрировать возможности Prolog'a В любом случае я рад, что Prolog стал предметом обсуждения. |
Автор: | : AL/M ; [ Вт фев 08, 2011 17:35 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
вот по-моему решение попроще (SWI-Prolog) входная строка задается атомом, which_char/1 -- для печати сразу всех решений which_char/2 -- для перебора по одному :- dynamic pair/3. |
Автор: | вопрос [ Вт фев 08, 2011 19:14 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
Да. это решение более изящное Моё могло б похвастать в сравнении с этим только более информативным выводом (это нужно было для проверки решений задачи на форте) |
Автор: | : AL/M ; [ Вт фев 08, 2011 19:59 ] |
Заголовок сообщения: | Re: Решение задачи на Prolog'e |
спасибо а не могли бы вы рассказать про свой алгоритм? |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |