Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

"Комсомольский-на-Амуре государственный технический университет"

Факультет компьютерных технологий

Кафедра МОП ЭВМ

По дисциплине: "Функциональное и логическое программирование"

Студент группы 0ВТ3к-1

Коновалова. К.А.

Преподаватель Абарникова Е.Б.

2012

Задание 1

Тема: списки и бинарные деревья.

Цель: изучить основные операции работы со списком.

Задание: написать программу реализующую:

1) удаление элемента из списка перед указанным элементом.

2) сортировку списка по возрастанию методом быстрой сортировки.

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

Теоретическое описание

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

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

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

"голову" - первый элемент списка;

"хвост" - элемент или последовательность элементов следующих за "головой" списка.

Описание алгоритма быстрой сортировки.

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

В результате список разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х. Этот шаг называется разделением. Х - центром.

К получившимся частям рекурсивно применяем ту же процедуру. В результате получается очень эффективная сортировка. Среднее быстродействие O(n*log(n)), но возможен случай таких входных данных, на которых алгоритм будет работать за O(n²) операций. Hа случайных входных данных вероятность такого чрезвычайно мала.

Описание программы

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

Рассмотрим только основные предикаты, реализующие указанные в задании действия.

Список всех предикатов:

cmp(STRING,SLIST,SLIST,SLIST) %сортировка (для сравнения элементов)

del (SYMBOL,S,S) %удаление элемента перед указанным

chksmb(SYMBOL)%проверка ввода пользователя

tolist(S,INTEGER,WINDOW)%запись элементов в список

tolbox(S,WINDOW)%запись элементов в лист

delelem(SYMBOL,S,S)%удаление конкретного элемента

scan(SYMBOL,S) %поиск элемента в списке

isempty(S) %проверка на наличие элементов в списке

sort(SLIST,SLIST)%быстрая сортировка

link(SLIST,SLIST,SLIST)%вспомогательный предикат для сортировки

first(SYMBOL,S) %проверка на удаление перед первым эл-ом.

Основные предикаты:

del(SYMBOL,S,S)%удаление элемента перед указанным

· 1-й аргумент - элемент, перед которым требуется удалить другой элемент;

· 2-й аргумент - входной список элементов;

· 3-й аргумент - результирующий список элементов.

Данное правило использует восходящую рекурсию для удаления элементов из списка (2-й аргумент) и перемещения результата удаления элементов из списка в результирующий список(3-й аргумент).

sort (SLIST,SLIST)%предикат быстрой сортировки

· 1-й аргумент - список строк, который требуется отсортировать;

· 2-й аргумент - отсортированный список строк (результат).

Данное правило использует восходящую рекурсию для сортировки списка(1-й аргумент) и перемещения отсортированного списка в результирующий список(2-й аргумент).

Для каждого из рассмотренных предикатов текст соответствующих правил представлен в разделе "Текст программы".

Текст программы

domains

S=SYMBOL*

predicates %предикаты

dlg_dialog_eh : EHANDLER %идентификатор окна

cmp(STRING,SLIST,SLIST,SLIST)%сортировка

chksmb(SYMBOL)%проверка ввода пользователя

tolist(S,INTEGER,WINDOW)%запсиь элементов в список

tolbox(S,WINDOW)%запсиь элементов в лист

delelem(SYMBOL,S,S)%удаление конкретного элемента

nondeterm del(SYMBOL,S,S)%удалить предидущий

scan(SYMBOL,S)%поиск элемента в списке

isempty(S)%проверка на наличие элементов в списке

sort(SLIST,SLIST)%быстрая сортировка

link(SLIST,SLIST,SLIST)%вспомогательный предикат

first(SYMBOL,S)%проверка на удаление перед первым элементом

clauses %предложения

chksmb(EL):-EL>="A",EL<="Z",!.

chksmb(EL):-EL>="a",EL<="z",!.

chksmb(EL):-EL>="А",EL<="Я",!.

chksmb(EL):-EL>="а",EL<="я",!.

chksmb(EL):-EL>="0",EL<="9",!.

chksmb(EL):-EL="", dlg_error("Ошибка","Элемент не указан"),!, fail.

chksmb(_):-dlg_error("Ошибка","Некоректный ввод"),!, fail.

first(EL,[A|LST]):-EL=A.

tolist([E|LST],N,O):-

E=lbox_GetItem(O,N),

E<>"",

N1=N+1,!,

tolist(LST,N1,O).

tolist([],_,_).

tolbox([E|LST],O):-lbox_Add(O,E),tolbox(LST,O).

tolbox([],_).

%***************************************************************

delelem(_,[],[]).

delelem(EL,[E|LST],LST1):-EL=E,!,delelem(EL,LST,LST1).

delelem(EL,[E|LST],[E|LST1]):-!,delelem(EL,LST,LST1).

%***************************************************************

del(_,[],[]).

del(EL,[X,EL|T],[EL|T1]):-del(EL,T,T1),!.

del(EL,[X|T],[X|T1]):-del(EL,T,T1).

%***************************************************************

scan(_,[]):-!,fail. %проверяем наличие элемента в списке

scan(EL,[EL|_]):-!.

scan(EL,[_|LST]):-!,scan(EL,LST).

link([],L,L).

link([X|L1],L2,[X|L3]):-link(L1,L2,L3).

sort([],[]).

sort([X|Z],SORTLIST) :-

cmp(X, Z, S, L),

sort(S, SORTS),

sort(L, SORTL),

link(SORTS,[X|SORTL],SORTLIST).

cmp(_,[],[],[]).

cmp(X,[Y|TAIL], [Y|S],L):-X>Y,!,cmp(X,TAIL,S,L).

cmp(X,[Y|TAIL], S,[Y|L]):-cmp(X,TAIL,S,L).

isempty([]).%список пуст

%создание диалогового окна

dlg_dialog_Create(Parent):-

win_CreateResDialog(Parent,dlg_dialog_DlgType,dlg_dialog_ResID,dlg_dialog_eh,0).

%BEGIN dialog, idc_sort _CtlInfo

dlg_dialog_eh(_Win,e_Control(idc_sort,_CtrlType,_CtrlWin,_CtlInfo),0):-

L=win_GetCtlHandle(_Win,idc_list),

LN=lbox_CountAll(L),

LN>0,

S=lbox_GetAll(L),

sort(S,S1),

lbox_Clear(L),

lbox_Add(L,S1),

!.

%проверка списка на наличие в нем элементов

dlg_dialog_eh(_Win,e_Control(idc_sort,_CtrlType,_CtrlWin,_CtlInfo),0):-

List=win_GetCtlHandle(_Win,idc_list),

ListCount=lbox_CountAll(List),

ListCount=0,

dlg_Note("Ошибка","Список пуст"),

!.

%END dialog, idc_sort _CtlInfo

%BEGIN dialog, idc_addelem _CtlInfo

dlg_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

I=win_GetCtlHandle(_Win,idc_add),

O=win_GetCtlHandle(_Win,idc_list),

EL=win_GetText(I),

str_len(EL,1),

chksmb(EL),

lbox_Add(O,EL), %добавление элемента в список

win_SetText(I,""), %очистка поля ввода

!.

%проверка на корректный ввод

dlg_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

O=win_GetCtlHandle(_Win,idc_add),

T=win_GetText(O),

T="",

dlg_error("Ошибка","Элемент не задан"),

win_SetText(O,""),

!.

%проверка длины элемента

dlg_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

O=win_GetCtlHandle(_Win,idc_add),

T=win_GetText(O),

T<>"",

dlg_error("Ошибка","Элемент должен состоять из 1 символа!"),

win_SetText(O,""),

!.

%END dialog, idc_addelem _CtlInfo

%BEGIN dialog, при нажатии кнопки выхода idc_cancel _CtlInfo

dlg_dialog_eh(_Win,e_Control(idc_cancel,_CtrlType,_CtrlWin,_CtrlInfo),0):-!,

win_Destroy(_Win),

!.

%END dialog, idc_cancel _CtlInfo

%BEGIN dialog, idc_del_elem _CtlInfo

%обработка ввода пользователя - проверка списка на наличие элементов

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

O=win_GetCtlHandle(_Win,idc_list),

tolist(LIST,0,O),

isempty(LIST),

dlg_error("Ошибка","Список пуст"),

I=win_GetCtlHandle(_Win,idc_del),

II=win_GetCtlHandle(_Win,idc_befor),

win_SetText(I,""),

win_SetText(II,""),

!.

%проверка на заполнение обоих полей для удаления

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_befor),

DEL1=win_GetText(I),

DEL2=win_GetText(O),

DEL1<>"",

DEL2<>"",

dlg_error("Ошибка","Укажите один элемент для удаления в одном поле"),

win_SetText(I,""),

win_SetText(O,""),

!.

%удаление конкретного элемента

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_list),

EL=win_GetText(I),

str_len(EL,1),

chksmb(EL),

tolist(LIST,0,O),

scan(EL,LIST),

delelem(EL,LIST,LIST1),

lbox_Clear(O),

tolbox(LIST1,O),

win_SetText(I,""),

!.

%удаление элементов перед указанным

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

ListHandle=win_GetCtlHandle(_Win,idc_list),

ListCount=lbox_CountAll(ListHandle),

ListCount<>0,

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_befor),

EL=win_GetText(O),

EL<>"",

tolist(LIST,0,ListHandle),

first(EL,LIST),

dlg_error("Ошибка","Удаление перед первым элементом невозможно"),

win_SetText(I,""),

win_SetText(O,""),

!.

%удаление элементов перед указанным

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

ListHandle=win_GetCtlHandle(_Win,idc_list),

ListCount=lbox_CountAll(ListHandle),

ListCount<>0,

BeforHandle=win_GetCtlHandle(_Win,idc_befor),

EL=win_GetText(BeforHandle),

EL<>"",

str_len(EL,1),

chksmb(EL),

tolist(LIST,0,ListHandle),

scan(EL,LIST),

del(EL,LIST,LIST1),

lbox_Clear(ListHandle),

tolbox(LIST1,ListHandle),

win_SetText(BeforHandle,""),

!.

%обработка ввода пользователя:

%проверка на корректный ввод в поля элементов

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_befor),

DEL1=win_GetText(I),

DEL2=win_GetText(O),

concat(DEL1,DEL2,DEL),

DEL="",

dlg_error("Ошибка","Элемент для удаления не указан"),

win_SetText(I,""),

win_SetText(O,""),

!.

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_befor),

DEL1=win_GetText(O),

DEL1<>"",

ListHandle=win_GetCtlHandle(_Win,idc_list),

ListCount=lbox_CountAll(ListHandle),

ListCount=1,

dlg_error("Ошибка","Число элементов должно быть четным"),

win_SetText(I,""),

win_SetText(O,""),

!.

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-

dlg_error("Ошибка","Заданный элемент не существует"),

I=win_GetCtlHandle(_Win,idc_del),

O=win_GetCtlHandle(_Win,idc_befor),

win_SetText(I,""),

win_SetText(O,""),

!.

%END dialog, idc_delelem _CtlInfo

Программа и методика испытаний

Объект испытаний

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

Цель испытаний

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

Средства и порядок испытаний

Требования к техническим средствам:

ЭВМ модели - Pentium 4 и выше.

Объем ОЗУ - 1 Гб,

Объем свободной памяти на жестком диске 1 Гб

Программное обеспечение - операционная система Windows 2000\NT\XP.

Специальной конфигурации программного обеспечения не требуется.

Испытание программы проводились в следующем порядке:

испытание на корректность (адекватно ли программа реагирует на ввод вывод информации);

испытание на правильность;

испытание на надежность (процент отказа системы).

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

Методы испытаний

Проверка на корректность

Проверка при использовании входных данных:

Поле "элемент" было заполнено значениями: 1,9,2,8,3,7,4,6,5,0,а,б;

Поле "перед" было заполнено значением 3;

При нажатии на кнопку "Сортировка" результат совпал

с ожидаемым (рис. 2).

При нажатии на кнопку "Удалить" результат совпал

с ожидаемым (рис. 3).

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

Удаление перед первым элементом, выдается сообщение об ошибке (рис. 4, рис. 5, рис. 6, рис. 7, рис. 8);

Проверка на корректный вывод информации

При выводе отсортированного списка результат не отличался от ожидаемого (см. рис. 2). При удалении элемента 0 из списка перед указанным, результат не отличался от ожидаемого (см рис. 3). Поэтому можно сказать, что программа работает корректно.

Проверка на правильность

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

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

Проверка на надежность

При изменении входных данных не должен изменяться внешний вид пользовательского интерфейса. При выводе списка '1','9','2','8','3', '7','4', '6','5','0','а','б' внешний вид пользовательского интерфейса не отличался от интерфейса, полученного при вводе списка '3', '5', 'x', 'y', 'Z' (см рис. 2 и рис. 9).

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

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

Эскизы экранных форм

Рис. 1. Результат работы программы при корректных данных.



Рис. 2. Результат сортировки списка.

Рис. 3. Результат удаления элемента из списка перед указанным.



Рис. 4. Вывод сообщения об ошибке при отсутствии элемента для добавления.

Рис. 5. Вывод сообщения об ошибке при добавлении элемента с длиной более 1 символа.

Рис. 6. Вывод сообщения об ошибке при нажатии на кнопку удалить, если список пуст.

Рис. 7. Вывод сообщения об ошибке при отсутствии элемента для удаления.



Рис. 8. Вывод сообщения об ошибке при попытке удаления элемента перед первым элементом.

Рис. 9. Результат работы программы при разных входных данных.

Задание 2

ТЕМА: Бинарные деревья.

ЦЕЛЬ: Научиться работать с бинарными деревьями.

ЗАДАНИЕ 2: Написать программу для обхода бинарного дерева по схеме: Правое поддерево - Корень - Левое поддерево. Все необходимые исходные данные задаются пользователем. Вывод результата осуществляется в отдельное окно.

Теоретические сведения

Бинарное дерево - частный случай составной структуры. Бинарные деревья задаются с помощью тренарного функтора:

программа сортировка предикат бинарный

tree( Element, Left, Right ); void - пустое дерево.

Например:

tree ( a, b, c ); tree ( a, tree( b, void, void), tree( c, void, void) ).

Проверка принадлежности дереву:

tree_mem ( X, tree( X, L, R )).

tree_mem ( X, tree( Y, L, R )) :- tree_mem ( X, L ).

tree_mem ( X, tree( Y, L, R )) :- tree_mem ( X, R ).

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

а) сверху вниз: ( V, L, R )

pre ( tree ( X, L, R ), XS ) :- pre ( L, LS ), pre ( R, RS ), append ( [ X | LS ], RS, XS ).

pre ( void, [ ] ).

б) слева направо: ( L, V, R )

in ( tree ( X, L, R ), XS ) :- in ( L, LS ), in ( R, RS ), append ( LS, [ X | RS ], XS ).

in ( void, [ ] ).

в) снизу вверх: ( L, R, V )

post (tree( X, L, R ), XS ):- pre( L, LS ), pre( R, RS ), append( RS, [ X ], RS1),append( LS, RS1, XS ).

post ( void, [ ] ).

Логика программы

Domains

tr = tree(tr, string, tr); void

slist=string*

Predicates

nondeterm append(slist, slist, slist)

nondeterm in(tr, slist)

Clauses

append([], Ys, Ys).

append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

in (tree(L, X, R), XS) :-in(R,RS),in(L,LS),append(LS,[X|RS],XS).

in(void,[]).

goal

in (tree (tree (void, "b", void), "a", tree (void, "c", void)), R), write (R).

Список использованных источников

1. Дж. Доорс, А. Р. Рейблен, С. Вадера. ПРОЛОГ - язык программирования будущего. - М.: Финансы и статистика, 1990.

2. Л. Стерлинг, Э. Шапиро. Искусство программирования на языке ПРОЛОГ. - М.: Мир, 1990.

3. И. Братко. Программирование на языке Пролог для искусственного интеллекта. - М.: Мир, 1990.

Размещено на Allbest.ru