Лабораторная работа обработка списков цель работы




Скачать 53.85 Kb.
НазваниеЛабораторная работа обработка списков цель работы
Дата21.12.2012
Размер53.85 Kb.
ТипЛабораторная работа
Лабораторная работа

ОБРАБОТКА СПИСКОВ


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


Краткая справка

Список — упорядоченное множество объектов одинакового типа.

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

Например, список, состоящий из целых чисел, на Прологе описывается так: [1, 7, 3, 50], то есть элементы списка заключаются в квадратные скобки и разделяются запятыми.


Пустой список обозначается [ ].


Если в программе предусмотрена обработка списков, они обязательно должны быть описаны в секции доменов:

domains

integerlist = integer* /* Список целых чисел */

symbollist = symbol* /* Список символических имен */

listlist = integerlist* /* Список списков */


Список списков можно рассматривать как аналог двумерного массива.


В Прологе список принято разделять на две части: начало и конец списка. Еще говорят, голова (head) и хвост (tail) или остаток (rest) списка. Голова и хвост списка разделяются вертикальной чертой |:

[ голова | хвост ],


где “голова” чаще всего является первым элементом списка, но может быть и любое число начальных элементов списка.


Рассмотрим примеры сопоставления списков и результат этих сопоставле­ний:


Список 1

Список 2

Результат

[ Х1, Х2, Х3 ]

[ 1, 2, 3 ]

Х1=1, Х2=2, Х3=3

[ 7 ]

[ Х1 | X2 ]

X1=7, X2=[ ]

[ 1, 2, 3,4 ]

[ X1, X2 | X3 ]

X1=1, X2=3, X3=[ 3,4 ]

[ X ]

[ 5 ]

X=5



Примеры обработки списков


1. Определение принадлежности элемента списку

Чтобы работать с данными разного типа, имеется возможность много­кратного определения предиката.


domains

list=symbol* /* Список символьных данных */

list=integer* /* Список целых чисел */


predicates

member(symbol, list) /* ( i, i ) */

member(integer, list)


clauses

member(Name,[Name| _ ]).

member(Name,[ _ |Rest]):- member(Name,Rest).


Из первого утверждения процедуры следует, что элемент принадлежит спи­ску, если он стоит в голове списка. Согласно второму утверждению элемент принадлежит списку, если он нахо­дится в начале оставшейся части списка. По умолчанию в голове списка находится один (первый) элемент этого списка.

При выполнении рекурсивного правила, всякий раз как бы отсекается по одному головному элементу списка. И где бы ни находился искомый элемент, в конце концов, он окажется в голове оставшейся части списка. А это приведет к сра­батыванию первого утверждения процедуры (граничного условия).


Введем цель:

Goal : member (“Дима”, [“Дима”, “Маша”]).

Yes

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

Изменим цель:


Goal : member (“Дима”, [ “Валя”, “Дима”, “Маша”]).

Yes


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


2. Объединение списков (конкатенация)


В некоторых версиях Пролога имеется встроенный (стандартный) предикат append(...), выполняющий функцию объединения списков. В Турбо-Прологе та­кого предиката нет, но процедуру объединения списков легко реализовать само­стоятельно.


domains

list = symbol*

predicates

append(list, list, list) /* (i,i,o) */


clauses

append([ ], L, L).

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


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

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

Когда первый список будет исчерпан, сработает первое утверждение: ре­зультирующий список станет равным второму списку, и к его началу на обратном ходе рекурсии последовательно присоединятся элементы из стека переменной H.

Зададим цель:


Goal: append( [ a, b ], [ c, d, e ], L).

L= [ “a”,”b”, “c”, “d”, “e” ]

1 Solution


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

Например, рассмотренное решение задачи объединения списков может быть использовано для “вычитания” и “разбиения” списков.

Пример вычитания списков:


Goal: append( [ a, b ], L, [ a, b, c, d, e] ).

L= [ “c”, “d”, “e” ]
1 Solution



3. Индексирование списка

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


domains

list=symbol*


predicates

index(list,integer,symbol) /* ( i, i, o) */


clauses

index([ H | _ ], 1, H).

index([ _ | R], N, X):- index(R,K,X), N=K+1.


Пример решения:


Goal: index([ a,b,c,d ], 3, S).

S= c

1 Solution


Goal: index([ a,b,c,d ], N, c).

N= 3

1 Solution


4. Определение длины списка


Подсчитывается число элементов в списке.

domains

list=symbol*

lenlist(list,integer) /* ( i, o ) */


clauses

lenlist( [ ], 0 ).

lenlist( [ _ | R ], L ):- lenlist( R, L1 ), L=L1+1.


Пример решения:


Goal: lenlist([ a, b, c, d, e], N).

N=5

1 Solution


5. Определение суммы действительных чисел списка


domains

rlist=real*

predicates

sumlist(rlist,real) /* (i,o) */


clauses

sumlist([ ],0).

sumlist([H|R],S):-sumlist(R,S1),S=S1+H.


Пример решения:


Goal: sumlist( [ 2.5, 4, 7.5, 6 ], Y ).

Y=20


Проработать рассмотренные процедуры обработки списков.

Самостоятельные задания


  1. Создайте предикат, заменяющий в исходном списке первое вхождение заданного значения другим.

  2. Создайте предикат, заменяющий в исходном списке все вхождения заданного значения другим.

  3. Создайте предикат, удваивающий значения элементов списка.

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

  5. Создайте предикат, который разделит исходный список из целых чисел на два списка: список положительных чисел и список отрицательных чисел.

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

  7. Создайте предикат, осуществляющий удаление указанного количества последних элементов исходного списка.

Контрольные вопросы


  1. Что понимается в Прологе под списком?

  2. Как обозначается пустой список?

  3. Как разделяется начало и конец списка?



Список используемых источников





  1. Крылов, Б.А. Логическое программирование. Учебное пособие – М.: Изд-во МГИЭМ, 2006. – 100 с.

  2. Программирование на Прологе. Методические указания к выполнению лабораторных работ 4-8 по дисциплине “Логическое программирование” / Сост. Б.А. Крылов, Моск. гос. ин-т электроники и математики. - М.: Изд-во МГИЭМ, 2006. - 22 с.

Похожие:

Лабораторная работа обработка списков цель работы iconЛабораторная работа №3 работа со списками
Целью работы является изучение приемов работы со списками в Прологе, а также более детальное изучение рекурсивного программирования...
Лабораторная работа обработка списков цель работы iconЛабораторная работа «Обработка деревьев»
Цель работы – получить навыки применения двоичных деревьев, реализовать основные операции над деревьями: обход деревьев, включение,...
Лабораторная работа обработка списков цель работы iconЛабораторная работа №5. Эксперимент лабораторная работа №6 Раздел II. Эмпирические исследования познавательных процессов. Ощущения и восприятие лабораторные работы №7-9: Методика «Специфика восприятия»
Цель: Выявление типов поведения студентов (коллег) в дискуссии (наблюдение по схеме Р. Бейлза)
Лабораторная работа обработка списков цель работы iconКонтрольная работа №3 Лабораторная работа 5
Цель лабораторной работы – освоить основные способы работы со стеками и очередями
Лабораторная работа обработка списков цель работы iconЛабораторная работа. "Обработка одномерных массивов (векторов)"
Цель работы: Знакомство с структурированными типами данных, получение практических навыков в организации одномерных массивов данных....
Лабораторная работа обработка списков цель работы iconЛабораторная работа «Графы» Цель работы
Цель работы – реализовать алгоритмы обработки графовых структур: поиск различных путей, проверку связности, построение остовых деревьев...
Лабораторная работа обработка списков цель работы iconЛабораторная работа №6 Автоматизация работы текстового процессора Microsoft Word. Работа с большим (структурированным) документом
Цель работы: изучение возможностей автоматизации работы в текстовом редакторе Microsoft Word, работы со сносками, методов создания...
Лабораторная работа обработка списков цель работы iconЛабораторная работа №2
Цель работы: изучить основы работы и создания проектной документации в среде Visio 2007
Лабораторная работа обработка списков цель работы iconЛабораторная работа №9 фотоколориметрический анализ
...
Лабораторная работа обработка списков цель работы iconЛабораторная работа 2 цель работы
Исследование влияния различных факторов на величину синхронизирующего момента и точность работы сельсинной пары в индикаторном и...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница