- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
- Определить функцию для проверки упорядоченности бинарного дерева.
Вариант 3
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, реализующую головоломку «Ханойские башни».
- Определить функцию для вывода бинарного дерева на экран в виде дерева.
Вариант 4
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
- Определить функцию для вычисления глубины бинарного дерева (глубина пустого дерева равна 0, глубина одноузлового дерева равна 1).
Вариант 5
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
- Определить функцию для подсчета количества вершин бинарного дерева, значения которых лежат в определенном диапазоне.
Вариант 6
- Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).
- Определить функцию, вычисляющую, сколько всего атомов в списке (списочной структуре).
- Определить функцию для нахождения среднего арифметического листьевых вершин бинарного дерева.
Вариант 7
- Определить рекурсивную функцию для удаления последнего элемента списка.
- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
- Определить функцию для проверки упорядоченности бинарного дерева.
Вариант 8
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, реализующую головоломку «Ханойские башни».
- Определить функцию для вывода бинарного дерева на экран в виде дерева.
Вариант 9
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
- Определить функцию для вычисления глубины бинарного дерева (глубина пустого дерева равна 0, глубина одноузлового дерева равна 1).
Вариант 10
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
- Определить функцию для подсчета количества вершин бинарного дерева, значения которых лежат в определенном диапазоне.
Содержание отчета:
- титульный лист;
- задание;
- исходный текст;
- выводы по работе.
Методические указания:
Предложения prog1, prog2, progN
(progX form1 form2 … formN)
Назначение: выполнение последовательных вычислений.
Пример:
>(progn (setq x 2) (setq y (* 3 x)))
6
Предложение cond
(cond (predicate1 form1) (predicate2 form2) … (predicateN formN))
Назначение: выполнение ветвления.
Пример: функция, определяющая тип выражения (пустой список, атом или список).
>(defun deftype(arg)
(cond ((null arg) ‘empty) ((atom arg) ‘atom) (t ‘list)))
DEFTYPE
>(deftype ‘(a b c))
LIST
>(deftype (atom ‘(a t o m)))
EMPTY
Предложение if
(if (condition) thenform elseform)
Назначение: выполнение ветвления.
Пример:
>(setq x ‘(a b c))
(A B C)
>(if (atom x) ‘atom ‘list)
LIST
Предложение do
(do ((var1 value1) (var1 value1) … (var1 value1))
(endcondition form11 form12)
form 21 form 22)
Назначение: выполнение циклических вычислений.
Пример: вычисление суммы целых чисел от n до 0.
>(defun count (n)
(do ((result n)) ;;начальное значение
((= n 0) result) ;;условие окончания цикла
(setq n (- n 1))
(setq result (+ result n))
)
)
COUNT
>(count 5)
15
Простая рекурсия
Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Пример: построение копии списка.
>(defun listcopy (list)
(cond ((null list) nil) ;;граничное условие
(t (cons (car list) (listcopy (cdr list)))))) ;;рекурсия
LISTCOPY
>(listcopy ‘(a b c))
(A B C)
Трассировка программы
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения.
Для того, чтобы включить трассировку, можно воспользоваться следующей директивой:
(trace function)
Назначение: включает режим трассировки.
Пример:
>(trace listcopy)
(LISTCOPY)
>(listcopy '(a b))
Entering: LISTCOPY, Argument list: ((A B))
Entering: LISTCOPY, Argument list: ((B))
Entering: LISTCOPY, Argument list: (NIL)
Exiting: LISTCOPY, Value: NIL
Exiting: LISTCOPY, Value: (B)
Exiting: LISTCOPY, Value: (A B)
(A B)
(untrace function)
Назначение: отключает режим трассировки.
Пример:
>(untrace listcopy)
NIL