Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу префикс-функция
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
malamut malamut вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.11.2007
По умолчанию 25.11.2007, 22:54

Задача такая. Даётся список и нужно вычислить префикс-функции для каждого элемента. Вообще-то всё не совсем так.
Лучше пример.
например, в слове abracadabra значение этих префикс-функций будет:
P(a)=0
P(ab)=0
P(abr)=0
P(abra)=1
P(abrac)=0
P(abraca)=1
P(abracad)=0
P(abracada)=1
P(abracadab)=2
P(abracadabr)=3
P(abracadabra)=4
Это кол-во символов, которые одновременно являются префиксом и суффиксом. Эти циферки и надо вычислить и вывести списком.
Как я представляю решение:
брать какую-нибудь abracadabra, копировать её, изменить копию, добавляя в начало списка последний элемент (такое есть смысл делать длина(abracadabra)/2 раз). При каждом добавлении по-порядку сравнивать начальный список с изменённым, увеличивая счётчик.
Код:
%добавить элемент в начало списка:
add_elem([], Elem, [Elem]).
add_elem([H|T], Elem, [Elem,H|T]).

%удалить последний элемент списка:
remove_last_elem([], _) :- fail.
remove_last_elem([X], []).
remove_last_elem([X,Y|Z], [X|T]) :-
    remove_last_elem([Y|Z],T).

%возвращает последний элемент списка:
last_elem([Elem], Elem).
last_elem([_|T], Elem) :- last_element(T, Elem).
А вот собрать это вместе не получается Что вы думаете по этому поводу? Наверняка есть решение попроще.
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 26.11.2007, 22:14

Цитата:
Наверняка есть решение попроще.
Попроще, чем какое?

Симпатичная задачка.
Вот простое симпатичное решение. Главное в нем - предикат append. Предложения для него написаны в таком порядке, чтобы находился максимальный подсписок, который является и префиксом, и суффиксом (для префикса исходного списка) одновременно:
Код:
domains
sl = symbol*
predicates
nondeterm f_prefix(sl,sl,integer)
nondeterm prefix(sl,sl)
nondeterm append(sl,sl,sl)
determ max_sub(sl,sl)
length(sl,integer)
clauses
f_prefix(L,P,Value):- 
    prefix(P,L),
    max_sub(P,Sub),
    length(Sub,Value).
    
prefix([A],[A|_]).
prefix([A|P],[A|L]):- prefix(P,L).

max_sub(P,Sub):-
    append(Sub,Rest,P),
    append(_,Sub,Rest),
    !.

append([A|L1],L2,[A|L]):- append(L1,L2,L).
append([],L,L).

length([],0).
length([_|L],V):- length(L,V1),V=V1+1.
goal
f_prefix([a,b,r,a,c,a,d,a,b,r,a],Prefix,Value).
Вот ответ:
Код:
Prefix=["a"], Value=0
Prefix=["a","b"], Value=0
Prefix=["a","b","r"], Value=0
Prefix=["a","b","r","a"], Value=1
Prefix=["a","b","r","a","c"], Value=0
Prefix=["a","b","r","a","c","a"], Value=1
Prefix=["a","b","r","a","c","a","d"], Value=0
Prefix=["a","b","r","a","c","a","d","a"], Value=1
Prefix=["a","b","r","a","c","a","d","a","b"], Value=2
Prefix=["a","b","r","a","c","a","d","a","b","r"], Value=3
Prefix=["a","b","r","a","c","a","d","a","b","r","a"], Value=4
11 Solutions
Список значений можно найти с помощью findall:
Код:
List = ...,
findall(Val, f_prefix(List,_,Val),VList).
Ответить с цитированием
  (#3 (permalink)) Старый
malamut malamut вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.11.2007
По умолчанию 27.11.2007, 12:36

Большое спасибо. Сейчас абсолютно нет времени. Вечером поразвлекаемся с Prolog'ом ещё раз спасибо
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Функция MOD fredwriter Delphi 3 02.04.2010 10:53
Функция MOD или округлить fredwriter Pascal 3 24.03.2010 16:39
Функция типа Т9 как на сотовых.Есть ли прога для ПК чтоб была та же функция ? Технарь Софт и программы 11 14.03.2009 12:39
Префикс и суфикс как с ними работать fromrus Lisp 7 11.05.2008 22:50
Списки(префикс?Суфикс?) fromrus Prolog 7 04.05.2008 15:08
функция mail Sasyk PHP 1 29.11.2007 19:57
первый список - префикс второго azg Prolog 4 23.11.2007 03:00
Функция imported_KILLER Prolog 1 22.05.2006 14:21
функция rand Fearing С/С++ 3 11.08.2005 08:23
Create что это за функция -=VISUAL=- Visual C++ 10 28.07.2005 22:30
Функция задержки в C Thamior С/С++ 8 31.03.2005 11:43
математическая функция min PerpleXOR Visual Basic 3 19.04.2004 15:13



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов