Породження комбінаторних об’єктів, Детальна інформація

(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) можна записати з використанням лямбда виклику: