close

Вход

Забыли?

вход по аккаунту

?

ЛП4

код для вставкиСкачать
Министерство образования и науки Украины
Севастопольский национальный технический университет
кафедра кибернетики и
вычислительной техники
Лабораторная работа № 4
по дисциплине "Логическое программирование"
"ОБРАБОТКА СПИСКОВ"
Вариант № 21
Выполнил: ст. гр. М-43д
Ярославцев Д.А.
Проверил: доц. Брюховецкий А.А.
2011
Цель работы: Ознакомиться с реализацией структуры данных типа список в языке Пролог и методами их обработки в среде Visual Prolog.
Постановка задачи:
Необходимо разработать консольное приложение на языке Prolog для работы со списками, позволяющее организовать следующие операции: * добавление элемента списка,
* удаление элемента из списка,
* конкатенация списков,
* определение длины списка,
* определение принадлежности к списку,
* подсчет количества положительных чисел в списке.
Ход работы:
Структура предиката для определения длины списка:
Логично определить:
* Длина пустого списка [] есть 0.
* Длина любого другого списка есть 1 плюс длина его хвоста.
Строго говоря, [_|T] сопоставляется с любым непустым списком, связывая T с хвостом списка. Значение головы неважно, если она есть, она может быть учтена как один элемент. length_of вызывает себя рекурсивно. Этот вызов сопоставляется со вторым клаузом, связывая [/*список*/] и T(хвост) в вызове клаузы и TailLength с L в клаузе.
Рекурсивный вызов продолжается до тех пор, пока хвост список не окажется пуст - тогда переменная TailLength будет конкретизирована и получит значение 0. Далее будем подсчитывать L как TailLength + 1, а затем возврат и подстановка нового значения TailLength.
Первый параметр предиката - список целых чисел, второй параметр - целое число для хранения длины списка. Структура предиката для добавления элемента:
Первый и третий параметры - списки целых чисел, второй параметр - целое число. Голове третьего параметра присваиваем значение второго параметра, а хвосту - третьего. В результате получаем новый список, голова которого определяется вторым параметром, а хвост - первым.
Структура предиката для удаления элемента:
Данный предикат выполняет операцию удаления головы списка, в качестве результата возвращает новый список и удалённый элемент. Первый и второй параметры - списки целых чисел, третий - целое число. Второму аргументу (списку) присваивается значение хвоста первого аргумента (списка), а голову первого аргумента помещаем в третий аргумент.
Структура предиката для конкатенации списков:
Все параметры предиката - списки целых чисел. Структура предиката для получения всех членов списка.
Используется также предикат
Выбираем голову списка и возвращаем ее, последующий вызов осуществляем уже с хвостом списка. Операции продолжаем, пока хвост списка не пуст. Параметры предиката: первый предикат - целое число, второй - список целых чисел.
Структура предиката для определения принадлежности к списку
Организовываем получение всех элементов списка и по очереди сравниваем каждый элемент с заданным значением. При равенстве значений - выводим сообщение о наличии элемента с данным значением в списке. Параметры предиката: первый - список целых чисел, для которого будем определять принадлежность элемента, второй - целое число, принадлежность которого к списку будем определять.
Структура предиката для определения количества положительных чисел в списке
Параметры предиката - [H|Tail] - список целых чисел, разделенный на голову (H) и хвост (Tail). Выполняется проверка головы списка на положительность. Если значение H больше 0, выполняется рекурсивный вызов positive(Tail,C1) - аргументы которого - список, полученный из хвоста исходного списка, С1 - новое, не конкретизированное значение, в котором хранится результат предиката. В противном случае предикат выполняет отсечение (обозначается восклицательным знаком в тексте программы - ! ), переход к предикату positive(Tail,C). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).
Пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатывающий предикат (предикат, содержащий отсечение).
positive([],0) - предикат, обозначающий конец рекурсивных вызовов, затем совершаем возврат с конкретизацией переменных и вычислением результата С как сумму значения С1 с 1.
Текст программы:
implement main open core, console domains rList= integer*. class predicates length_of:(rList, integer) procedure (i, o). add:(rList, integer, rList) procedure (i, i, o).
delete:(rList, rList, integer) procedure (i, o, o).
conc : (rList, rList, rList) procedure (i, i, o).
member : (integer, integer*) nondeterm (o,i). test : (integer*,integer) procedure (i,i). positive : (integer*, integer) procedure (i,o). clauses classInfo("main", "append").
length_of([], 0).
length_of([_|T], L):-
length_of(T, TailLength),
L = TailLength + 1.
add(X, S, D) :- D = [S|X]. delete([], [],0) :- !.
delete([X|Xs], D,G) :- D = Xs, G = X. conc([], L, L). conc([H|T], L, [H|U]) :-
conc(T, L, U).
member(H, [H|_]).
member(H, [_|T]) :- member(H, T).
test(L,M) :- member(H, L), if(H=M) then stdIO::nl, write("Данный элемент - ", M, " присутствует в списке") end if,
stdio::nl, fail or succeed(). positive([],0).
positive([H|Tail],C):-H > 0,!,positive(Tail,C1),C = C1+1.
positive([_|Tail],C):-positive(Tail,C).
run():- console::init(), stdIO::nl,
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите список (будет определена его длина)"),
stdIO::nl,
List= read(), length_of(List, A),
stdIO::nl,
write("Длина списка - ", A), stdIO::nl,
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите список, в который будем добавлять элемент(ы)"),
stdIO::nl,
List1= read(),
stdIO::nl,
write("Введите элемент, который нужно добавить в список"),
stdIO::nl,
A1= read(),
add(List1, A1, List2),
stdIO::nl,
write("Список до добавления: ", List1),
stdIO::nl,
write("Список после добавления: ", List2),
stdIO::nl,
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите список (будет произведена операция удаления)"),
stdIO::nl,
List3= read(),
delete(List3, List4, A3),
write("Список до удаления: ", List3),
stdIO::nl,
write("Список после удаления ", List4),
stdIO::nl,
write("Удаленный элемент - ", A3),
stdIO::nl,
write("--------------------------------------------------------------------------"),
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите первый список (подготовка данных к конкатенации)"),
stdIO::nl,
List5= read(),
write("Введите второй список для конкатенации"),
stdIO::nl,
List6= read(),
write("Список 1 до конкатенации ", List5),
stdIO::nl,
write("Список 2 до конкатенации ", List6),
stdIO::nl,
conc(List5, List6, List7),
write("Результат конкатенации списков - ", List7),
stdIO::nl,
write("--------------------------------------------------------------------------"),
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите список (будет произведена проверка на наличие элемента)"),
stdIO::nl,
write("Отсутствие результата обозначает отстутствие элемента в списке"),
stdIO::nl,
List8= read(),
write("Теперь введите элемент, который будем искать"),
stdIO::nl,
A4= read(),
write("Стало ", List8),
test(List8,A4), stdIO::nl,
write("--------------------------------------------------------------------------"),
write("--------------------------------------------------------------------------"),
stdIO::nl,
write("Введите список (будет определено количество положительных чисел в нем)"),
stdIO::nl,
%write("Если ничего не высветиться - повторений нет"),
%stdIO::nl,
List9= read(),
stdIO::nl,
positive(List9,F),
stdIO::nl,
write("Количество положительных чисел в списке - ",F),
stdIO::nl,
write("Программа успешно выполнена"),
stdIO::nl,
write("--------------------------------------------------------------------------"),
List11= read(), length_of(List11, A11),
stdIO::nl,
write("Длина списка ", A11), nl. end implement main goal mainExe::run(main::run).
Выполнение программы в режиме трассировки:
Trace: >> CALL: goal()
Trace: >> CALL: write(Введите список (будет определена его длина))
Trace: >> CALL: LIST$0 = [1,2,3]
Trace: >> RETURN: [1,2,3] = [1,2,3]
Trace: >> CALL: length_of([1,2,3],A$1)
Trace: >> CALL: length_of([2,3],TAILLENGTH$2)
Trace: >> CALL: length_of([3],TAILLENGTH$3)
Trace: >> CALL: length_of([],TAILLENGTH$4)
Trace: >> RETURN: length_of([],0)
Trace: >> CALL: TAILLENGTH$3 = 1
Trace: >> RETURN: 1 = 1
Trace: >> RETURN: length_of([3],1)
Trace: >> CALL: TAILLENGTH$2 = 2
Trace: >> RETURN: 2 = 2
Trace: >> RETURN: length_of([2,3],2)
Trace: >> CALL: A$1 = 3
Trace: >> RETURN: 3 = 3
Trace: >> RETURN: length_of([1,2,3],3)
Trace: >> CALL: write(Длина списка - ,3)
Trace: >> CALL: write(Введите список, в который будем добавлять элемент(ы))
Trace: >> CALL: LIST1$5 = [1,3,5]
Trace: >> RETURN: [1,3,5] = [1,3,5]
Trace: >> CALL: write(Введите элемент, который нужно добавить в список)
Trace: >> CALL: A1$6 = 55
Trace: >> RETURN: 55 = 55
Trace: >> CALL: add([1,3,5],55,LIST2$7)
Trace: >> CALL: LIST2$7 = [55,1,3,5]
Trace: >> RETURN: [55,1,3,5] = [55,1,3,5]
Trace: >> RETURN: add([1,3,5],55,[55,1,3,5])
Trace: >> CALL: write(Список до добавления: ,[1,3,5])
Trace: >> CALL: write(Список после добавления: ,[55,1,3,5])
Trace: >> CALL: write(Введите список (будет произведена операция удаления))
Trace: >> CALL: LIST3$8 = [1,8,9]
Trace: >> RETURN: [1,8,9] = [1,8,9]
Trace: >> CALL: delete([1,8,9],LIST4$9,A3$10)
Trace: >> CALL: LIST4$9 = [8,9]
Trace: >> RETURN: [8,9] = [8,9]
Trace: >> CALL: A3$10 = 1
Trace: >> RETURN: 1 = 1
Trace: >> RETURN: delete([1,8,9],[8,9],1)
Trace: >> CALL: write(Список до удаления: ,[1,8,9])
Trace: >> CALL: write(Список после удаления ,[8,9])
Trace: >> CALL: write(Удаленный элемент - ,1)
Trace: >> CALL: write(Введите первый список (подготовка данных к конкатенации))
Trace: >> CALL: LIST5$11 = [5,-1,3]
Trace: >> RETURN: [5,-1,3] = [5,-1,3]
Trace: >> CALL: write(Введите второй список для конкатенации)
Trace: >> CALL: LIST6$12 = [0,-2,11]
Trace: >> RETURN: [0,-2,11] = [0,-2,11]
Trace: >> CALL: write(Список 1 до конкатенации ,[5,-1,3])
Trace: >> CALL: write(Список 2 до конкатенации ,[0,-2,11])
Trace: >> CALL: conc([5,-1,3],[0,-2,11],LIST7$13)
Trace: >> CALL: conc([-1,3],[0,-2,11],U$14)
Trace: >> CALL: conc([3],[0,-2,11],U$15)
Trace: >> CALL: conc([],[0,-2,11],U$16)
Trace: >> RETURN: conc([],[0,-2,11],[0,-2,11])
Trace: >> RETURN: conc([3],[0,-2,11],[3,0,-2,11])
Trace: >> RETURN: conc([-1,3],[0,-2,11],[-1,3,0,-2,11])
Trace: >> RETURN: conc([5,-1,3],[0,-2,11],[5,-1,3,0,-2,11])
Trace: >> CALL: write(Результат конкатенации списков - ,[5,-1,3,0,-2,11])
Trace: >> CALL: write(Введите список (будет произведена проверка на наличие элемента))
Trace: >> CALL: write(Отсутствие результата обозначает отсутствие элемента в списке)
Trace: >> CALL: LIST8$17 = [2,5,0]
Trace: >> RETURN: [2,5,0] = [2,5,0]
Trace: >> CALL: write(Теперь введите элемент, который будем искать)
Trace: >> CALL: A4$18 = 5
Trace: >> RETURN: 5 = 5
Trace: >> CALL: write(Введите список (будет определено количество положительных чисел в нем))
Trace: >> CALL: LIST9$19 = [1,-1,3]
Trace: >> RETURN: [1,-1,3] = [1,-1,3]
Trace: >> CALL: positive([1,-1,3],F$20)
Trace: >> CALL: 1 > 0
Trace: >> RETURN: 1 > 0
Trace: >> CALL: positive([-1,3],C1$21)
Trace: >> CALL: -1 > 0
Trace: >> FAIL: -1 > 0
Trace: >> CALL: positive([3],C1$21)
Trace: >> CALL: 3 > 0
Trace: >> RETURN: 3 > 0
Trace: >> CALL: positive([],C1$22)
Trace: >> RETURN: positive([],0)
Trace: >> CALL: C1$21 = 1
Trace: >> RETURN: 1 = 1
Trace: >> RETURN: positive([3],1)
Trace: >> RETURN: positive([-1,3],1)
Trace: >> CALL: F$20 = 2
Trace: >> RETURN: 2 = 2
Trace: >> RETURN: positive([1,-1,3],2)
Trace: >> CALL: write(Количество положительных чисел в списке - ,2)
Trace: >> CALL: write(Программа успешно выполнена)
True
1 Solution
Результат выполнения программы (без трассировки)
Вывод:
В ходе выполнения лабораторной работы ознакомился с реализацией структуры данных типа список в языке Пролог и методами их обработки в среде Visual Prolog, разработал консольное приложение на языке Prolog для работы со списками. 
Документ
Категория
Рефераты
Просмотров
31
Размер файла
148 Кб
Теги
лп4
1/--страниц
Пожаловаться на содержимое документа