Списки

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

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

[10,24,1,8,385,0,8]

[0.4,67.43,986.01,914.5]

["ПЕТРОВ П.Р.","ИВАНОВ Б.О.","СИДОРОВ Т.К."]

Список может содержать произвольное число элементов (ограничением является объем доступной оперативной памяти). Список, не содержащий элементов, называется пустым списком и обозначается []. Обработка списков в Турбо-Прологе базируется на разбиении списка на голову - первый элемент в списке и хвост - остальную часть списка. Например, как показано в следующей таблице:

Список	Голова	Хвост
[1,2,3,4]	1	[2,3,4]
['а'.'b'.'с']	'а'	['bYc'l
["Курсант"]	"Курсант"	[ ]
[]	не определено	не определено

Наглядным представлением процесса разбиения списка на голову и хвост является графическое представление в виде бинарного (двоичного) дерева. Для списка [1,2,3,4] таким деревом будет следующее:

Для использования списков в Пролог-программе необходимо:

1) В разделе domains описать домен списка. Домен списка задается в формате:

= *

319

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

domains

list_num=integer*

или

list_num=elem*

elem= Integer

2) Описать работающий со списком предикат в разделе predicates, например:

predicates

num(list_num)

3) Ввести или создать в программе собственно список, т.е. задать список в разделах

goal или clauses.

Пример задания списков в Пролог-программе:

domains

Iist1=symbol*

Iist2=num*

num=integer

predicates

name(list1)

score(list2)

clauses

name(["ПЕТРОВ П.Р.","ИВАНОВ Б.О.","СИДОРОВ Т.К."]).

score([1,3,5,7,9]).

Ниже приведены примеры внешних запросов к программе и получаемые при этом результаты:

Запрос	Результат
nате(Х)	Х= ["Петров П. Р.", "Иванов Б. О.", "Сидоров Т. К."].
name([_, Y, _])	Y="Иванов Б. О."
score([A,B,_,_,C])	A=1,B=3,C=9

При использовании в Пролог-программе списков с произвольным числом элементов используется метод разделения списка на голову и хвост. Этот метод обеспечивает рекурсивную обработку списка. Операция разделения списка на голову и хвост в языке Турбо-Пролог обозначается вертикальной чертой (|) и записывается в виде:

[Head | Tail]

Здесь: Head - переменная для обозначения головы списка; Tail - переменная для обозначения хвоста списка.

Пример 1. Рассмотрим программу распечатки содержимого списка, элементы которого могут быть целыми числами или символьными строками:

domains

Iist1=integer*

320

Iist2=symbol*

predicates

printjist(listl)

print_list(list2)

clauses

print_list([]).

print_list([Head|Tail]):-write(Head),

nl,

print_list(Tail).

goal

print_list([1,2,3,4]).

В данной программе предикат списка print_list() описан для двух типов доменов, поэтому с его помощью могут обрабатываться списки, элементами которых являются как целые числа, так и символьные строки. В программе реализован рекурсивный метод обработки.

Первое правило программы print_list([]) описывает тот факт, что пустой список не нужно печатать, оно же является условием выхода из рекурсии, используемым во втором правиле - печать списка завершается тогда, когда список пуст. Опишем работу программы.

Первоначально аргумент целевого внутреннего запроса printjist([1,2,3,4]) сопоставляется с первым вариантом правила; сопоставление терпит неуспех, так как [1,2,3,4]#[]. Затем выбирается второй вариант правила, здесь сопоставление завершается успехом и выполняется операция - разделения целевого списка на голову и хвост. Результатом ее является означение Head=1 и Tail=[2,3,4]. Далее начинают последовательно выполняться предикаты тела правила.

Первым в теле стоит стандартный предикат write(Head), который выводит на экран значение переменной Head, в данном случае 1, затем выполняется предикат nl - перевод строки и формируется рекурсивный вызов print_list([2,3,4]). Снова обращение к первому варианту правила и снова неуспех - [2,3,4]#[], и снова успешное сопоставление со вторым вариантом и т.д. В конечном итоге переменная Head становится равной 4, a Tail=[], и теперь после рекурсивного вызова printjist([]) сопоставление для первого варианта правила завершится успехом - []=[], этот вариант правила не имеет рекурсии - он является фактом и интерпретируется Прологом как цель достигнута и целевой запрос считается удовлетворенным.

Пример 2. Рассмотрим Пролог-программу подсчета суммы произведений элементов двух векторов X и Y, представленных списками Х=[х1 ,х2,.. .хn] и Y=[y1 ,у2 ,.. ,уn]:

domains

vector=integer*

predicates

prod(vector, vector, integer)

clauses

prod([],[],0).

prod([X|Xs],[Y|Ys],S):-prod(Xs,Ys,Sp),

321

S=X*Y+Sp.

goal

prod([1,2,3],[7,8,9],Rest),white("Rest=",Res).

Предикат prod (...) является трехместным: первый аргумент - список X, второй - список Y и третий - сумма произведений списков. В разделе clauses описаны два варианта правила для этого предиката.

Первый вариант - утверждение о том, что сумма произведений элементов пустых списков равна 0. Второй вариант правила реализован с использованием хвостовой рекурсии. Выражение S=X*Y+Sp означает, что текущая сумма равна сумме произведений текущих элементов вектора и частичной суммы, полученной на предыдущих шагах вычислений.

Схематично действия при выполнении программы представлены в табл. 24.2. Рекурсивное правило описывает отсроченные вычисления - после рекурсивного вызова остается не выполненным хвост правила, копии которого помещаются в стек до тех пор, пока не произойдет сопоставление с первым вариантом правила. И после того, как это произойдет, частичная сумма Sp" получит значение 0 и все накопленные в стеке хвостовые вычисления будут выполнены в обратном порядке.

Таблица 24.2

Действия при выполнении программы

Вызов предиката	Подстановки	Хвостовые вычисления	Результаты вычислений
Prod([1, 2,3], [7,8,9], Res)	X=1, Y=7, Xs=[2,3], Ys=[8,9], Res=S	S=X*Y+Sp	S=1*7+43=50
Prod([2,3],[8,9],Sp)	X'=2, Y'=8, Xs'=[3], Ys'=[9], S=Sp	Sp=X'*Y'+Sp'	Sp=2*8+27=43
Prod([3],[9],Sp')	X"=3, Y"=9, Xs"=[], Ys"=[], Sp=Sp'	Sp'=X"*Y"+Sp"	Sp'=3*9+0=27
Prod([],[],Sp")	Xs"=[],Ys"=[], Sp"=0		Sp"=0

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

domains

Sp1, Sp= integer*

P, U, Z, Z1, N1, N, N2, X, F, P1, Q = integer

predicates

edit_list window(Sp, P) view_list(Sp)

make_list(Sp) delete_list(Sp)

process(X,Sp,P) insert_sort(Sp,Sp)

322

attent_windowcreate(N,Sp,Z)

list(Sp,integer) insert(integer,Sp,Sp) inversion(Sp,Sp)

split(integer,integer,Sp,Sp,Sp)connect(Sp,Sp,Sp)

add_list(Sp) goto(Sp,integer) prt(char,Sp)

qrt(char,Sp) delete(integer,Sp) sound1 sound2

goal

edit_list.

clauses

/*------------------------------------ОСНОВНОЕ МЕНЮ------------------------------------*/

edit_list:-window([],0).

window(Sp,P):-makewindow(1,31)7l"MEHЮ

РЕДАКТОРА",0, 0, 25, 80), cursor(5,15),

write(" СОЗДАНИЕ СПИСКА -1 "),cursor(7,15),

write(" ПPOCMOTP СОДЕРЖИМОГО СПИСКА - 2"),cursor(9,15),

write("КОНКАТЕНАЦИЯ СПИСКА И ЭЛЕМЕНТА - 3"),cursor(11,15),

write("УДАЛЕНИЕ - 4"),cursor( 13,15),

write("УПОРЯДОЧИВАНИЕ СПИСКА ПО ВОЗВРАСТАНИЮ-5"),cursor(15,15),

write("BЫХОД ИЗ РЕДАКТОРА - 6"),cursor(20,10),

write("Введите номер пункта меню:"),sound1,

readint(X),sound(8, 2000), X

process(1 ,Sp,0):-make_list(Sp).

process(1,Sp,1):-make_list([]).

process(4,Sp,0):-attent_window,window(Sp,0).

process(4,Sp,1):-delete_list(Sp).

process(2,Sp,0):-attent_window,window(Sp,0).

process(2,Sp,1):-view_list(Sp).

process(3,Sp,0):-add_list(Sp).

process(3,Sp,1 ):-add_list(Sp).

process(5,Sp,0):-attent_window,window(Sp,0).

process(5,Sp,1):-insert_sort(Sp,Sp1),view_list(Sp1).

process(6,Sp, 1 ):-sound2, exit. process(6,Sp,0):-sound2, exit.

/*------------------------------------СОЗДАНИЕ СПИСКА---------------------------------*/

make_list(Sp):-makewindow(2,48,7," СОЗДАНИЕ СПИСКА",5,5,15,70),

gotowindow(2),cursor(3,8),

write("Количество элементов в списке - "),readint(N),

sound(8,2000),cursor(5,8),

write(" Введите элементы списка: "),Z=1,Sp=[],create(N,Sp,Z).

create(0,Sp,Z):-inversion(Sp,[]).create(N,Sp,Z):-

write(" # ",Z,"-"),readint(U),sound(8,3000),scroll(1,0),cursor(5,32),

N1 =N-1, Z1 =Z+1 ,create(N1 ,[U | Sp],Z1).

inversion([],Sp1 ):-window(Sp1,1).

inversion([H|T],Sp):-inversion(T,[H|Sp]).

323

/*---------------- ОКНО ПРЕДУПРЕЖДЕНИЯ ----------- */

attent_window:-akewindow(3, 64,7, "BHИMAHИE",10,25,5,30),gotowindow(3),nl,

write(" Ваш список пустой !"),sound(50,1 000), readchar(L).

/*-------------------------УДАЛЕНИЕ ---------------------*/

delete_list(Sp):-makewindow(8,48,7,"УДAЛEHИE",5,15,15, 45), gotowindow(8)l

write(""),nl,

write(" СПИСКА - 1 "),nl,

write(" ЭЛЕМЕНТА В СПИСКЕ - 2 "),nl, cursor(7,5),readint(N),delete(N, Sp).

delete(1, Sp):-makewindow(9, 64, 7,"", 10, 23, 5, 30), gotowindow(9),nl,

write("CПИCOK УДAЛEH!"), sound1, readchar(U),window([], 0).

delete(2,Sp):-makewindow(4, 48, 7, " УДАЛЕНИЕ ЭЛЕМЕНТА", 10, 15, 5,45),

gotowindow(4),nl,

write(" Введите номер удаляемого элемента: "),readint(S),N=0,

split(S,N,Sp,Sp1,[H|T]),connect(Sp1,T,Sp3),view_list(Sp3).

split(S, N,[H|T],[H|L1],L2):-N1=N+1,N1

split(S,N, [H|T],L1,[H|L2]):-N1=N+1,split(S,N1,T,L1,L2),N1>=S.

connect([],L,L).

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

/*------------------- ПРОСМОТР СОДЕРЖИМОГО СПИСКА --------- */

view_list(Sp):-makewindow(5,48,7,"COДEPЖИMOE СПИСКА",5, 1 5, 1 5,45),

gotowindow(5),cursor(10,5),list(Sp,1),readchar(L),window(Sp,1).

list([], N).

list(T,7):-readchar(L),scroll(1 ,0),cursor( 10,5),list(T, 1 ).

list([H|T],N):-N1=N+1,N2=N1*6,write(H), sound(10,3000),

cursor(10,N2),list(T,N1),!.

/* ------- УПОРЯДОЧИВАНИЕ ЭЛЕМЕНТОВ ПО ВОЗРАСТАНИЮ-----------*/

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]):-X>Y,!,

insert(X,Sorted_list,Sorted_list1).

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

/* ----------- ДОБАВЛЕНИЕ ЭЛЕМЕНТА К СПИСКУ -------- */

add_list(Sр):-makewindow(6,48,7,"ДОБАВЛЕНИЕ К СПИСКУ",5, 15, 15,45),

gotowindow(6), cursor(3,5),

write("B НАЧАЛО СПИСКА - 1 "),cursor(5,5),

write("B КОНЕЦ СПИСКА - 2"),cursor(7,5),

readint(L),sound(8,2000),L

goto(Sp, 1 ):-makewindow(7,48,7, "ДOБABЛEHИE К СПИСКУ",5, 15, 15,45),

gotowindow(7),cursor(5,5),

write("BBEДИTE НОВЫЙ ЭЛЕМЕНТ: "),cursor(5,28),

readint(X),sound(8,3000),connect([X],Sp,Sp1),cursor(7,5),

324

write (" ЕЩЕ - ? < y/n > "),readchar(Z),sound(8, 2000),qrt(Z,Sp1).

goto(Sp,2):-makewindow(8,48, 7,"ДOБABЛEHИEKCПИCKУ", 5, 15,15,45),

gotowindow(8),cursor(5,5),

write("BBEДИTE НОВЫЙ ЭЛЕМЕНТ: "),cursor(5,28),

readint(X), sound(8,3000),connect(Sp,[X], Sp1),cursor(7,5),

write("ЕЩЕ - ? < y/n > "),readchar(Z),sound(8,2000),prt(Z,Sp1).

prt('y',Sp1):-goto(Sp1,2).

prt('n',Sp1 ):-view_list(Sp1).

qrt('y',Sp1):-goto(Sp1,1).

qrt('n',Sp1 ):-view_list(Sp1).

/*------------------------------------------------------------------------------------*/

soundl :-sound(15,1000),sound(15,1500),sound(15,2000).

sound2:-sound(15,2000),sound(15,1500),sound(15,1000).

325

319 :: 320 :: 321 :: 322 :: 323 :: 324 :: 325 :: Содержание

Содержание раздела