Лекции в ворде (1086314), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

(A B)

$ (setq конец '(c d))

(C D)

$ (setq результат (append начало конец))

(A B C D)

APPEND создает копию списка, являющегося первым аргументом. Если список НАЧАЛО, например, содержит 1000 элементов, а КОНЕЦ – один, то во время вычисления будет создано 1000 новых ячеек, хотя нужно добавить лишь одну. Если не существенно, что значение переменной НАЧАЛО изменится, то вместо функции APPEND можно использовать функцию NCONC (concatenate). Эта функция выполняет то же самое, что и APPEND, но склеивает два списка, не создавая копии. При этом меняется указатель в поле CDR последней ячейки списка, являющегося первым аргументом, на начало списка, являющегося вторым аргументом

$ начало

(A B)

$ конец

(C D)

$ (setq изменится (append конец начало)) ; это значение заметно изменится

(C D A B)

$ (setq результат1 (nconc начало конец)) ; разрушающее объединение

(A B C D)

$ начало

(A B C D)

$ конец

(C D)

$ изменится

(C D A B C D)

Использовав NCONC, мы избежали копирования списка НАЧАЛО, однако в качестве побочного эффекта мы получили изменение значения переменной НАЧАЛО, изменились и другие структуры, например, значение символа ИЗМЕНИТСЯ.

Упражнения

1. Нарисуйте следующие списки при помощи списочных ячеек и стрелок:

а) (а);

б) (a (b (c) d));

в) (nil (b . c) . d)

1. Каковы будут значения выражений (RPLACA x x) и (RPLACD x x), если а) x='(a b); б) x='(a).

2. Вычислите значения следующих выражений:

1. (replacd '(a) 'b);

б) (replaca '(a) 'b);

в) (replacd (cddr '(a b d)) 'c)

г) (replacd '(nil) '(nil))

Тема 7. Свойства символа.

Краткое изложение содержания темы 7 можно найти в методических указаниях к выполнению лабораторных работ. Там же изложен материал о свойствах символа.

В Приложении приведены дополнительные полезные функции и конструкции, которые в основном тексте не освещались.

Тема 8. Другие формы рекурсии.

• Параллельная рекурсия

Рекурсия называется параллельной, если тело определения функции f содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивными вызовами функции f:

(defun f...

... (g ... (f ...) ... (f ... ) ...)... )

Пример 1. Обращение элементов списка и его подсписков независимо от их места и глубины вложенности, Обратите внимание, что в теле определяемой функции вызывается функция append, оба аргумента которой представляют рекурсивные вызовы определяемой функции. Иными словами имеет место параллельная рекурсия. Функция обращает голову списка, формирует из него список и присоединяет к нему спереди обращенный хвост::

$ (defun обрати (l)

cond

((atom l) l)

((null (cdr l))

(cons (обрати (car l) nil))

(t (append (обрати (cdr l)) (обрати(cons (car l) nil))))))

ОБРАТИ

$ (обрати '(a (b c) (d (e (f g)))))

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

Пример 2. Преобразовать список, элементы которого представляют вложенные подсписки, в виде одномерного линейного списка.

$ (defun список_в_линию (l)

cond

((null l) nil)

((atom l) (cons (car l) nil)l)

(t (append

(список_в_линию (car l)))) ;сначала голову

(список_в_линию (cdr l)))))) ; затем хвост

СПИСОК_В_ЛИНИЮ

$ (список_в_линию '(a ((b c (d))))

(A B C D )

 Взаимная рекурсия

Рекурсия называется взаимной, если в определении функции f вызывается некоторая функция g, которая в свою очередь содержит вызов функции f:

(defun f ...

... (g ...) ...)

(defun g ...

... (f ...) ... )

Пример 3. Решим ту же задачу, что и в примере1, но с помощью вспомогательной функции:

$ (defun обрати1 (l)

(cond ((atom l) l)

(t (переставь l nil))))

ОБРАТИ1

$ (defun переставь (l результат)

(cond ((null l) результат)

(t (переставь (cdr l)

(cons (обрати1 (car l))

результат))))

ПЕРЕСТАВЬ

$ (обрати1 '('(a (b c) (d (e (f g)))))

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

В заключение этого раздела рассмотрим трехуровневую вложенную рекурсию. Целью задачи – сортировка списка. Здесь определяются три функции: ВСТАВЬ(x k z), где х – элемент, вставляемый в список k на место, определяемое порядком z; РАНЬШЕ-Р(x y z) проверяет, находится ли элемент X раньше элемента Y, в соответствии с порядком следования, установленным списком Z; СОРТИРУЙ(k z) – упорядочивает список l в соответствии с порядком z.

$ (defun вставь (x k порядок)

(cond ((null k) (list x))

((раньше-р x (car k) порядок)

(cons x k))

(t (cons (car k)

(втавь x (cdr k) порядок)))))

ВСТАВЬ

$ (defun раньше-р (x y порядок)

(cond

((null порядок) nil)

((eq x (car порядок)) t) ; x раньше

((eq y (car порядок)) nil) ; y раньше

(t (раньше-р x y (cdr порядок)))))

РАНЬШЕ-Р

$ (раньше-р 'b 'e '(a b c d e))

T

$ (втавь 'b '(a c d) '(a b c d e))

(A B C D)

$ (defun сортируй (l порядок)

(cond

((null l) nil)

(t (вставь (car l)

сортируй (cdr l) порядок)

порядок)))

СОРТИРУЙ

$ (сортируй '(c a b) '(a b c d))

(A B C )

Упражнения

1. Определить функцию МНОЖЕСТВО(lst), преобразующую список в множество. В определении использовать конструкцию cond.

Ћ! Множество – это список, в котором отсутствуют одинаковые элементы. Пример: список – lst=(a b c a)множество – set=(a b c) Функция МНОЖЕСТВО вызывает в своем теле функцию member(x, lst), определяющую принадлежность атома х списку lst:

а. Если список пуст – null, возврат nil.

б. Если атом х совпадает (eql) с car от списка, то возврат Т, т.е. атом х является первым элементом списка, иначе

в. Атом х принадлежит хвосту списка – cdr(lst)

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

2. Определить функцию, вычисляющую глубину списка.

Ответы к некоторым упражнениям

К теме 2.

1.

2.

3.

4.

5.

К теме 3

1а. В левом -выражении х – связанная переменная, у – свободная; в правом – у -связанная переменная.

2. Два: первое вхождение у свободно, второе – связано.

3.а) Fy;

б) y;

в) (х.(у. у х)z)v[v|x]((y.y x)z) (у. у v)z

[z|y](y v) z v

К теме 4.

п. 4.2

1a (car(cdr (car x)))=(caddr x)

1б. (car(cdr (car (cdr x)))=(cadadar x)

1в. (car (cdr (cdr (car (cdr (car (cdr (car x))))))))=(caddar (cdadar x))

2a. (NIL ЭТО ПУСТОЙ СПИСОК)

2б. ((nil) nil)

2в. (Ф И)

2г. ((A B) (CAR (C D)))

3. в, г

п 4.3

1а Х=Y, Y=Y

1б. X=Y, Y=X.

2a. B

2б С.

3а. (CAR (QUOTE (A B C))

3б. A.

3в. (EVAL (DUOTE (QUOTE QUOTE)))

4. $ (setq spis '(a b c d))

(A B C D)

$ (setq spis1 (cons 'f spis))

(F A B C D)

п.4.4.

1а.((lambda (x)(cons x nil)) 'y)

1б.((lambda (x )(list x))(list nil))

2а. (defun fact (n)

((eql n 0) 1))

(* n(fact(-n 1))))

2б. (defun fib (n)

((zerop n) 1)

((eql n 1) 1)

(+ (fib (- n 1))(fib (- n 2))))

3. (defun last_element (lst)

((null lst) nil)

((null (cdr lst))(car lst)

(last_element (cdr lst)) )

4. (defun append (lst1 lst2)

((null lst1) lst2)

((cons (car lst1)(append (cdr(lst1) lst2)))

1. (defun member (x lst)

((null lst) nil)

((eql x (car lst)) t)

(member x (cdr lst)) )

6. (defun rember (obj lst)

((null lst) nil)

(eql obj (car lst)) (cdr lst))

(cons ((car lst)(rember obj (cdr lst))) ).

К теме 5

1. (defun пары (lst) ; из входного списка (a b c d ...) поучается

((cond ; список ((a b) (c d) ...)

((null lst) nil)

((null (cdr lst)) nil)

(t (cons(list (car lst) (cadr lst)(пары (cddr lst))))))

1. (defun произведение (n m)

(if (=n 1)m)

(+ произведение(- n 1)m))))

1. (defun power1(x n)

(if (= n 1) x

(* x (power1 x (- n 1)))) )

1. (defun power (n m) ;результат вычисления возвращается через

(setq result 1) ; локальную переменную rezult

(loop

((zerop m) result)

(setq res (* n result))

(setq m (- m 1)) ) )

К теме 6.

1а.

1б.

1в.

2а. ((A B) B) и (А А В).

2б. ((A)) и (А А).

3а. (А . В); б) (В); в) (D . C); г) (NIL).

К теме 8.

1. (defun множество (lst) ; преобразование списка в множество.

(cond ; Множество – список, в котором

((null lst) nil) ; отсутствуют одинаковые

((member (car lst)(cdr lst) ; элементы. Функция member(x,lst)

(множество (cdr lst))) ; определяет принадлежность х

(t (cons (car lst) ; атома х списку lst (определение

(множество (cdr lst))))) ) ; см. §4.4, упражнение 5).

2.(defun атомов (x) ;количество атомов в списке.

(cond ((null x) 0)

((atom (car x))

(+ 1 (атомов (cdr x))))

(t (+ (атомов (car x))

(атомов (cdr x))))) ).

3. (defun глубина (x) ;глубина списка.

(cond ((atom x) 1)

(t (max1 (+ 1 (глубина (car x))) (глубина (cdr x))))) ).

(defun max1 (x y) ;функция, определяющая

(if (> x y) x y)) ;максимальное из двух чисел

Приложение 1

Краткое введение в систему muLISP.

Интерпретатор содержится в файле mulisp.com .

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

Если здесь не указан тип вашей ЭВМ, выберите тип "2".

После запуска на экран выдается приглашение к диалогу в виде "$". Когда пользователь заканчивает ввод какого-либо выражения или вызов функции, то интерпретатор вычисляет и выдает значение этого выражения:

$ (+ 2 3)

5

$ (* (+ 1 2)(+ 3 4))

21

Для блокировки вычисления выражения используется апостроф ('):

$ '(+ 2 3)

(+ 2 3)

$ ( CAR '(+ 2 3))

Характеристики

Список файлов лекций