Деревья

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

DOMAINS

tree=empty;tr(i,tree,tree)

/* дерево либо пусто, либо

состоит из корня (целого числа),

левого и правого поддеревьев,

также являющихся деревьями */

Пример. Предикат будет проверять принадлежность значения дереву . Предикат будет иметь два аргумента. Первым аргументом будет исходное значение, вторым - дерево, в котором мы ищем данное значение.

tree_member(X,tr(X,_,_)):-!. /* X - является корнем

дерева */

tree_member(X,tr(_,L,_)):-

tree_member(X,L),!. /* X принадлежит

левому поддереву */

tree_member(X,tr(_,_,R)):-

tree_member(X,R). /* X принадлежит

правому поддереву */

Пример. Предикат, который будет заменять в дереве все вхождения одного значения на другое. У предиката будет четыре аргумента: три входных (значение, которое нужно заменять; значение, которым нужно заменять; исходное дерево ), четвертым - выходным - аргументом будет дерево, полученное в результате замены всех вхождений первого значения на второе.

tree_replace(_,_,empty,empty). /* пустое дерево

остается пустым деревом*/

tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):-

/* корень содержит заменяемое

значение X*/

!,tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):-

/* корень не содержит

заменяемое значение X */

tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

Пример. Предикат, подсчитывающий общее количество вершин дерева . У него будет два параметра. Первый (входной) параметр - дерево , второй (выходной) - количество вершин в дереве.

tree_length (empty,0). /* В пустом дереве

нет вершин */

tree_length(tr(_,L,R),N):-

tree_length (L,N1),

/* N1 - число вершин

левого поддерева */

tree_length (R,N2),

/* N2 - число вершин

правого поддерева */

N=N1+N2+1. /* число вершин

исходного дерева

получается сложением

N1, N2 и единицы */

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

tree_leaves(empty,0). /* в пустом дереве

листьев нет */

tree_leaves(tr(_,empty,empty),1):-!.

/* в дереве с одним корнем -

один лист */

tree_leaves(tr(_,L,R),N):-

tree_leaves(L,N1),

/* N1 - количество листьев

в левом поддереве */

tree_leaves(R,N2),

/* N2 - количество листьев

в правом поддереве */

N=N1+N2.

Пример. Создадим предикат, находящий сумму чисел, расположенных в вершинах дерева . Он будет иметь два аргумента. Первый - исходный список, второй - сумма чисел, находящихся в вершинах дерева , расположенного в первом аргументе.

tree_sum (empty,0). /* В пустом дереве

вершин нет */

tree_sum(tr(X,L,R),N):-

tree_sum (L,N1),

/* N1 - сумма элементов

левого поддерева */

tree_sum (R,N2),

/* N2 - сумма элементов

правого поддерева */

N=N1+N2+X. /* складываем N1, N2

и корневое значение */

Пример. Создадим предикат, позволяющий вычислить высоту дерева . Напомним, что высота дерева - это наибольшая длина пути от корня дерева до его листа . Предикат будет иметь два параметра. Первый (входной) - дерево , второй (выходной) - высота дерева , помещенного в первый параметр.

tree_height(empty,0). /* Высота пустого

дерева равна нулю */

tree_height(tr(_,L,R),D) :-

tree_height(L,D1),

/* D1 - высота левого

поддерева */

tree_height(R,D2),

/* D2 - высота правого

поддерева */

max(D1,D2,D_M),

/* D_M - максимум из высот

левого и правого поддеревьев */

D=D_M+1.

/* D - высота дерева получается

путем увеличения числа D_M

на единицу*/

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

Предикат для проверки значения принадлежащего двоичному справочнику.

tree_member2(X,tr(X,_,_)):-!. /* X - корень

дерева */

tree_member2(X,tr(K,L,_)):-

X<K,!,

tree_member2(X,L).

/* X - принадлежит

левому поддереву */

tree_member2(X,tr(K,_,R)):-

X>K,!,

tree_member2(X,R).

/* X - принадлежит

правому поддереву */

Предикат добавляющий в двоичный справочник новое значение.

tree_insert(X,empty,tr(X,empty,empty)).

/* вставляем X в пустое дерево,

получаем дерево с X в корневой

вершине,пустыми левым и

правым поддеревьями */

tree_insert(X,tr(X,L,R),tr(X,L,R)):-!.

/* вставляем X в дерево

со значением X в корневой

вершине, оставляем исходное

дерево без изменений */

tree_insert(X,tr(K,L,R),tr(K,L1,R)):-

X<K,!,

tree_insert(X,L,L1).

/* вставляем X в дерево

с большим X элементом в

корневой вершине, значит,

нужно вставить X в левое

поддерево исходногодерева */

tree_insert(X,tr(K,L,R),tr(K,L,R1)):-

tree_insert(X,R,R1).

/* вставляем X в дерево

с меньшим X элементом

в корневой вершине, значит,

нужно вставить X в правое

поддерево исходного дерева */

Предикат генерирующий дерево, являющееся двоичным справочником и состоящее из заданного количества вершин в которых размещаются случайные целые числа.

tree_gen(0,empty):-!. /* ноль вершин

соответствует пустому дереву */

tree_gen (N,T):-

random(100,X),

/* X - случайное число

из промежутка [0,100) */

N1= N-1,

tree_gen (N1,T1),

/* T1 - дерево, имеющее

N-1 вершин */

tree_insert(X,T1,T). /* вставляем X

в дерево T1 */

Дерево не обязательно будет иметь столько вершин сколько указано в этом параметре, т.к. будут одни и те же числа. Если нужно получить содержащее ровно столько вершин, сколько указано, нужно модифицировать рассмотренный предикат, например, в случае когда вставляемое значение совпало с корневым генерировать новое случайное число для вставки в дерево.

Предикат удаляющий заданное значение из двоичного справочника. Опишем вспомогательный предикат удаляющий минимальный элемент двоичного справочника.

tree_del_min(tr(X,empty,R), R, X).

/* Если левое поддерево пусто,

то минимальный элемент - корень,

а дерево без минимального

элемента - это правое поддерево.*/

tree_del_min(tr(K,L,R), tr(K,L1,R), X):-

tree_del_min(L, L1, X).

/* Левое поддерево не пусто,

значит, оно содержит минимальное

значениевсего дерева,

которое нужно удалить */

tree_delete(X,tr(X,empty,R), R):-!.

/* X совпадает с корневым

значением исходного дерева,

левое поддерево пусто */

tree_delete (X,tr(X,L,empty), L):-!.

/* X совпадает с корневым

значением исходного дерева,

правое поддерево пусто */

tree_delete (X,tr(X,L,R), tr(Y,L,R1)):-

tree_del_min(R,R1, Y).

/* X совпадает с корневым

значением исходного

дерева, причем ни левое, ни

правое поддеревья не пусты */

tree_delete (X,tr(K,L,R), tr(K,L1,R)):-

X<K,!,

tree_delete (X,L,L1).

/* X меньше корневого значения

дерева */

tree_delete (X,tr(K,L,R), tr(K,L,R1)):-

tree_delete (X,R,R1).

/* X больше корневого значения

дерева */

Предикат, преобразующий произвольный список в двоичный справочник.

list_tree([],empty). /* Пустому списку

соответствует пустое дерево */

list_tree([H|T],Tr):-

list_tree(T,Tr1),

/* Tr1 - дерево, построенное

из элементов хвоста

исходного списка */

tree_insert(H,Tr1,Tr).

/* Tr - дерево, полученное

в результате вставки

головы списка в дерево Tr1 */

Предикат, преобразующий двоичный справочник в список.

tree_list(empty,[]). /* Пустому дереву

соответствует пустой список */

tree_list(tr(K,L,R),S):-

tree_list(L,T_L),

/* T_L - список,

построенный из элементов

левого поддерева */

tree_list(R,T_R),

/* T_L - список,

построенный из элементов

правого поддерева */

conc(T_L,[K|T_R],S).

/* S - список, полученный

соединением списков T_L

и [K|T_R] */

Сортировка списка.

sort_listT(L,L_S):-

list_tree(L,T),

/* T- двоичный справочник,

построенный из элементов

исходного списка L */

tree_list(T,L_S).

/* L_S - список, построенный из

элементов двоичного

справочника T */

Так как в двоичном справочнике все элементы различны, при переписывании списка в двоичный справочник и обратно повторяющиеся элементы будут из него удалены. Неизменным останется количество элементов списка, только если все его элементы были различны.

Строки

str_len – определение длины строки. Аргументы – строка, количество символов.

concat – соединение двух строк. Аргументы – строка1, строка2, результат.

frontchar – для разделение исходной строки а первый символ и хвост из оставшихся символов строки.

frontstr - аналогичен предыдущему, только позволяет отделить не один, а указанное количество символов. Аргументы – количество символов, которые копируются из второго параметра в третий, а в четвертый помещается остаток от второго параметра.

fronttoken – выделяет первый атом, входящий в строку. Атом это или идентификатор, или без знаковое число или символ.

isname – истинен, если его строковый аргумент является идентификатором и ложен в противном случае.

Предикат, который преобразует строку в список символов. Предикат будет иметь два аргумента. Первым аргументом будет данная строка, вторым — список, состоящий из символов исходной строки.

str_list("",[]). /* пустой строке соответствует

пустой список */

str_list(S,[H|T]):–

frontchar(S,H,S1),

/* H — первый символ строки S,

S1 — остаток строки */

str_list(S1,T).

/* T — список, состоящий

из символов, входящих

в строку S1*/

Предикат, преобразующий строку в список атомов:

str_a_list("",[]). /* пустой строке по-прежнему

соответствует пустой список */

str_a_list(S,[H|T]):–

fronttoken(S,H,S1),

/* H — первый атом строки S,

S1 — остаток строки */

str_a_list(S1,T).

/* T — список, состоящий

из атомов, входящих

в строку S1*/

Предикат преобразует список символов в строку. Предикат будет иметь два аргумента. Первым аргументом будет список символов, вторым — строка, образованная из элементов списка.

list_str([],""). /* пустой строке соответствует

пустой список */

list_str([H|T],S):–

list_str(T,S1),

/* S1 — строка, образованная

элементами списка T */

frontchar(S,H,S1).

/* S — строка, полученная

дописыванием строки S1

к первому элементу списка H */

Создадим предикат, который по строке и символу подсчитает количество вхождений этого символа в данную строку. Предикат будет иметь три аргумента: первые два — входные (строка и символ), третий — выходной (количество вхождений второго аргумента в первый).

char_count("",_,0). /* Любой символ не встречается

в пустой строке ни разу*/

char_count(S,C,N):–

frontchar(S,C,S1),!,

/* символ C оказался первым символом

строки S, в S1 — оставшиеся

символы строки S */

char_count(S1,C,N1),

/* N1 — количество вхождений

символа C в строку S1 */

N=N1+1.

/* N — количество вхождений

символа C в строку S получается

из количества вхождений символа C

в строку S1 добавлением единицы */

char_count(S,C,N):–

frontchar(S,_,S1),

/* первым символом строки S

оказался символ, отличный

от исходного символа C, в S1 —

оставшиеся символы строки S */

char_count(S1,C,N).

/* в этом случае количество

вхождений символа C в строку S

совпадает с количеством

вхождений символа C

в строку S1 */

Предикат, который по символу и строке возвращает первую позицию вхождения символа в строку, если символ входит в строку и 0, если не входит. Первые два — входные — символ и строка, третий — выходной — первая позиция вхождения первого параметра во второй параметр или ноль.

str_pos(C,S,1):–

frontchar(S,C,_),!.

/* Искомый символ C оказался первым

символом данной строки S */

str_pos(C,S,N) :–

frontchar(S,_,S1),

/* S1 — состоит из всех символов

строки S, кроме первого, который

отличается от искомого символа C */

str_pos(C,S1,N1),

/* N1 — это позиция, в которой

символ C встречается первый раз

в хвосте S1 или ноль*/

N1<>0,!, /* если позиция вхождения

символа C в строку S1 не равна

нулю, то есть если он встречается

в строке S1, /

N=N1+1. /* то, увеличив позицию его

вхождения на единицу, мы получим

позицию его вхождения в исходную

строку */

str_pos(_,_,0). /* искомый символ не входит в данную

строку */

Предикат, который заменяет все вхождения одного символа на другой символ. У предиката будет четыре параметра. Первые три — входные (исходная строка; символ, вхождения которого нужно заменять; символ, которым нужно заменять первый символ); четвертым — выходным — параметром должен быть результат замены в первом параметре всех вхождений второго параметра на третий параметр.

str_replace("",_,_,""):–!. /* из пустой строки можно

получить только пустую

строку */

str_replace(S,C,C1,SO):–

frontchar(S,C,S1),!,

/* заменяемый символ C оказался

первым символом строки S,

S1 — остаток строки S */

str_replace(S1,C,C1,S2),

/* S2 — результат замены

в строке S1 всех вхождений

символа C на символ C1 */

frontchar(SO,C1,S2).

/* SO — результат склейки

символа C1 и строки S2 */

str_replace(S,C,C1,SO):–

frontchar(S,C2,S1),

/* разделяем исходную строку S

на первый символ C2

и строку S2, образованную

всеми символами строки S,

кроме первого */

str_replace(S1,C,C1,S2),

/* S2 — результат замены

в строке S1 всех вхождений

символа C на символ C1 */

frontchar(SO,C1,S2).

/* SO — результат соединения

символа C1 и строки S2 */

Предикат, который удаляет часть строки. Предикат будет иметь четыре параметра. Первые три входные: первый — исходная строка, второй — позиция, начиная с которой нужно удалять символы, третий — количество удаляемых символов. Четвертым — выходным — параметром будет результат удаления из строки, указанной в первом параметре, символов, в количестве, указанном в третьем параметре, начиная с позиции, указанной во втором параметре.

str_delete(S,I,C,SO) :–

I1=I–1, /* I1 — количество символов,

которые должны остаться

в начале строки S */

frontstr(I1,S,S1,S2),

/* S1 — первые I1 символов

строки S, S2 — символы

строки S, с I —го

до последнего */

frontstr(C,S2,_,S3),

/* S3 — последние символы

строки S2 или, что тоже

самое, последние символы

строки S */

concat(S1,S3,SO).

/* SO — строка, полученная

соединением строк S1 и S3 */

Предикат, который копирует часть строки. Предикат будет иметь четыре параметра. Первые три входные: первый — исходная строка, второй — позиция, начиная с которой нужно копировать символы, третий — количество копируемых символов. Четвертым — выходным — параметром будет результат копирования символов из строки, указанной в первом параметре, в количестве, указанном в третьем параметре, начиная с позиции, указанной во втором параметре.

str_copy(S,I,C,SO) :–

I1=I–1, /* I1 — это количество

символов, расположенных

в начале строки S, которые

не нужно копировать */

frontstr(I1,S,_,S1),

/* S1 — строка, состоящая

из всех символов строки S,

с I-го и до последнего */

frontstr(C,S1,SO,_).

/* SO — первые C символов

строки S1 */

Предикат, позволяющий вставить одну строку в другую. Предикат будет иметь четыре параметра. Первые три входные: первый — вставляемая строка; второй — строка, в которую нужно вставить первый аргумент; третий — позиция, начиная с которой нужно вставить первый параметр во второй. Четвертым — выходным — параметром будет результат вставки строки, указанной в первом параметре, в строку, указанную во втором параметре, начиная с позиции, указанной в третьем параметре.

str_insert(S,S1,I,SO) :–

I1=I–1, /* I1 — это количество

символов, расположенных

в начале строки S, после

которых нужно вставить новые

символы */

frontstr(I1,S1,S1_1,S1_2),

/* S1_1 — первые I1 символов

строки S1, S1_2 — остаток

строки S1, с I —го и до

последнего */

concat(S1_1,S,S2),

/* S2 — строка, полученная

объединением строк S1_1

и S */

concat(S2,S1_2,SO).

/* SO — строка, полученная

слиянием строк S2 и S1_2 */

Предикат подсчитывающий количество цифр в строке. Предикат будет иметь всего два аргумента. Входным аргументом будет строка, количество цифр в которой нужно подсчитать, выходным аргументом будет количество цифр в первом аргументе.

dig(C,1):–

‘0’<=C,C<=’9’,!. /* C — цифра*/

dig(_,0).

count_digit("",0):–!. /* В пустой строке цифр нет */

count_digit(S,N):–

frontchar(S,C,S2),

/* C — первый символ строки S,

S2 — хвост строки S */

dig(C,M), /* M равен единице, если C —

цифра, и нулю — иначе */

count_digit(S2,N2),

/* N2 — количество цифр

в строке S2*/

N=N2+M. /* Количество цифр во всей

строке больше на единицу,

чем количество цифр

в хвосте, если первый символ

строки — цифра, и равно

количеству цифр в хвосте —

иначе */

Файлы

Файлом называют именованную совокупность данных, записанных на диске. Файл состоит из компонентов. При чтении или записи файловая переменная перемещается по очередному компоненту и делает его доступным для обработки. В Прологе пользовательские файлы описываются в разделе описания доменов следующим образом:

file = <символическое имя файла1>;...;

<символическое имя файлаN>

Символические имена файлов называют внутренними или логическими именами в отличие от внешних или физических имен файлов. Символическое имя файла должно начинаться со строчной буквы. Кроме пользовательских файлов имеются стандартные файлы, которые не нужно описывать в разделе описания доменов.

Это:

• stdin(стандартное устройство ввода);
• stdout(стандартное устройство вывода);
• stderror(стандартное устройство вывода сообщений об ошибках);
• keyboard(клавиатура);
• screen(монитор);
• printer(параллельный порт принтера);
• coml(последовательный порт).

По умолчанию стандартным устройством ввода является клавиатура, а вывода – монитор. Чтобы начать работу с пользовательским файлом, его нужно открыть, а по завершении работы закрыть. Стандартное устройство открывать и закрывать не нужно. Встроенные предикаты для работы с файлами:

openread – открывает только для чтения.
openwrite – только для записи.
openappend – запись в конец файла
openmodify – чтение и запись одновременно
existfile – истинен если файл с указанным именем существует

“C:\\Prolog\\BIN”

closefile – закрытие файла
renamefile – переименовать файл
deletefile – удалить файл
disk – задает текущий диск или каталог
dir – выбор из списка файлов
eof – истинен если достигнут конец файла
filepos – текущая позиция чтения или записи в файле или изменить её. Первый аргумент символическое имя, второй – позиция внутри файла, третий - номер режима, который задает откуда отсчитывается позиция (0 – начало, 1 – текущая, 3 - конец)
readdevice – используется для переопределения текущего устройства ввода или чтобы узнать, какое устройство является текущим.
writedevice – используется для переопределения текущего устройства вывода или для получения имени текущего устройства вывода.
write – предикат для записи данных в текущее устройство
readln – чтение строки и з текущего устройства
readint – читает целое число

readreal - читает вещественное число

readchar – читает символ

readterm – читает терм
file_str – читает символы файла в строку или, наоборот, записывает содержимое строки в файл, в зависимости от того, свободен ли второй параметр этого предиката
flush – используется для принудительной записи в файл содержимого внутреннего буфера, выделенного для файла, указанного в его единственном параметре
filemode – задает режим доступа к файлу(0 – бинарный режим, 1 - текстовый)

Пример. Предикат, выводящий содержимое произвольного файла на экран. Параметр – внешнее дисковое имя файла.

DOMAINS /* раздел описания доменов */

file = f /* f — внутреннее имя файла */

PREDICATES /* раздел описания предикатов */

write_file(file)

writeFile(string)

CLAUSES /* раздел описания предложений */

write_file(f):–

not(eof(f)),!, /* если файл f еще

не закончился */

readchar(C), /* читаем из него символ */

write(C," "), /* выводим символ на экран*/

write_file(f). /* продолжаем процесс */

write_file(_). /* это предложение нужно, чтобы предикат

не потерпел неудачу в случае, когда

будет достигнут конец файла */

writeFile(F_N):–

existfile(F_N),!, /* убеждаемся в существовании

файла с именем F_N */

openread(f,F_N), /* связываем внешний файл F_N

с внутренним файлом f

и открываем его на чтение */

readdevice(f), /* устанавливаем в качестве

устройства чтения файл f */

write_file(f), /* вызываем предикат, выводящий

на экран все символы

файла f */

closefile(f), /* закрываем файл */

readdevice(keyboard), /* перенаправляем ввод

на клавиатуру */

nl,nl, /* пропускаем строку */

write("Нажмите любую клавишу"),

/* выводим сообщение на экран */

readchar(_)./* ждем нажатия любой клавиши */

writeFile(F_N):–

write("Файл с именем ",F_N," не наден!").

/* выдаем сообщение, если предикат

existfile потерпел неудачу */

GOAL /* раздел описания внутренней цели*/

write("Введите имя файла: "),

readln(F_N), /* читаем название файла в переменную F_N */

writeFile(F_N).

Пример. Формирование файла из символов с клавиатуры.

DOMAINS

file=f

PREDICATES

Readfile

CLAUSES

readfile:–

writedevice(screen), /* назначаем текущим

устройством записи

экран */

write("Введите символ (# — конец ввода)"), nl,

/* выводим сообщение */

readchar(C), /* читаем символ с клавиатуры */

write(C), /* дублируем символ на экран */

C<>'#',!, /* если это не #*/

writedevice(f), /* , то перенаправляем вывод

в файл */

write(C), /* записываем символ в файл */

readfile.

readfile:–

closefile(f). /* если введенный символ оказался

равен символу '#', то закрываем файл */

GOAL

write("Введите имя файла: "),

readln(F_N),

/* читаем название файла в переменную F_N */

openwrite(f,F_N), /* связываем внешний файл F_N

с внутренним файлом f и открываем

его на запись */

readfile(f).

Пример. Предикат, который переписывает один файл в другой так, чтобы в другом файле все английские буквы были большими.

transform:–

not(eof(f)),!, /* если файл f еще

не закончился */

readln(S), /* читаем из файла f строку

в переменную S */

upper_lower(S_U,S),

/* S_U — результат преобразования

всех символов строки S в верхний

егистр */

write(S_U),nl, /* записываем строку S_U

в файл f_o */

transform. /* продолжаем процесс */

transform:–

closefile(f), /* закрываем файл f */

closefile(f_o). /* закрываем файл f_o */

upper_file(N_F,N_o_F):–

existfile(N_F),!, /* проверяем существование

файла с именем N_F */

openread(f,N_F), /* связываем внешний файл

с именем N_F с внутренним

файлом f и открываем его

на чтение */

readdevice(f), /* устанавливаем в качестве

текущего устройства чтения

файл f */

openwrite(f_o,N_o_F),

/* связываем внешний файл с именем

N_o_F с внутренним файлом f

и открываем его на запись */

writedevice(f_o), /* устанавливаем в качестве

текущего устройства записи

файл f_o */

transform. /* вызываем вспомогательный

предикат */

upper_file(N_F,_):–

write("Файл с именем ",N_F," не найден!").

/* выдаем сообщение, если предикат

existfile был неуспешен */