Warning: Declaration of action_plugin_subjectindex_indexer::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php on line 15

Warning: Declaration of action_plugin_mathjax_enable::register(Doku_Event_Handler &$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/mathjax/action/enable.php on line 62

Warning: Declaration of action_plugin_googleanalytics::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/googleanalytics/action.php on line 40

Warning: Declaration of action_plugin_folded::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/folded/action.php on line 40

Warning: Declaration of action_plugin_hidden::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/hidden/action.php on line 28

Warning: Declaration of action_plugin_include::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/include/action.php on line 354

Warning: Declaration of action_plugin_tag::register(&$contr) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/tag/action.php on line 175

Warning: Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in /data/web/virtuals/28604/virtual/www/subdom/bo/inc/auth.php on line 532

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /data/web/virtuals/28604/virtual/www/subdom/bo/inc/auth.php on line 818

Warning: Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in /data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php on line 656

Warning: Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in /data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php on line 656

Warning: Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in /data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php on line 656
======P10.scm======

#!/usr/bin/env racket
#lang racket/base

přiklady, programy, kód z [[PAPR1:L10|Lekce 10]] * n-ární a binární stromy 10.1, 10.3 * množiny jako uspořádané seznamy 10.2, nebo BST: 10.3 * kombinatorika 10.4 ======= 10.1 n-ární stromy ======= a /|\ b c d |\ e f /|\ g h i | j


(define tree-aj
'(a
   (b)
   (c
       (e)
       (f
         (g)
         (h)
         (i (j))))
       (d))
 )


(define tree
  (lambda (val . subtrees)
    (cons val subtrees)))

(define get-val car)
(define (get-branches tree)
  (if (null? tree)
    '()
    (cdr tree));safe-cdr
  )

(a (b c) (...))


(define (forall p? l)
  (or (null? l);prazdna mnozina splnuje
      (and (p? (car l))
           (forall p? (cdr l)))))

(define (tree? t)
  (and (list? t)
       (forall tree? (cdr t))))
 ;
 ;stejne jako tree?, ale forall inline named let:
(define (tree2? t)
  (and (list? t)
       (let forall ((p? tree?) (l (cdr t)))
         (or (null? l)
             (and (p? (car l))
                  (forall p? (cdr l)))));inline forall, named-let iterace
       ))


(map tree?  (list tree-aj 1 '(1 . 2) '(1 2) '(1 (2 3)) '(1 (2 (3))) ))
(map tree2? (list tree-aj 1 '(1 . 2) '(1 2) '(1 (2 3)) '(1 (2 (3))) ))


(define (left-branches tree k)
  (if (or (< k 0) (null? tree))
    '()
    (let iter ((k k) (branches (cdr tree)))
      (cond ((null? branches) '())
            ((= k 0) (car branches))
            (else (iter (- k 1) (cdr branches)))))))

(define (right-branches tree k)
  (left-branches tree (- (length tree) k -2)))


(map (lambda (k) (left-branches tree-aj k)) '(0 1 2 3 4))
(map (lambda (k) (left-branches '(r (a) (b) (c) (d)) k)) '(0 1 2 3 4))


(define (dfs tree)
  (if (null? tree)
    '()
    (cons (get-val tree)
         ;(   dfs (get-branches tree))
         ;mapuj dfs na branches => apply append
          (apply append (map dfs (get-branches tree)))
          )))


(dfs tree-aj)
(equal? (dfs tree-aj) '(a b c e f g h i j d))

do sirky: iterace po patrech:


(a (b) (c               (f)))
       (d ...) (e ...))


(define (bfs tree)
  (let patro ((tree (list tree)));"pridame" patro navic
    (display tree) (newline)
    (if (null? tree)
      '()
      (append (map get-val tree);hodnoty tohoto patra
              ;rekurze do dalsiho patra
              (patro (apply append (map get-branches tree)))))))


'(bfs testy)
tree-aj
(map (lambda (x) (display `(x: ,x)) (newline))  tree-aj)

(map get-val tree-aj) ;nefunguje!!!


(map get-val (list tree-aj))
(map get-val (get-branches tree-aj))
`(bfs: ,(bfs tree-aj))
`(dfs: ,(dfs tree-aj))

======= 10.3 BST, reprezentace množin ======= BST: prázdný nebo strom s dvěma podtromy


(define (make-bst  val left right) (list val left right))
(define (make-leaf val) (make-bst val '() '()))
(define (bst-val   tree) (car tree))
(define (bst-left  tree) (cadr tree))
(define (bst-right tree) (caddr tree))


(define bstree (make-bst 4
                         (make-bst 2 (make-leaf 1) (make-leaf 3))
                         (make-bst 6 (make-leaf 5) (make-leaf 7))))
bstree

* union a inter: sjednocení a průnik predikát in * prazdný => #f * hodnota rovna => #t * jinak left/right podle <=


(define (bst-in? x tree)
  (cond
    ((null? tree) #f)
    ((= x (bst-val tree)) #t)
    ((< x (bst-val tree))
          (bst-in? x (bst-left  tree)))
    (else (bst-in? x (bst-right tree)))))


(let ((cisla  '(1 2 3 4 5 6 7 99)))
 (map cons cisla (map (lambda (x) (bst-in? x bstree)) cisla)))


(define (cons-bst x tree)

(display `(x: ,x tree: ,tree)) (newline)


  (cond ((null? tree) (make-leaf x));vratime novy leaf
        ((= x (bst-val tree)) tree) ;roven/nasli, vratime
        ((< x (bst-val tree))
            (make-bst (bst-val tree)
                      (cons-bst x (bst-left tree))
                      (bst-right tree)))
        (else
            (make-bst (bst-val tree)
                      (bst-left tree)
                      (cons-bst x (bst-right tree))))))


(cons-bst 1 '())
(cons-bst 2 (cons-bst 1 '()))
(let iter ((i 1) (tree '()))
  (if (> i 10)
    tree
    (iter (+ i 1) (cons-bst i tree)))) ;nebude balancovany!?

Program 10.x


 ; vim: syntax=racket