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

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

ГоловнаІнформатика, Компютерні науки → Породження комбінаторних об’єктів - Реферат

Породження комбінаторних об’єктів - Реферат


Реферат на тему:
Породження комбінаторних об'єктів.
Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.
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) (DEFUN NEXT (lst n)
((ZEROP n) NIL) ((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))
(CONS 1 (GEN1 (- n 1))) ) ((NULL (CDR lst)) NIL)
(CONS 1 (NEXT (CDR lst) n))
Шукана функція має вигляд: (DEFUN P12BEST (n k lst c)
(DEFUN P12 k n) ((ZEROP n) (PRIN1 lst) (TERPRI))
(SETQ lst (GEN1 k)) (PUSH 1 c)
(LOOP (LOOP
(( (CAR c) k))
(PRIN1 lst) (TERPRI) (P12BEST (- n 1) k (CONS (CAR c) lst) c)
(SETQ lst (NEXT lst n)) (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)))
((< (CAR lst) (CADR lst)) (SETQ a (POP lst))
(SETQ b (POP lst))
(PUSH a lst)
(PUSH b lst)
(SETQ lst (APPEND (REVERSE cur) lst))
(move_per lst) )
(PUSH (POP lst) cur)
) )
Обчислювані функції
Обчислення виразів та звернення до функцій відбувається автоматично інтерпретатором muLisp. Обчислювані функції необхідні в тих випадках коли необхідно безпосередньо обчислити вираз або звернутися до функцій. Визначенням функції є список, який складається з трьох частин: імені типу функції, формальних параметрів та тіла функції.
CAR-елементом визначення функції є ім'я типу фукції - LAMBDA, NLAMBDA чи MACRO. Тип функції дає інтерпретаторові інформацію про те, як використовувати дану функцію.
Визначення функцій та їх обчислення в Ліспі основано на лямбда-численні Чорча. Лямбда вираз, який взято з лямбда числення, є важливим механізмом у програмуванні. В лямбда численні Чорча функція записується у вигляді:
lambda (x1, x2, ..., xn) . f
В Ліспі лямбда вираз має вигляд:
(LAMBDA (x1 x2 ... xn) f)
Символ LAMBDA говорить нам про визначення функції. Символи xi - це формальні параметри, f - тіло функції. Тілом функції може бути довільна форма, значення якої може обчислити інтерпретатор Ліспа. Функцію, яка обчислює суму квадратів двох чисел, можна визначити так:
(LAMBDA (x y) (+ (* x x) (* y y)) )
Формальність параметрів вказує на те, що ми можемо замінити їх на інші символи, але від цього не зміниться сутність обчислення функції.
Лямбда вираз - це визначення обчислення та параметрів функції в чистому вигляді без фактичних параметрів або аргументів. Для застосування такої функції до певних аргументів, необхідно поставити лямбда вираз на місце імені функції:
(лямбда-вираз a1 a2 ... an)
Тут ai - форми, що задають фактичні параметри. Наприклад, множення (* 3 4) можна записати з використанням лямбда виклику:
$ ((LAMBDA (x y) (* x y)) 3 4)
12
Наступний виклик будує список з двох аргументів:
$ ((LAMBDA (x y) (CONS x (CONS y NIL))) 'dog 'cat)
(dog cat)
Таку форму виклику називають лямбда викликом. Обчислення лямбда виклику відбувається в два етапи. Спочатку обчислюються значення фактичних параметрів та відповідні формальні параметри зв'язуються з отриманими значеннями. На другому етапі обчислюється форма, яка є тілом лямбда виразу. Отримане значення повертається в якості значення лямбда виклику. По завершенню обчислення формальним параметрам повертаються зв'язки , які існували до лямбда виклику. Весь цей процес називається лямбда перетворенням.
Пам'ятайте, що лямбда вираз без фактичних параметрів є лише визначення, а не форма, яку можна обчислити. Сам по собі лямбда вираз інтерпретатором не сприймається. Якщо ви введете: (LAMBDA (x y) (CONS x (CONS y NIL))), то інтерпретатор Ліспу видасть повідомлення про помилку.
Лямбда вираз є як чисто абстрактним механізмом для визначення та опису обчислення, так і механізмом для зв'язування формальних та фактичних параметрів під час виконання обчислення. Лямбда вираз є функцією без імені.
Ми вже говорили про те, як визначити нову функцію - це можна здійснити за допомогою функції DEFUN. Визначення функції викликається так:
(DEFUN )
Для спрощення опустимо зовнішні дужки у лямбда виразі та сам атом LAMBDA. Тоді ми отримаємо знайоме нам визначення функції. Наступні визначення еквівалентні:
(DEFUN list2 (LAMBDA (x y) (CONS x (CONS y NIL))))
та
(DEFUN list2 (x y) (CONS x (CONS y NIL)))
Функція DEFUN з'єднує символ з лямбда виразом, після чого символ починає іменувати обчислення, яке визначається лямбда виразом. Значенням функції DEFUN є ім'я нової функції.
За допомогою структури LET, яка визначена в common.lsp, можна утворити локальний звя'зок. Значення змінним форми LET присвоюються одночасно. Ця структура має наступний вигляд:
(LET ((m1 a1) (m2 a2) ... (mN aN)) ... ),
яка в дійсності є лямбда викликом, де формальні та фактичні параметри знаходяться разом на початку структури:
((LAMBDA (m1 m2 ... mN) ... ) a1 a2 ... aN)
Наступні виклики еквівалентні:
$ (LET ((x 4)(y 2))(+ x y)) $ ((LAMBDA (xy) (+ x y)) 4 2)
6 6
Функція типу NLAMBDA називається необчислюваною. Якщо викликається необчислювана функція, то їй аргументи передаються без обчислення - так, як вони стоять в рядку виклику. Пояснимо це на прикладі. Визначимо дві функції f1 та f2, які на перший погляд однакові:
(DEFUN f1 (LAMBDA (x y) (DEFUN f2 (NLAMBDA (x y)
(+ x y)) ) (+ x y)) )
Якщо викликати (f1 5 6) або (f2 5 6), то результат буде однаковим - 11.
Нехай змінним k та l присвоєні деякі значення: (SETQ k 5 l 6). Тоді
$ (f1 k l) $ (f2 k l)
11 помилка: (+ k l) / а не (+ 5 6), оскільки передані аргументи не обчислені /
Функція типу MACRO називається макро-функцією. Макроси є потужним робочим інструментом програмування. Синтаксис визначення макроса виглядає таким же чином як синтаксис визначення функції форми DEFUN:
(DEFMACRO )
Виклик макроса співпадає за формою з викликом функцї, але його обчислення відрізняється від
Loading...

 
 

Цікаве