Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика»



Скачать 436.3 Kb.
страница4/4
Дата26.07.2014
Размер436.3 Kb.
ТипУчебно-методическое пособие
1   2   3   4

5.11. Списки

Список – это объект, который содержит конечное число других объектов. Список в ПРОЛОГе можно приблизительно сравнить с массивами в других языках, но для списков нет необходимости заранее объявлять размерность.

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

Примеры списков:

список, элементами которого являются целые числа: [1, 2, 3]

список, элементами которого являются строки: [“One”, “Two”, “Three”]

пустой список: []

Элементами списка могут быть списки: [[-1,3,5],[6,4,2,8]]

Чтобы использовать в ПРОЛОГ-программе списки, необходимо в разделе DOMAINS описать тип домена в формате.



<имя домена> = <тип элементов>*

Например,

DOMAINS

list = *

Список является рекурсивным объектом. Он состоит из головы (первого элемента списка) и хвоста (все последующие элемента). Хвост также является списком.

Например, [A, B, C] - список , у которого А – голова, [B,C] - хвост

В ПРОЛОГе имеется операция “|”, которая позволяет делить список на голову и хвост.

[A, B, C] = [A | [B, C] ] = [A | [B | [C] ] ] = [A | [B | [C | [ ] ] ] ]

Пустой список нельзя разделить на голову и хвост. Такая структура позволяет использовать рекурсию для обработки списка.

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

DOMAINS

list = integer *



PREDICATES

writelist(list)

CLAUSES

writelist ([]).



writelist ([A | Z]) :- write (A), nl, writelist (Z).

GOAL


writelist([10, 20, 30, 40]).

Результат выполнения программы:

10

20

30



40

В данной программе A – голова списка, Z – его хвост



5.12. Стандартные задачи обработки списка

К наиболее типичным задачам обработки списков относятся:

1) генерирование списка;

2) объединение списков;

3) поиск заданного элемента в списке;

4) удаление указанного элемента из списка;

5) вставка указанного элемента в список.

1. Генерирование списка из (N2-N1) последовательных целых чисел, начиная с N1.

Для формирования списка создадим отношение genlist(N1, N2, L), где

N1 – начальный элемент списка

N2 – его верхняя граница

L – список

Возможны случаи:

1) если N1 = N2, тогда N1 – не добавляется в список и L – пустой список.

genlist (N2, N2, [ ]) – первая часть правила (условие останова).

2) если N1 < N2, то N1 помещаем в голову списка, затем увеличиваем N1 на 1 и для нового значения снова вызывается genlist. Получаем вторую часть правила:

genlist (N1, N2, [N1 | L]): - N1 < N2, N = N1+1, genlist (N, N2, L).

Таким образом, правило формирования списка имеет вид:

genlist (N2, N2, [ ]). % нерекурсивная часть правила

genlist (N1, N2, [N1 | L]): - % рекурсивная часть правила

N1 < N2, N = N1+1, GenList (N, N2, L).

Например, для формирования списка [2, 3, 4, 5] следует указать запрос:

GOAL


GenList (2, 6, L), Write (L), nl.

2. Объединение списков.

Создадим отношение append(L1, L2, L3), где L1, L2 – исходные списки, L3 – список, полученный в результате присоединения L2 к L1.

Возможны случаи:

1) если L1 пустой список, то результирующий список L3 равен списку L2. Получаем первую (нерекурсивную) часть правила:

append ([ ], L, L).

2) если L1 не пустой список, то делим его на голову и хвост ( [X | L1]). Вторая (рекурсивная) часть правила:

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

Таким образом, правило объединения списков имеет вид:

append ([ ], L, L).

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

Например, для объединения списков [1, 2, 3] и [4, 5] следует написать запрос:

GOAL


append ([1, 2, 3], [4, 5], L) write [L].

Результат:

[1, 2, 3, 4, 5]

При выполнении программы из L1 выделяется и заносится в стек по одному элементу (голова списка) до тех пор, пока L1 не станет пустым. После этого выполняется первая часть правила и L3 получает значение L2, то есть L3 = [4, 5] начинается выгрузка элементов из стека и добавление их в голову L3.

Правило append обладает большое гибкостью и позволяет решать множество задач по обработке списка. Его можно использовать для решения обратной задачи: разбиение исходного списка на две части.

Например, чтобы определить все возможные способы разбиения списка [1,2,3], следует составить запрос:

GOAL

append (L1, L2, [1,2,3]), write (“L1=”, L1, “L2=”, L2), fail, nl.



Результат:

L1 = [ ] L2 = [1, 2, 3]

L1 = [1] L2 = [2, 3]

L1 = [1, 2] L2 = [3]

L1 = [1, 2, 3] L2 = [ ]

3. Поиск заданного элемента

Чтобы определить содержится ли элемент X в списке L создадим отношение member(X, L).

Возможны случаи:

1) если X совпадает с головой списка L, то элемент найден и поиск прекращается. Первая часть правила (нерекурсивная):

member (X, [X | L]).

2) если X не принадлежит голове, то он может принадлежать хвосту. Отбрасываем голову списка и вызываем правило для оставшегося списка. Вторая часть правила (рекурсивная):

member (X, [_ | L]: - member (X, L).

Таким образом, правило поиска элемента имеет вид:

member (X, [X | L]).

member (X, [_ | L]: - member (X, L).

Например, для ответа на вопрос «Содержится ли число 4 в списке [2, 3, 4, 5]?», можно составить запрос:

GOAL


member(4, [2, 3, 4, 5]),Write (“yes”);Write (“no”), nl.

При выполнении поиска X сравнивается с головой L. Если элементы не совпадают, то первый элемент отбрасывается и X сравнивается с головой полученного списка и так далее, пока L не станет пустым списком. Если элемент X найден, то цель достигнута, выводится сообщение “yes”, иначе выводится “no”.



4.Удаление элемента из списка.

Определим отношение del(X, L, L1), где

X – удаляемый элемент;

L – исходный список;

L1 – список, полученный в результате удаления X из L.

Возможны два случая:

1) если X – голова списка, то результирующий список равен хвосту списка L. Первая часть правила (нерекурсивная):

del(X, [X|L], L).

2) если X принадлежит хвосту, то список L делим на голову и хвост. Для хвоста снова вызывается правило del. Вторая часть правила (рекурсивная):

del(X, [Y|L], [Y|L1]):- del(X,L,L1).

Полная запись правила удаления элемента из списка:

del(X, [X|L], L).

del(X, [Y|L], [Y|L1]):- del (X,L,L1).

Например, для удаления из списка [1, 2, 3, 4] элемента 3, следует составить запрос:

GOAL

del(3, [1, 2, 3, 4], L),Write (L), nl.



Результат: [1, 2, 4].

П
нет


ри выполнении программы X сравнивается с первым элементом списка.

X


нет
= 3 [1 | 2, 3, 4] - первая часть правила не выполняется, 1 заносится в стек, рекурсивный вызов для хвоста [2, 3, 4]

X


да
= 3 [2 | 3, 4] - первая часть правила не выполняется, 2 заносится в стек, рекурсивный вызов для хвоста [3, 4]

X = 3 [3 | 4] первая часть правила выполняется, результирующий список принимает значение хвоста L = [4]. Элементы извлекаются из стека по одному и становятся в голову списка L.

L = [1, 2, 4]

5. Вставка символа X в список

Определим отношение ins(X, L, L1), где

X – добавляемый элемент в список

L – исходный список

L1 – список, полученный в результате вставки элемента Х в список L

Отношение ins(X, L, L1) можно определить через del(X, L1, L). Если для отношения del(X, L1, L) список L1 – исходный список, содержащий элемент Х, то для ins(X, L, L1) список L1 является результирующим. Список L, не содержащий Х, для del(X, L1, L) – результирующий, а для ins(X, L, L1) – исходный.

ins(X, L, L1): - del(X, L1, L).

Например, для вставки элемента 5 в список [1, 2, 3] необходимо составить запрос:

GOAL

ins(5, [1, 2, 3], L),Write (L), nl, fail.



Результат:

[5, 1, 2, 3]

[1, 5, 2, 3]

[1, 2, 5, 3]

[1, 2, 3, 5]

Примечание: так как отношение ins(X, L, L1) определено через del (X, L1, L), то в разделе CLAUSES должно быть описано также правило del(X, L1, L).

Литература




  1. Адаменко А., Кучуров А. Логическое программирование и Visual Prolog.-CПб., 2003.

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

  3. Ин Ц., Соломон Д. Использование Турбо-Пролога. -М., 1993.

  4. Клоксин У., Меллиш К. Программирование на языке ПРОЛОГ. -М., 1991.

  5. Макаллистер Дж. Искусственный интеллект и Пролог на микроЭВМ.- М., 1990.

  6. Нильсон Н. Искусственный интеллект. М., 1973.

  7. Попов Э.В. Экспертные системы. М., 1987.

  8. Симонс Дж. ЭВМ пятого поколения: компьютеры 90-х годов.- М.,1985 г.

  9. Тимофеев А.В. Информатика и искусственный интеллект.- М.,1992.

  10. Янсон А. Турбо-Пролог в сжатом изложении. -М.,1990.






1   2   3   4

Похожие:

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов, обучающихся по специальности «История». / А. Г. Ситдиков. Казань: Издательство Казанского государственного университета, 2008. 33 с
В этногенез народов Поволжья и Приуралья. Часть I. Истоки этногенеза финских народов: учебно-методическое пособие для студентов,...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов первого курса бакалавриата, обучающихся по направлениям 080100. 62 «Экономика» и080700. 62 «Бизнес-информатика»
Линейная алгебра. Учебно-методическое пособие для студентов первого курса бакалавриата, обучающихся по направлениям 080100. 62 «Экономика»...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие по Новой истории стран Азии и Африки Брянск, 2008 Сагимбаев Алексей Викторович. Учебно-методическое пособие по курсу «Новая история стран Азии и Африки»
Учебно-методическое пособие предназначено для студентов дневного отделения Исторического факультета, обучающихся по специальности...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов, обучающихся по специальности 07. 00. 02 Отечественная история

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов 4 курса (озо, одо) специальности 050602. 65 «Изобразительное искусство»
О. А. Бакиева. Народный костюм Севера: Учебно-методическое пособие для студентов 4 курса очной и заочной формы обучения специальности...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие Нижний Новгород 2007 ббк 40. 3
Учебное пособие предназначено для студентов, обучающихся по специальности 013400 Менеджмент и маркетинг в природопользовании
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов 1 и 2 курсов дневного и заочного отделений исторического факультета, обучающихся по специальности 07. 00. 02. отечественная история

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconМ. В. Ярощук Математическое моделирование
Учебно-методическое пособие предназначено для студентов 4 курса факультета вычислительной математики и кибернетики, обучающихся по...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие по курсу «Информационные технологии» для студентов Института дополнительного образования
Технологии ado. Net и asp. Net. Учебно-методическое пособие по курсу «Информационные технологии» для студентов Института дополнительного...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для самостоятельных занятий Допущено Министерством сельского хозяйства Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению «Агрономия»
Учебно-методическое пособие разработано на основании требований Государственного образовательного стандарта высшего профессионального...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org