Задание на лабораторную работу. 1. Определить функции, реализующие работу с очередями

1. Определить функции, реализующие работу с очередями. Вы должны реализовать следующие функции:

1) make-queue() – строит очередь, не содержащую ни одного элемента;

2) endqueue(item q) – добавляет элемент item в конец очереди q;

3) decqueue(q) – удаляет первый элемент из очереди q;

(для реализации удаления можно воспользоваться встроенной функцией pop – взять элемент из стека)

Например,

>(setf L '(1 2 3))

(1 2 3)

>(pop L)

>L

(2 3)

4) queue-contents(q) – возвращает содержимое очереди q;

5) front(q) – возвращает первый элемент очереди q.

Определенной Вами очереди должна соответствовать следующая диаграмма списочных ячеек: на этой диаграмме car является последним элементом очереди, а cdr является содержимым очереди, представленным в виде списка.

Примеры:

>(setf queue (make-queue));создали очередь queue

#l=(#l#)

>(endqueue 'a queue);добавили элемент 'a в очередь

(#l=(A). #l#)

>(endqueue 'b queue);добавили элемент 'b в очередь

(#l=(B) A. #l#)

>(front queue);отобразили первый элемент очереди

A

>(decqueue queue);удалили первый элемент

(#l=(A). #l#)

>(queue-contents queue)

(B);отобразили содержимое очереди queue

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

2. Определите функциональный предикат each1(p l), который истинен в том и только том случае, когда, являющийся функциональным аргументом предикат p истинен для всех элементов списка l.

Примеры:

>(each1 'atom '(a b c))

T

>(each1 'numberp '(1 2 a 3))

NIL

3. Определите функцию (count-if p l), подсчитывающую количество элементов списка l, которые обладают свойством, наличие которого проверяется предикатом p.

Примеры:

>(count-if 'numberp '(1 2 a 3 b c))

4. Напишите программу генератора чисел Фибоначчи (1, 1, 2, 3, 5,...).

5. Напишите функцию, которая получает матрицу в качестве аргумента и возвращает транспонированную матрицу. (Ваша функция должна работать с матрицами любой размерности). Транспонирование матрицы – это результат отображения матрицы относительно ее диагонали.

Пример:

>(transpose '((a b c) (d e f) (g h i)))

((A D G) (B E H) (C F I))

Для выполнения єтого задания используйте функцию mapcar. Матрицу можно представить как список списков.

6. Определите форму, соответствующую синтаксису оператора IF Фортрана: (FIF тест отр нуль полож).

Примеры:

>(setq x 3)

>(fif x (print 'negative)

(print 'zero)

(print 'positive))

POSITIVE

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

1. Вычислите значения следующих вызовов:

a) (apply ’list ’(a b))

b) (funcall ’list ’(a b))

c) (funcall ’apply ’list ’(a b))

d) (funcall ’list ’apply ’(a b))

e) (funcall ’funcall ’funcall ’list ’list ’(a b))

2. Определите функционал FUNCALL через функционал APPLY.

3. Реализуйте рекурсивную функцию my-find, которая в качестве аргументов получает предикат и список элементов, и возвращает первый элемент списка, который удовлетворяет предикату. Если в списке нет элементов, удовлетворяющих предикату, то ответом должно быть NIL.

Пример:

>(my-find ‘numberp ‘(a b 2 C))

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

Примеры:

>(subsets nil)

(NIL)

>(subsets ’(A B C))

(NIL (A) (B) (C) (A B) (A C) (B C) (A B C))

5. Определите функционал (MAPLIST fn список) для одного списочного аргумента.

6. Напишите программу генератора, порождающего следующую последовательность: (A), (B A), (A B A), (B A B A) …

7. Определите в виде макроса форму (REPEAT e UNTIL p), соответствующую оператору REPEAT языка Паскаль.

Лабораторная работа №7

Методы поиска решений в пространствах состояний