======ypp1du.scm====== <code shell></code> #!/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. ======= 1. interlace ======= (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í: <code scheme> (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) </code> ======= 2. interlace? ======= (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í: <code scheme> (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 </code> ======= 3. collate ======= (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í: <code scheme> (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)) </code> ====== 4. pick-combination ====== (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í: <code scheme> (pick-combination ’(a b c) (1 1 3 1)) ;⇒ (a a c a) (pick-combination ’(a b c) (1 3 2)) ;⇒ (a c b) </code> ====== 5. pairwise-testp ====== (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í: <code scheme> (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 </code> ====== 6. pairwise-testp akumulace====== (6 bodů) Naprogramujte predikát pairwise-test? z předchozího příkladu pomocí akumulace. ======= 7. redblack-treep ======= (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é. <code scheme> ; vim: syntax=racket </code>