/  
 ДОКУМЕНТІВ 
20298
    КАТЕГОРІЙ 
30
Про проект  Рекламодавцям  Зворотній зв`язок  Контакт 

Засоби та принципи програмування на Ліспі, Детальна інформація

Тема: Засоби та принципи програмування на Ліспі
Тип документу: Реферат
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 0
Скачувань: 933
Скачати "Реферат на тему Засоби та принципи програмування на Ліспі"
Сторінки 1   2   3   4   5   6   7  
(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)

) )

5. Дерева

Деревом називається граф без циклів, в якому виділено окрему вершину, яку називають коренем дерева.

Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру типу (Значення . (Лівий син . Правий син)), де лівий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).

Функція INSEL вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Інакше вставити елемент в ліве піддерево якщо n менше за значення поточної вершини або в праве піддерево, якщо більше. Функція INSL створює за списком сортуюче дерево, вершинами якого будуть всі елементи списка. Дерево називається сортуючим, оскільки при обході його зліва направо ми отримаємо відсортований список елементів у зростаючому порядку.

(DEFUN insel (n tree)

((NULL tree) (CONS n (CONS NIL NIL)))

((> 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) — обхід зліва направо.

Сторінки 1   2   3   4   5   6   7  
Коментарі до даного документу
Додати коментар