bule.cz wiki

2014/2015

2015/2016

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
Zadání započtového domácího úkolu pro
KMI/YPP1

22.10.13
Celkový počet bodů je 45, z nich student, 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. 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)

(5 bodů)

2. 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

(3 body)

3. 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))
(6 bodů)

4. 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)

(3 body)

5. 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 3 4) <=) ⇒ #t
(pairwise-test? ’(1 3 4) (lambda(a b) (= a (- b 1)))) ⇒ #f
(pairwise-test? ’(1 2 3) (lambda(a b) (= a (- b 1)))) ⇒ #t
(7 bodů)

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

7. 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é.
(15 bodů)
YPP1/ypp1du.txt · Last modified: 2014/01/10 01:35 (external edit)
Show page Old revisions
Media Manager Back to top