Fpptreesandgraphs

Задачи свързани с Графи и Дървета


Тези задачки са малко по-кофти, поради рекурсивния подход към тях.


Задачи за дървета

Не са особено приятни, а и на упражненията не решихме достатъчно задачки.
Цялата работа с дървета се сведе до работа с двоични (наредени и ненаредени) дървета.
Все пак ще почнем с няколко основни функции, за работа с дървета :

;създава празно дърво
(define (empty-tree tree) '())
;Предикат дали дървото е празно
(define (empty-tree? tree) (null? tree))
;Създава дърво
(define (make-tree left root right)(list left root right))

Основните селектори :

(define (left t) (car t))
(define (right t) (caddr t))
(define (root t) (cadr t))

Проверка дали даден елемент е в двоично дърво

(define (tree-mem? t x)
  (cond ((empty-tree? t) #f)
        ((=(root t) x) #t)
        (else (or (tree-mem? (left t) x)
                  (tree-mem? (right t) x)))))

Функция, която връща списък от елементите на дадено ниво от дървото

(define (level tree k)
  (
   cond((empty-tree? tree) '())
       ((= k 0)(list (root tree)))
       (else(append (level (left tree) (- k 1)) (level (right tree) (- k 1))))
))

Функция, която връща нивото на даден елемент в двоични дърво

(define (node-level t x)
  (define (node-level-iter t k)
    (cond ((null? t) -1)
          ((=(root t) x) k)
          ((tree-mem? (left t) x) (node-level-iter (left t)  (+ k 1)))
          (else (node-level-iter (right t)  (+ k 1)))))
    (node-level-iter t 0))

Функция, която връща минималният елемент в двоично наредено дърво (най-левият)

(define (min-el tree)
  (if(empty-tree? (left tree)) (root tree)
     (min-el (left tree))
))

Задачи за графи

Тук е черната магия. Шаманизмът и джадайството.

Проверка дали съществува път между два върха на граф

(define (way u v g);;namira pyt mejdu u i v w g
  (define (w x viz)
    (if (= x v) 
        viz
        (let* ((children (lookup x g))
                (chf (filter (lambda (child);;izhvyrlq decata koito obrazuvat cikyl
                                  (not (member child viz)))
                              children)))
                 (next (map (lambda (child)
                             (w child
                                (cons child viz)))
                              chf))
                  (nextf (filter (lambda (attemt)
                                (not (null? attemt))
                                 next))
         (if (null? nextf)
              ()
              (car next f))))))
  (w u (list u)))
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License