Лабораторная работа обработка списков цель работы
Скачать 53.85 Kb.
|
Лабораторная работаОБРАБОТКА СПИСКОВ Цель работы – изучение механизма рекурсивного вывода на примерах разработки процедур обработки списков. Краткая справка Список — упорядоченное множество объектов одинакового типа. Формально это определение соответствует определению массива в традиционных языках программирования. Однако в списке не оговаривается ни размерность, ни число элементов. Например, список, состоящий из целых чисел, на Прологе описывается так: [1, 7, 3, 50], то есть элементы списка заключаются в квадратные скобки и разделяются запятыми. Пустой список обозначается [ ]. Если в программе предусмотрена обработка списков, они обязательно должны быть описаны в секции доменов: domains integerlist = integer* /* Список целых чисел */ symbollist = symbol* /* Список символических имен */ listlist = integerlist* /* Список списков */ Список списков можно рассматривать как аналог двумерного массива. В Прологе список принято разделять на две части: начало и конец списка. Еще говорят, голова (head) и хвост (tail) или остаток (rest) списка. Голова и хвост списка разделяются вертикальной чертой |: [ голова | хвост ], где “голова” чаще всего является первым элементом списка, но может быть и любое число начальных элементов списка. Рассмотрим примеры сопоставления списков и результат этих сопоставлений:
Примеры обработки списков 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 Solution3. Индексирование списка Речь идет о предикате, позволяющем определить значение элемента по его номеру в списке (и наоборот). 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 Проработать рассмотренные процедуры обработки списков. Самостоятельные задания
Контрольные вопросы
Список используемых источников
|
Похожие:
 | Лабораторная работа №3 работа со списками Целью работы является изучение приемов работы со списками в Прологе, а также более детальное изучение рекурсивного программирования... | | Лабораторная работа «Обработка деревьев» Цель работы – получить навыки применения двоичных деревьев, реализовать основные операции над деревьями: обход деревьев, включение,... |
| Лабораторная работа №5. Эксперимент лабораторная работа №6 Раздел II. Эмпирические исследования познавательных процессов. Ощущения и восприятие лабораторные работы №7-9: Методика «Специфика восприятия» Цель: Выявление типов поведения студентов (коллег) в дискуссии (наблюдение по схеме Р. Бейлза) | | Контрольная работа №3 Лабораторная работа 5 Цель лабораторной работы – освоить основные способы работы со стеками и очередями |
| Лабораторная работа. "Обработка одномерных массивов (векторов)" Цель работы: Знакомство с структурированными типами данных, получение практических навыков в организации одномерных массивов данных.... | | Лабораторная работа «Графы» Цель работы Цель работы – реализовать алгоритмы обработки графовых структур: поиск различных путей, проверку связности, построение остовых деревьев... |
| Лабораторная работа №6 Автоматизация работы текстового процессора Microsoft Word. Работа с большим (структурированным) документом Цель работы: изучение возможностей автоматизации работы в текстовом редакторе Microsoft Word, работы со сносками, методов создания... | | Лабораторная работа №2 Цель работы: изучить основы работы и создания проектной документации в среде Visio 2007 |
 | Лабораторная работа №9 фотоколориметрический анализ ... | | Лабораторная работа 2 цель работы Исследование влияния различных факторов на величину синхронизирующего момента и точность работы сельсинной пары в индикаторном и... |