На этом шаге мы приведем решения некоторых задач с использованием рекурсии.
Структура текста ваших программ для их выполнения с помощью интерпретатора muLISP85:
; -------------------------------------------------------- ; Условие вашей задачи ; -------------------------------------------------------- (DEFUN Имя_вашей_функции (LAMBDA (Аргументы_вашей_функции) Тело функции )) (RDS)
Для загрузки ваших функций в интерпретатор muLISP85 используйте функцию RDS следующим образом: (RDS Имя_файла.Расширение_файла).
Демонстрационные примеры
Пример 1.
(DEFUN SUMMA (LAMBDA (X Y)
(+ X Y)
))
; ---------------------
(DEFUN ADD1 (LAMBDA (NUM)
; Функция инкремента
(+ NUM 1)
))
; ---------------------
(DEFUN SUB1 (LAMBDA (NUM)
; Функция декремента
(- NUM 1)
))
; ------------------------
(DEFUN PROCENT (LAMBDA (A B)
; Функция возвращает A процентов от числа B
(/ (* A 100) B)
))
; --------------------
(DEFUN ABS (LAMBDA (NUM)
; Функция ABS возвращает абсолютное значение аргумента NUM
(COND ( (MINUSP NUM) (- NUM))
( T NUM )
)
))
; --------------------
(DEFUN MAX (LAMBDA (M N)
; Функция MAX возвращает большее из двух чисел
(COND ( (> M N) M )
( T N )
)
))
; ----------------------
(DEFUN KPLUS (LAMBDA (X Y)
; Фрагмент комплексной арифметики
; X и Y - списки вида (x y)
(LIST (+ (CAR X) (CAR Y))
(+ (CADR X) (CADR Y)) )
))
Пример 2. Вычислить факториал целого числа X. Поставленная задача решается с помощью функции, которая принимает значение, равное единице при равенстве аргумента единице или нулю, а во всех остальных случаях равна произведению аргумента на значение этой же функции от аргумента, уменьшенного на единицу. Решение:
(DEFUN FACT (LAMBDA (X)
(COND ( (ZEROP X) 1 )
( T (* X (FACT (- X 1))) )
)
))
Изобразим процесс нисходящей рекурсии графически:
(FACT 3)
--------
V
(* 3 (FACT 2))
---------
V
(* 2 (FACT 1))
---------
V
(* 1 (FACT 0))
---------
V
1
А теперь изобразим процесс "выхода из рекурсии":
(* 3 (* 2 (* 1 1))) -> 6
Пример 3. Вычислите значение функции, заданной формулой: F(N) = If N>100 then N-10 else F(F(F(N+21))). Решение:
(DEFUN FN (LAMBDA (N)
(COND
( (> N 100) (- N 10) )
( T (FN (FN (FN (+ N 21)))) )
)
))
Тестовые примеры:
$ (FN 94)
91
$ (FN 100)
91
$ (FN 123)
113
Пример 4. Определить функцию COPY, которая возвращает копию данного списка. Решение:
(DEFUN COPY (LAMBDA (LST) ; Функция для копирования самого ; "верхнего" уровня списка LST (COND ( (NULL LST) NIL ) ( T (CONS (CAR LST) (COPY (CDR LST))) ) ) ))
Пример 5. Определите функцию, удаляющую из списка последний элемент. Решение:
(DEFUN DROPLAST (LAMBDA (L)
(COND
( (NULL L) NIL )
( (NULL (CDR L)) NIL )
( T (CONS (CAR L) (DROPLAST (CDR L))) )
)
))
Пример 6. Построить предикат, который проверяет, является ли его аргумент списком (возможно, пустым), составленным лишь из атомов. Решение:
(DEFUN ATOMLIST (LAMBDA (X)
(COND
( (NULL X) T )
( (ATOM X) NIL )
( (ATOM (CAR X)) (ATOMLIST (CDR X)) )
( T NIL )
)
))
Пример 7. Определите функцию, удаляющую из списка первое вхождение данного элемента на верхнем уровне. Решение:
(DEFUN DELETEFIRST (LAMBDA (A L)
(COND
( (NULL L) NIL )
( (EQUAL (CAR L) A) (CDR L) )
( T (CONS (CAR L) (DELETEFIRST A (CDR L))) )
)
))
Пример 8. Определите функцию, удаляющую из списка каждый второй элемент. Решение:
(DEFUN EVERYSECOND (LAMBDA (L)
(COND
( (NULL L) NIL )
( (NULL (CDR L)) L )
( T (CONS (CAR L) (EVERYSECOND (CDDR L))) )
)
))
Пример 9. Определить наибольший элемент одноуровневого числового списка LST. Решение:
(DEFUN MAXIM (LAMBDA (LST)
(COND
( (NULL LST) NIL )
( (EQ (LENGTH LST) 1) (CAR LST) )
( T (MAX2 (CAR LST) (MAXIM (CDR LST))) )
)
))
; ---------------------
(DEFUN MAX2 (LAMBDA (X Y)
(COND
( (> X Y) X )
( T Y )
)
))
Какие исправления необходимо сделать в программе, чтобы получить наименьший
элемент?
Пример 10. Определите функцию, которая возвращает список, у которого первый элемент является суммой, а второй - произведением элементов данного списка LST. Решение:
(DEFUN SP (LAMBDA (LST)
(LIST (SUM LST) (PR LST))
))
; --------------------
(DEFUN SUM (LAMBDA (LST)
; Сумма элементов числового списка
(COND
( (NULL LST) 0 )
( T (+ (CAR LST) (SUM (CDR LST))) )
)
))
; -------------------
(DEFUN PR (LAMBDA (LST)
; Произведение элементов числового списка LST
(COND
( (NULL LST) 1 )
( T (* (CAR LST) (PR (CDR LST))) )
)
))
Тестовые примеры:
$ (SP '(1 2 3 4))
(10 24)
$ (SP '())
(0 1)
$ (SP '(1))
(1 1)
$ (SP '(0 1))
(1 0)
Пример 11. Определить количество элементов, равных максимальному элементу числового списка. Решение:
(DEFUN AAA (LAMBDA (LST)
(KOL LST (MAXIM LST))
))
; ----------------------
(DEFUN KOL (LAMBDA (LST M)
(COND
( (NULL LST) 0 )
( (EQ (CAR LST) M) (ADD1 (KOL (CDR LST) M)) )
( T (KOL (CDR LST) M) )
)
))
; ----------------------
(DEFUN MAXIM (LAMBDA (LST)
; Функция возвращает максимальный элемент списка LST
(COND
( (NULL LST) NIL )
( (EQ (LENGTH LST) 1) (CAR LST) )
( T (MAX2 (CAR LST) (MAXIM (CDR LST))) )
)
))
; ---------------------
(DEFUN MAX2 (LAMBDA (X Y)
; Функция возвращает наибольшее из двух чисел X и Y %
( ((> X Y) X ) Y )
))
; ---------------------
(DEFUN ADD1 (LAMBDA (NUM)
; Функция, увеличивающая аргумент на 1
(+ NUM 1)
))
Тестовые примеры:
$ (AAA '(1 2 3 4 5))
1
$ (AAA '(2 2 3 4 5))
2
$ (AAA '(5 5 5 5 5))
5
$ (AAA '())
0
Пример 12. В числовом списке найдите наибольший элемент и номер первого такого элемента, если их несколько. Решение:
(DEFUN MAIN (LAMBDA (LST)
(POSITION (MAXIM LST) LST)
))
; ----------------------
(DEFUN MAXIM (LAMBDA (LST)
; Функция возвращает наибольший элемент списка
(COND
( (NULL LST) NIL )
( (EQ (LENGTH LST) 1) (CAR LST) )
( T (MAX2 (CAR LST) (MAXIM (CDR LST))) )
)
))
; ---------------------
(DEFUN MAX2 (LAMBDA (X Y)
; Функция возвращает наибольшее из двух чнсел X и Y
(COND
( (> X Y) X )
( T Y )
)
))
; ----------------------------
(DEFUN POSITION (LAMBDA (X LST)
; Функция POSITION возвращает положение атома X в
; одноуровневом списке LST (первый элемент имеет
; номер 1). Если элемента в списке нет, то функция
; возвращает 0.
(COND
( (NULL LST) 0 )
( (EQ X (CAR LST)) 1 )
( (MEMBER X LST)
(+ 1 (POSITION X (CDR LST))) )
( T 0 )
)
))
Тестовые примеры:
$ (MAIN '(6 8 3 5 8 4 2 8))
2
$ (MAIN '(6 1 3 5 8 4 2 8))
5
Пример 13. Построить функцию, которая удаляет из списка все совпадающие с данным атомом (в смысле EQ) элементы и возвращает список из всех оставшихся элементов. Решение:
(DEFUN REMBER (LAMBDA (X LST)
(COND
( (NULL LST) NIL )
( (EQ X (CAR LST)) (REMBER X (CDR LST)) )
( T (CONS (CAR LST) (REMBER X (CDR LST))) )
)
))
Тестовые примеры:
$ (REMBER 5 '(4 6 5 7 2 5 9 5 87))
(4 6 7 2 9 87)
$ (REMBER 12 '(1 86 12 6 7 12 0)
(1 86 6 7 0)
Пример 14. Определить функцию CDRN, такую что (CDRN N L) будет эквивалентна функции (CDDD...DR L), в имени которой имеется N букв D. Решение:
(DEFUN CDNR (LAMBDA (N LST)
(COND
( (EQ N 0) LST )
( (EQ N 1) (CDR LST) )
( T (CDNR (- N 1) (CDR LST)) )
)
))
Тестовые примеры:
$ (CDNR 3 '(1 2 3 4 5))
(4 5)
$ (CDNR 3 '(1 2 (3 4 5)))
NIL
$ (CDNR 3 '(1 2 3 (4 5) 6))
((4 5) 6)
Пример 15. Напишите функцию, зависящую от трех аргументов U, N и V, вставляющую в список U, начиная с N-го элемента список V. Например:
$ (MAIN '(1 2 3) 2 '(4 5 6)) (1 2 4 5 6 3)Решение:
(DEFUN MAIN (LAMBDA (LST1 N LST2)
(COND
( (EQ (LENGTH LST1) N) (APPEND LST1 LST2) )
( T (APPEND (FIRSTN LST1 N) (APPEND LST2
(LASTN LST1 (- (LENGTH LST1) N)))
)
)
)
))
; -------------------------
(DEFUN FIRSTN (LAMBDA (LST N)
; Выделяет в список первые N элементов списка LST
(COND ( (EQ N 1) (LIST (CAR LST)) )
( T (CONS (CAR LST) (FIRSTN (CDR LST)
(- N 1))))
)
))
; ------------------------
(DEFUN LASTN (LAMBDA (LST N)
; Выделяет в список последние N элементов списка LST
(REVERSE (FIRSTN (REVERSE LST) N))
))
; -----------------------------
(DEFUN APPEND (LAMBDA (LST1 LST2)
; Составляет список из первых N элементов списка LST1
; и вставляемого списка LST2
(COND ( (NULL LST1) LST2 )
( T (CONS (CAR LST1)
(APPEND (CDR LST1) LST2) ))
)
))
Задачи для самостоятельного решения
- Выбрать из числового списка LST все элементы, делящиеся на 3, и сформировать из них список.
- Вычислить количество положительных, отрицательных и нулевых элементов в числовом списке LST.
- Опишите функцию, которая вычисляет произведение элементов числового списка.
- Опишите функцию, которая преобразует числовой список в список, каждый элемент которого на единицу меньше.
- Определить функцию, возвращающая список, у которого первый элемент является суммой квадратов, а второй - произведением квадратов элементов числового списка LST.
- Проверьте, нет ли в данном числовом списке элемента, который равен сумме первого и последнего элементов.
- Определите функцию (FIB N), вычисляющую N-й элемент последовательности Фибоначчи. Числа Фибоначчи определяются так: F1=1, F2=1, Fn=Fn-1+Fn-2 для n>=3.
- Определить функцию COUNTG, такую, что (COUNTG L N) возвращает количество атомов-чисел из списка L больших, чем N. Предполагается, что L не имеет подсписков и что все его атомы - числа. Так, если X есть (2 8 8 7 -4), то (COUNTG X 7) возвращает 2.
- В списке переставьте первый и последний элементы местами.
- Напишите функцию, осуществляющую циклическую перестановку элементов одноуровневого списка, при которой первый элемент списка становится последним.
- Написать функцию для поиска таких элементов числового списка, которые заключены между целыми числами H и L.
- Напишите функцию INRANGE, такую, что (INRANGE V MAXIMUM MINIMUM) возвращает T, если V лежит между MAXIMUM и MINIMUM, включая границы, и NIL в противном случае. Предполагается, что V - числовой атом, MAXIMUM и MINIMUM - соответственно наибольший и наименьший элементы числового списка.
- Определить функцию (CDRN N L), эквивалентную функции (CDDD...DR L), в имени которой имеется N букв D.
- Определить функцию DOMINATE с двумя списками, равными в смысле EQUAL, в качестве аргументов. Функция (DOMINATE L M) должна возвращать T, если каждый атом из L больше, чем соответствующий атом из M, и NIL в противном случае (все атомы - числовые).
- Напишите функцию REVERSE2, которая соединяет два списка, причем оба списка
должны быть обращены. Например:
$ (REVERSE2 ((A B) (C D))) (B A D C)
- Построить функцию, которая удаляет из числового списка все совпадающие с заданным числовым атомом элементы и возвращает в качестве значения список из квадратов оставшихся элементов.
- Написать функцию DELETE, которая удаляет N-й элемент списка LST.
- Напишите функцию INSLIST, зависящую от трех аргументов N, U и
V, вставляющую в список U, начиная с N-го элемента, обращенный список
V. Например:
$ (INSLIST (2 (A B) (C D))) (A D C B)
- Вычислить произведение сумм положительных и отрицательных элементов одноуровневого числового списка LST.
- Проверьте, есть ли среди элементов данного числового списка отрицательные. Если они есть, то постройте новый список, состоящий из отрицательных элементов исходного списка, записанных в том же порядке.
- В числовом списке каждый элемент равен 0, 1 или 2. Переставить элементы списка так, чтобы сначала располагались все нули, затем все единицы и, наконец, все двойки (сортировать список нельзя!).
- Вычислите сумму элементов числового списка.
- Найти максимальный элемент числового списка.
- Найти максимальный элемент среди отрицательных элементов числового списка.
- Найти минимальный элемент среди положительных элементов числового списка.
- Определить количество элементов, равных минимальному элементу числового списка.
- В числовом списке требуется найти наименьший элемент и номер первого такого элемента, если их несколько.
- Осуществите циклическую перестановку элементов списка: первый элемент должен стать вторым, второй - третьим и т.д., последний - первым.
- Определить, является ли сумма элементов числового списка четным числом.
- Для целых чисел A,B,C>0 функция REM (A,B,C), вычисляющая остаток
от деления AB на C, определяется рекурсивно:
REM (A*A,B/2,C), для A<C,B>2, B-четное; MOD (A*REM(A*A,(B-1)/2,C)), REM(A,B,C) = для A<C,B>=3, B-нечетное; A, для A<C, B=1; REM (MOD (A,C),B,C), для A>=C.Написать программу для вычисления REM(A,B,C). - Составьте функцию, записывающую элементы списка в порядке, обратном к данному.
- Определить операции сложения и умножения над кватернионами.
- Напишите функцию для вычисления числа сочетаний из n элементов по m.
- Напишите функцию, вычисляющую N!!.
- Определите функцию, которая возвращает последний атом списка.
- Определите функцию, удаляющую из списка каждый третий элемент.
- Определить, упорядочены ли элементы в одноуровневом списке, содержащем латинские буквы, по алфавиту.
На следующем шаге мы поговорим о парадигмах программирования.
