#!/usr/bin/env racket #lang racket/base Zadání započtového domácího úkolu pro KMI/YPP1

22.10.2013 Celkový počet bodů je 45, z nich student musí získat 30. Řešení odevzdávejte e-mailem (jako přílohu):

• adresa: jan.konecny@upol.cz
• předmět: KMI/YPP2 ukol
• příloha: jmeno _ prijmeni .scm

V odevzdávaném souboru:

• mějte jen definice požadovaných procedur,
• veškeré pomocné procedury definujte interně;
• v souboru nemějte příklady použití a testy,
• kód nemusí být komentován.

(5 bodů) Naprogramujte proceduru interlace, která bere dva argumenty: seznam list , libovolný element elem , a vrací seznam, který vznikne ze seznamu list vložením elementu elem mezi každé dva prvky. Příklady použití:

(interlace () ’x) ;⇒ ()
(interlace (list 1) ’x) ;⇒ (1)
(interlace (list 1 2 3) ’x) ;⇒ (1 x 2 x 3)
(interlace (list 1 2 3) ()) ;⇒ (1 () 2 () 3)

(3 body) Naprogramujte predikát interlaced?, který vrací #t, pokud je jeho argument seznam liché délky (nebo je prázdný) a prvky na sudých pozicích jsou si rovny. Predikát vlastně zjištuje, jestli seznam mohl vzniknout použitím procedury interlace z předchozího příkladu. Příklady použití:

(interlaced? ()) ;⇒ #t
(interlaced? (list 1)) ;⇒ #t
(interlaced? (interlace (list 1 2 3) ’x)) ;⇒ #t
(interlaced? ’(1 x 2 x)) ;⇒ #f
(interlaced? ’(x 1 x 2 x)) ;⇒ #f
(interlaced? ’(x x x)) ;⇒ #t

(6 bodů) Naprogramujte proceduru collate, která bere jako argument seznam list a vrací seznam párů ( elem . count ), kde elem je prvek ze seznamu list , count je počet výskytů elem v seznamu list . Páry jsou uspořádány sestupně podle count . Pro setřídění můžete použít sort Příklady použití:

(collate ()) ;⇒ ()
(collate ’(x)) ;⇒ ((x . 1))
(collate (interlace (list 1 2 3) ’x)) ;⇒ ((x . 2) (1 . 1) (2 . 1) (3 . 1))
(collate (1 1 2 1 2)) ;⇒ ((1 . 3) (2 . 2))

(3 body) Naprogramujte proceduru pick-combination, která bere jako argumenty dva seznamy: seznam list a číselný seznam indexes – čísla v něm představují pozice. Procedura vrací seznam prvků ze seznamu list, které odpovídají pozicím číselném seznamu. Příklady použití:

(pick-combination ’(a b c) (1 1 3 1)) ;⇒ (a a c a)
(pick-combination ’(a b c) (1 3 2)) ;⇒ (a c b)

(7 bodů) Naprogramujte predikát pairwise-test?, která bere dva argumenty: seznam list a predikát pred? dvou argumentů. Predikát pairwise-good?, který vrací #t, právě když každé dva sousední prvky v seznamu list splňují predikát pred? . Řešte pomocí rekurze. Příklady použití:

(pairwise-test? ’(1 2 3) (lambda(a b) (= a (- b 1)))) ;⇒ #t
(pairwise-test? ’(1 3 4) <=) ;⇒ #t
(pairwise-test? ’(1 3 4) (lambda(a b) (= a (- b 1)))) ;⇒ #f

(6 bodů) Naprogramujte predikát pairwise-test? z předchozího příkladu pomocí akumulace.

(15 bodů) Uvažujme následující reprezentaci stromů: každý uzel je reprezentován jako struktura ( tag ( left right )). tag je pravdivostní hodnota, která reprezentuje barvu (#t je černá„ #f je červená) a left a right jsou prázdné seznamy a nebo další uzly. Listy jsou representováný jako ( tag ()). Naprogramujte predikát redblack-tree?, který zjišťuje, jestli je jeho argument reprezentací červeno-černého stromu. To znamená

• kořen je černý,
• na cestě od kořenu ke každému listu je stejný počet černých uzlů,
• pokud je uzel červený, tak left a right jsou černé.

 ; vim: syntax=racket