WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Засоби та принципи програмування на Ліспі - Реферат

Засоби та принципи програмування на Ліспі - Реферат

value)
((ZEROP n) (POP lst) (PUSH value lst))
(CONS (CAR lst) (CHANGE (CDR lst) (- n 1) value)) )
Тоді функція MULTPOL, яка написана на Паскалі, на Ліспі набуває наступного вигляду:
(DEFUN MULTPOL (lst1 lst2)
(SETQ k (LENGTH lst1) l (LENGTH lst2) lst3 (GEN0 (+ k l)))
(SETQ i 0)
(POP lst3)
(LOOP
((= i k) lst3)
(SETQ j 0)
(LOOP
((= j l))
(SETQ lst3 (CHANGE lst3 (+ i j) (+ (MAS lst3 (+ i j)) (* (MAS lst1 i) (MAS lst2 j)))) )
(INCQ j) )
(INCQ i) ) )
Середовище muLisp має також вмонтовану функцію MAKE-LIST, яку можна використовувати для створення списків заданого розміру. Функція (MAKE-LIST n об'єкт список) утворює список з n елементів, кожний з яких приймає значення об'єкту, приєднані до списку. Якщо не задано перший аргумент, то по замовченню n = 0. Якщо другий аргумент не задано, то вважається об'єкт = NIL.
$ (MAKE-LIST 3 '(q w)) $ (MAKE-LIST 4) $ (MAKE-LIST 3 5 '(2 3))
((q w)(q w)(q w)) (NIL NIL NIL NIL) (5 5 5 2 3)
Наведену функцію можна визначити наступним чином (ім'я змінено на MAKE-LST):
(DEFUN MAKE-LST (N OBJ LST)
((AND (INTEGERP N) (PLUSP N))
(CONS OBJ (MAKE-LIST (SUB1 N) OBJ LST)) )
LST )
Функця (OBLIST) що не має аргументів, утворює та повертає список активних на поточний момент символів у системі. Символи розташовані в тому порядку, в якому вони прочитані або згенеровані строковими функціями: нові символі розташовані зліва від старих.
4. Породження комбінаторних об'єктів.
Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.
1. Надрукувати всі послідовності довжини n з цифр 0,1. (P11 n).
Функція P11 викликається з одним аргументом n, аргумент lst - допоміжний.
(DEFUN p11 (n lst) (DEFUN p13 (n lst)
((ZEROP n) (PRIN1 lst) (TERPRI)) ((ZEROP n) (PRN13 lst) (TERPRI))
(P11 (- n 1) (CONS 0 lst)) (P13 (- n 1) (CONS 0 lst))
(P11 (- n 1) (CONS 1 lst)) ) (P13 (- n 1) (CONS 1 lst)) )
2. Надрукувати всі послідовності довжини k з чисел 1..n. (P12 k n).
Друкуватимемо послідовності у лексикографічному порядку. За допомогою функції (GEN1 n) згенеруємо список з n елементів, кожен з яких дорівнює 1. Список lst зберігатиме поточну перестановку. Функція (NEXT lst n) знаходить перестановку, яка буде наступною після lst. Функція P12BEST є найкращим рекурсивним розв'язком цієї задачі.
(DEFUN GEN1 n)
((ZEROP n) NIL)
(CONS 1 (GEN1 (- n 1))) )
(DEFUN NEXT (lst n)
((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))
((NULL (CDR lst)) NIL)
(CONS 1 (NEXT (CDR lst) n))
Шукана функція має вигляд:
(DEFUN P12 k n)
(SETQ lst (GEN1 k))
(LOOP
(( (CAR c) k))
(P12BEST (- n 1) k (CONS (CAR c) lst) c)
(SETQ c (CONS (+ 1 (CAR c)) (CDR c)))
) (POP c) )
3. Надрукувати всі підмножини множини {1..n}. (P13 n).
Оскільки всі підмножини будь-якої множини {1..n} перебувають у взаємно однозначній відповідності зі всіма послідовностями з 0 та 1 довжини n, то ця задача зводиться до задачі 1.1. Функція (P13 n) наведена в 1.1. Тільки замість виведення списку з 0 та 1 необхідно виводити номери всіх елементів списку, які дорівнюють 1. Функція (PRN13 lst) виводить необхідні номери елементів.
(DEFUN PRN13 (lst)
(SETQ i 0)
(LOOP
((NULL lst))
(INCQ i)
(IF (= 1 (POP lst)) (PROGN (PRIN1 i) (SPACES 1)))
) )
4. З перестановки (1 2 3 ... n ) необхідно отримати перестановку (n ... 2 1) за найменшу кількість кроків. Кроком будемо називати обмін місцями довільних двох сусідніх чисел. Наприклад, з перестановки (1 3 4 2) можна отримати одну з наступних: (3 1 4 2), (1 4 3 2), (1 3 2 4).
Нехай lst - поточна перестановка. Опишемо алгоритм, за яким будемо знаходити наступну перестановку. Для цього, переглядаючи список lst зліва направо, знайдемо такі два числа що знаходяться поруч, де перше менше за друге. Поміняємо їх місцями та викличемо рекурсивно функцію move_per над отриманим списком.
(DEFUN move_per (lst)
(PRIN1 lst) (TERPRI 1)
(SETQ cur NIL)
(LOOP
((ATOM (CDR lst)))
(( n (CAR tree)) (cons (car tree) (cons (cadr tree) (insel n (cddr tree)))))
(cons (car tree) (cons (insel n (cadr tree)) (cddr tree))) )
(DEFUN INSL (lst tree)
((NULL lst) tree)
(SETQ tree (insel (car lst) tree))
(INSL (CDR lst) tree) )
Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) - обхід згори вниз, PLR (Print Left-Right) - обхід зліва направо.
(DEFUN PUD (tree) (DEFUN PLR (tree)
((NULL tree)) ((NULL tree))
(PRIN1 (CAR tree)) (SPACES 3) (PLR (CADR tree))
(PUD (CADR tree)) (PRIN1 (CAR tree)) (SPACES 3)
(PUD (CDDR tree)) ) (PLR (CDDR tree)) )
Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає лівим піддеревом і навпаки.
(DEFUN REVT (tree)
((NULL tree) NIL)
(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )
Розглянемо приклади:
$ (SETQ a (INSL '(5 1 7 3 9 2 4 8 10) NIL)) $ (SETQ b (REVT a))
$ (PLR a) $ (PLR b)
1 2 3 4 5 7 8 9 10 T 10 9 8 7 5 4 3 2 1
Функція HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між висотами лівого та правого піддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.
(DEFUN HEIGHT (tree)
((NULL tree) 0)
(MAX (ADD1 (HEIGHT (CADR tree)))
(ADD1 (HEIGHT (CDDR tree)))) )
6. Робота з файлами
По замовченню за пристрій потокового вводу (CIS - Current Input Stream) береться консоль.
1. Для читання даних з вхідного потоку використовують функцію READ. Після виконання команди (SETQ a (READ)) ви повинні ввести з консолі вираз, який буде прочитано та присвоєно змінній а. При цьому якщо буде введено декілька об'єктів, то змінній а буде присвоєно перший об'єкт. Наприклад, якщо ви введете: as bf gh, то змінна a прийме значення as. Якщо Ви хочете ввести список (складний об'єкт), то його необхідно вводити в круглих дужках: (as df gh).
2. Функція (CLEAR-INPUT) чистить буфер вводу. В будь-якому випадку повертається NIL.
3. Функція (READ-LINE) читає елементи з CIS поки не буде прочитано символ переходу на новий рядок (). Повертається символ, Р-ім'я якого складається з усіх прочитаних символів як ті були розташовані у вхідному рядку, окрім .
4. Функція (READ-CHAR) читає наступний елемент з CIS та повертає його.
5. Функція (UNREAD-CHAR) повертає в CIS останній прочитаний символ.
6. Функція (LISTEN) повертає T якщо CIS не порожній, та NIL якщо ми дійшли до кінця файлу.
7. Функції (OPEN-INPUT-FILE "") та (CLOSE-INPUT-FILE "") використовуються для відкриття та закриття файла для вводу.
8. Функції (OPEN-OUTPUT-FILE "") та (CLOSE-OUTPUT-FILE "") відповідно відкривають та закривають файл для виводу інформації.
Loading...

 
 

Цікаве