Дерева (графи)

Дерева (графи)

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

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

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

(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) )

Наступнi двi функцiї виконують обхiд дерева: PUD (Print Up-Down) - обхiд згори вниз, PLR (Print Left-Right) - обхiд злiва направо.

(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)) )

Функцiя REVT (Reverse Tree) обертає дерево: кожне праве пiддерево стає лiвим пiддеревом i навпаки.

(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

Функцiя HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорiвнює 0. Висота непорожнього дерева дорiвнює максимумовi мiж висотами лiвого та правого пiддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.

(DEFUN HEIGHT (tree)

((NULL tree) 0)

(MAX (ADD1 (HEIGHT (CADR tree))) (ADD1 (HEIGHT (CDDR tree)))) )

Функцiї модифiкатора

Функцiї модифiкатора виконують переадресацiю вказiвникiв в структурах даних мови програмування Лiсп.

1. RPLACA . Вiдбувається замiна CAR-елемента об'єкта1 вказiвником на об'єкт2, повертається модифiкований об'єкт. Якщо об'єкт1 - список, то перший елемент списка замiнюється на об'єкт2. Якщо об'єкт1 - бiнарне дерево, то його лiвий син замiнюється на об'єкт2. Якщо об'єкт1 - символ (aле не NIL), то символ приймає значення об'єкт2.

$ (SETQ a '(a b c d))$ (SETQ b '((1 . 2) . (3 . 4)))$ (SETQ s 'd)

$ (RPLACA a '(11 12))$ (RPLACA b 5)$ (RPLACA s 'g)

((11 12) b c d)(5 . (3 . 4))Val(s)=d,Val(d) = g

2. RPLACD . Вiдбувається замiна CDR-елемента об'єкта1 вказiвником на об'єкт2, повертається модифiкований об'єкт. RPLACA та RPLACD є основними функцiями, якi змiнюють фiзичну структуру спискiв. Їх можна представити через узагальнену функцiю присвоєння SETF:

(RPLACA x y)- це (SETF (CAR x) y)

(RPLACD x y)- це (SETF (CDR x) y)

3. NSUBSTITUTE . Модифiкуються конси найвищого рiвня списку. Старi елементи замiнюються на новi на нульовому рiвнi вкладеностi, для яких перевiрка по тесту не дорiвнює NIL. Якщо тест не вказано, то по замовченню тест = EQL.

$ (NSUBSTITUTE 1 3 '(4 5 6 (3 3 4 5) 3 4 1))

(4 5 6 (3 3 4 5) 1 4 1)

$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) >)$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1)

4. NSUBST . Функцiя працює як i NSUBSTITUTE, але модифiкуються конси всiх рiвнiв списку.

$ (NSUBST 1 3 '(4 5 6 (3 3 4 5) 3 4 1))

(4 5 6 (1 1 4 5) 1 4 1)

5. DELETE . Вилучає зi списку всi елементи, для яких ознака перевiрки за тестом не дорiвнює NIL.

$ (DELETE 3 '(1 2 3 4 3 2 1))

(1 2 4 2 1)

6. NREVERSE . Обертає елементи списку, зчеплених з об'єктом.

$ (NREVERSE '(a b c d))$ (NREVERSE '(1 2 3 (1 2 3) 4 5 6) '(1 2 3))

(d c b a)(6 5 4 (1 2 3) 3 2 1 1 2 3)

7. NBUTLAST . Якщо n - нуль або додатне цiле, то функцiя NBUTLAST повертає список без n останнiх елементiв (вiдбувається замiна n-го конса, взятого з кiнця списку на NIL). Якщо другий аргумент не вказано, то за замовченням n=1.

$ (NBUTLAST '(a b c d e))$ (NBUTLAST '(a b c d e) 3)

(a b c d)(a b)

8. NCONC ... . Повертається список, який складається з елементiв спискiв - аргументiв у вказаному порядку. Вiдбувається модифiкацiя останнiх CDR-елементiв спискiв. Якщо виконати команду (NCONC list list), де list - будь-який список, то результатом буде циркулянтний список, процес побудови якого буде нескiнченним.

$ (NCONC '(1 2) '(3 4) '(5 6 7))

(1 2 3 4 5 6 7)9. SPLIT . Розбиває список на два списки посерединi. Значенням списку стає його перша половина. Функцiя SPLIT повертає другу половину списку.

$ (SETQ a '(1 2 3 4 5 6))$ a

$ (SPLIT a)(1 2 3)

(4 5 6)

10. SORT . Сортуються елементи списку на основi тесту.

$ (SORT '(2 5 3 4 1 6 8 9 7) >)

(9 8 7 6 5 4 3 2 1)

Завдання 1. Знайти кiлькiсть листiв в заданому деревi.

2. Знайти середнє арифметичне чисел, якi знаходяться у вершинах дерева.

3. Написати функцiю швидкого сортування QSORT.

Робота з файлами

По замовченню за пристрiй потокового вводу (CIS - Current Input Stream) береться консоль.

1. Для читання даних з вхiдного потоку використовують функцiю READ. Пiсля виконання команди (SETQ a (READ)) ви повиннi ввести з консолi вираз, який буде прочитано та присвоєно змiннiй а. При цьому якщо буде введено декiлька об'єктiв, то змiннiй а буде присвоєно перший об'єкт. Наприклад, якщо ви введете: as bf gh, то змiнна a прийме значення as. Якщо Ви хочете ввести список (складний об'єкт), то його необхiдно вводити в круглих дужках: (as df gh).

2. Функцiя (CLEAR-INPUT) чистить буфер вводу. В будь-якому випадку повертається NIL.

3. Функцiя (READ-LINE) читає елементи з CIS поки не буде прочитано символ переходу на новий рядок (). Повертається символ, Р-iм'я якого складається з усiх прочитаних символiв як тi були розташованi у вхiдному рядку, окрiм .

4. Функцiя (READ-CHAR) читає наступний елемент з CIS та повертає його.

5. Функцiя (UNREAD-CHAR) повертає в CIS останнiй прочитаний символ.

6. Функцiя (LISTEN) повертає T якщо CIS не порожнiй, та NIL якщо ми дiйшли до кiнця файлу.

7. Функцiї (OPEN-INPUT-FILE "") та (CLOSE-INPUT-FILE "") використовуються для вiдкриття та закриття файла для вводу.

8. Функцiї (OPEN-OUTPUT-FILE "") та (CLOSE-OUTPUT-FILE "") вiдповiдно вiдкривають та закривають файл для виводу iнформацiї.

Приклади

1. Надрукувати кiлькiсть лiтер sym в файлi name.

(DEFUN f (name sym) (SETQ a (READ))

(SETQ c 0) (IF (EQL a sym) (INCQ c)) )

(OPEN-INPUT-FILE name) (CLOSE-INPUT-FILE name)

(LOOP c)

((NOT (LISTEN)))

2. Надрукувати файл в оберненому порядку, якщо його елементи є атомами.

(DEFUN rew (in out) (PUSH (READ) temp) )

(OPEN-INPUT-FILE in) (LOOP

(OPEN-OUTPUT-FILE out) ((EQL temp NIL))

(SETQ temp NIL) (WRITE (POP temp))

(LOOP (SPACES 1) )

((NOT (LISTEN))) (CLOSE-INPUT-FILE in)

(CLOSE-OUTPUT-FILE out) )

Завдання

1. Написати функцiю (SRT ), яка сортує текстовий файл та виводить данi в файл .

2. Написати функцiї (PRNUM2 num) та (PRNUM16 num), якi вiдповiдно друкують введенi десятковi числа в двiйковому та шiстнадцятковому представленнi.

3. Згенерувати за даними числом n та символом y список (y yy yyy yyyy .... yyyyyyyy. Кiлькiсть лiтер s в останньому елементi списку дорiвнює n.

Пpиклади.

Пpиклад 1. Число вводиться своїм двiйковим представленням (довжина числа не перевищує 10000 двiйкових розрядiв). Необхiдно визначити, чи дiлиться воно на 15.

Вказiвка: Ознакою дiлння на 9 у десятковiй системi числення є подiльнiсть на 9 суми цифр числа (дiйсно, нехай є число

S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].

S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +

+ ... + a[1]*(10-1)+a[1] + a[0]) mod 9

А оскiльки 10^k - 1 дiлиться на 9, то i

S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,

що вipно).

Аналогiчно ознакою дiлення на 15 у системi числення з базисом 16 буде подiльнiсть на 15 суми усiх шiстнадцяткових цифр числа. Ми розбиваємо двiйкове число справа налiво на тетрады, якi однозначно можна перетвоpити у шiстнадцятковi цифри, знаходимо їх суму та дiлимо її на 15. Якщо залишок 0, то введене число дiлится на 15, iнакше - нi.

Пpиклад 2. Дано число в K-iчнiй системi числення

a a ...a (K<=36).

n n-1 0

Знайти залишок вiд дiлення його на m.

Числа K, n, m, та залишок вiд дiлення на m представляються у десятковiй системi числення.

Вказiвка: У системi числення з основою K число представляється у виглядi

a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0.

Знайдемо залишок вiд дiлення його на m (залишок вiд дiлення a на b позначимо чеpез a mod b):

(a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0) mod m =

┌ n ┐ ┌ n ┐

=│ SUM a[i]*K^i│ mod m = │ SUM a[i]* (K^i mod m)│ mod m =

└ i=0 ┘ └ i=0 ┘

Остання piвнiсть випливає з наступного:

Hехай K^i mod m=t, тодi K^i =p*m+t, та

(a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =

= (a[i]* p*m) mod m + (a[i]*t) mod m =

= (a[i] * (K^i mod m)) mod m,

при цьому для довiльних чисел b[i] виконується

n n( SUM b[i] ) mod m =( SUM b[i] mod m ) mod m.

i=0 i=0

Вiдмiтимо також очевидну рiвiсть

K^i mod m =[(K^(i-1) mod m) * K] mod m,

оскiльки якщо K^(i-1) = p*m+t,

то K^(i-1) mod m = t,

K^i = p*m*K+t*K и K^i mod m = t*K mod m =

= [(K^(i-1) mod m)*K] mod m.

Запис цього алгоритму (тут a[i] - K-iчнi цифри числа):

s:=0; t:=1;

for i:=0 to n do

begin

s:=(s+a[i]*t) mod m;

t:=t*K mod m;

end;

У змiннiй S пiсля закiнчення роботи алгоритму буде збеpiгатися шукана остача.

Пpиклад 3.Пiдpахувати кiлькiсть одиниць у двiйковому запису числа i. Кiлькiсть опеpацiй для pозв'язку задачi повинна бути мiнiмiзована.

Вказiвка:

cnt:=0; cnt -- лiчильник одиниць у числi i.

while (i<>0) do цикл повторюється кiлькiсть разiв, рiвне

begin кiлькостi одиниць в i. "Знищуємо" крайню

i:=(i-1) and i; справа одиницю у двiйковому запису числа.

cnt:=cnt+1;

end; Приклад: 110 = i

101 = i-1

------------------

100 = i and (i-1)

Пpиклад 4. Послiдовнiсть 011212201220200112... будується так: спочатку пишеться 0, потiм повторюється наступна дiя: вже написану частину приписують справа iз замiною 0 на 1, 1 на 2, 2 на 0, тобто

0 -> 01 -> 0112 -> 01121220 ->...

Скласти алгоритм, який за введеним N, (0<=N<=3000000000) визначає, яке число стоїть на N-ому мiстi в послiдовностi.

Вказiвка: Hехай a(k) - k-ий член послiдовностi. Розглянемо послiдовнiсть, сфоpмовану за наступним пpавилом:

a(0)=0;

ряд

a(0)...a(2**k-1)

отpимуємо приписуванням до цiєї послiдовностi справа цiєї ж послiдовностi, але при цьому кождний член приписуємої частини збiльшуємо на одиницю. Отpимаємо

0->01->0112->01121223->...

Доведемо, що a(k) є сума одиниць у двiйковому представленнi числа k.

Доведення проведемо за iндукцiєю. Для a(0)=0 це справедливо. Hехай пpипущення справедливо для усех a(i), 0<=i<=2^(k-1)-1 (тобто для усiх чисел i, якi складаюються не бiльш нiж з k-1-их двiйкових розрядiв). Тодi у двiйковому pозкладi l, 2^(k-1)<=l