Практическое занятие №4

Тема: Списки в Турбо-Пролог

Задание 1.

Для списка в листинге 5.1 number_list: а) Нарисовать линейный граф. Для упорядочивания элементов используйте стрелки. б) Нарисовать бинарный граф. Сколько узлов будет иметь это дерево ?

Задание 2.

Составьте список, элементами которого являются имена гномов из сказки "Белоснежка и семь гномов" (сколько вспомните). Какова длина получившегося списка ?

Задание 3.

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

Различаются ли с точки зрения Турбо-Пролога два таких списка:

 

[63,29,24,27,86]

[63,24,29,27,86]

 

Аргументируйте свой ответ.

Задание 4.

Можно ли назвать корректным следующий список ?

 

score(["Kennedy High School",6,3,8,9,6.2])

Задание 5.

 

Корректен ли список

 

symbols(["*","+","-","?","#","&"])

 

Если да, то почему ?

 

Листинг 5.1

/* Программа: Списки Файл: PROG0501.PRO */

/* Назначение: Работа со списками. */

 

domains

 

bird_list = bird_name *

bird_name = symbol

 

number_list = number *

number = integer

 

predicates

 

birds(bird_list)

score(number_list)

 

clauses

 

birds(["sparrow",

"robin",

"mockingbird",

"thunderbird",

"bald eagle"]).

 

score([56,87,63,89,91,62,85]).

 

/***** конец программы *****/

____________________________

Практическое занятие №5.

Тема: Использование метода с разделением списка на голову и хвост. Различные операции над списками.

Задание 1.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

 

[Head|Tail].

 

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка. (Для имен головы и хвоста списка пригодны любые допустимые Турбо-Прологом имена.)

Программа "Голова-хвост" (листинг 5.2) демонстрирует использования метода разделения списка. Два списка описаны в ней: список целых чисел (имя домена - number_list) и список символических имен (домен animal_list). Правило print_list

применяется для доступа к элементам обоих списков.

 

Изменить Листинг 5.2 и отладить эту программу в соответствии с заданием:

Для списка["Boston","Philadelphia","Seattle","Chicago"] напишите рекурсивное правило, которое печатает все элементы списка через два пробела.

 

 

_____________________________

Листинг 5.2

/* Программа: Голова-хвост Файл: PROG0502.PRO */

/* Назначение: Работа со списками путем */

/* деления на голову и хвост. */

 

domains

 

number_list = integer *

animal_list = symbol *

 

predicates

 

print_list(number_list)

print_list(animal_list)

 

clauses

 

print_list([]).

print_list([Head|Tail]) :-

write(Head),nl,

print_list(Tail).

 

/***** конец программы *****/

_____________________________

 

Программа "Голова-хвост" использует правило

 

print_list([]).

print_list([Head|Tail]) :-

write(Head),nl,

print_list(Tail).

 

Практическое занятие №6.

Тема: Поиск элемента в списке. Деление списков. Присоединение списка. Сортировка списков.

Программа "Элементы" (листинг 5.3) демонстрирует реализацию операции поиска элемента в списке. Поскольку предикат find_it определен как для списков целых чисел, так и для списков символических имен, то в данной программе он и работает со списками обоих типов.

____________________________

Листинг 5.3

/* Программа: Элементы Файл: PROG0503.PRO */

/* Назначение: Поиск нужного элемента в списке. */

 

domains

 

number_list = number *

number = integer

 

member_list = member *

member = symbol

 

predicates

 

find_it(number, number_list)

find_it(member, member_list)

 

clauses

 

find_it(Head, [Head|_]).

find_it(Head, [_|Tail]) :-

find_it(Head, Tail).

 

/***** конец программы *****/

____________________________

 

 

Изменить Листинг 5.3 и отладить эту программу в соответствии с заданием:

Если задать цель find_it(44,[11,22,33,44,11,22,33,44,11,22,33,44,55])

В скольких случаях будет достигнут успех ?

Отметим, что метод деления списка на голову и хвост используется в данном правиле как для разделения исходного списка, так и для формирования выходных списков.

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

то элементы списка и компаратор должны относиться к типу symbol.

Программа "Деление списка" (листинг 5.4) включает в себя только что приведенное правило. Попробуйте ввести такое целевое утверждение:

 

split(40,[30,50,20,25,65,95],L1,L2).

 

Результат работы программы с данной целью можно видеть

на рис. 5.8.

____________________________

Листниг 5.4

/* Программа: Деление списка Файл: PROG0504.PRO */

/* Назначение: Разделение списка на два. */

 

domains

 

middle = integer

list = integer *

 

predicates

 

split(middle,list,list,list)

 

clauses

 

split(Middle,[Head|Tail],[Head|L1],L2) :-

Head <= Middle,

split(Middle,Tail,L1,L2).

split(Middle,[Head|Tail],L1,[Head|L2]) :-

split(Middle,Tail,L1,L2),

Head > Middle.

split(_,[],[],[]).

 

/***** конец программы *****/

_____________________________

 

* Упражнение

 

5.12. Для программы "Деление списка"

 

а. Задайте внешнюю цель

 

split(12,[96,32,8,16,55,12],L1,L2).

 

Как будут выглядеть списки L1 и L2 ?

 

 

Практическое занятие №7.

Тема: Компоновка данных в список.

Задание 1.

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

Программа "Присоединение списка" (листинг 5.5) демонстрирует применение данного метода. В этой программе n_list является доменом списков целых чисел. Описание предиката для присоединения одного списка к другому записано в виде

 

append(n_list,n_list,n_list)

 

Раздел clauses содержит уже приведенные описания правил append. Внешней целью для программы может служить, скажем, ранее разобранный пример:

 

append([1,2,3],[4,5],L).

Запустите программу на счет с целевыми утверждениями

 

insert_sort([4,7,3,9],S).

 

и

 

insert_sort([7,6,5,4,3,2,1],S).

 

Задание 2.

Запустите программу "Сортировка списка". Введите цель

 

insert_sort([53,11,93,77,11],S).

 

Что получится ?

 

_____________________________

Листинг 5.5

/* Программа: Присоединение списка Файл: PROG0505.PRO */

/* Назначение: Слияние двух списков. */

 

domains

 

n_list = integer *

 

predicates

 

append(n_list,n_list,n_list)

 

clauses

 

append([],L,L).

append([N|L1], L2, [N|L3]) :-

append(L1,L2,L3).

 

/***** конец программы *****/

____________________________

 

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

определенно остается за сценой. Программисту нет необходимости специфицировать все эти действия.

Правила присоединения списка являются важным инструментом программирования. Способ работы этих правил на первых порах может несколько смутить Вас, поэтому стоит попрактиковаться при помощи приведенных ниже упражнениями.

 

Упражнение

 

5.13. Запустите программу "Присоединение списка" и введите целевое утверждение

 

append([9,15,3,60,55],[15,2,21],L).

Что получится ?

 

Программа "Сортировка списка" (листинг 5.6) реализует правило сортировки при помощи вставок для целочисленных списков. Программа работает в интерактивном режиме.

____________________________

Листинг 5.6

/* Программа: Coртировка списка Файл: PROG0506.PRO */

/* Назначение: Сортировка списка целых чисел. */

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

 

domains

 

number = integer

list = number *

 

predicates

 

insert_sort(list,list)

insert(number,list,list)

asc_order(number,number)

 

clauses

 

insert_sort([],[]).

insert_sort([X|Tail],Sorted_list) :-

insert_sort(Tail,Sorted_Tail),

insert(X,Sorted_Tail,Sorted_list).

 

insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :-

asc_order(X,Y), !,

insert(X,Sorted_list,Sorted_list1).

insert(X,Sorted_list,[X|Sorted_list]).

 

asc_order(X,Y) :- X>Y.

 

/***** конец программы *****/

____________________________