# Zkouška 14.5.2007

<{ForumPost(poster="neoangin", timestamp=2007-05-15 10:26:11)}>
PROLOG  
  
1) Permutaci prvku od 1 do n muzeme reprezentovat bud jako "vektor obrazu"   
napr. pro n=7 termem v(7, \[3,2,4,1,6,5,7])  
nebo jako seznam netrivialnich cyklu prislusneho zobrazeni  
c(7, \[ \[1,3,4], \[5,6] ] ) (cykly \[2] a \[7] jsme vynechali).  
Soucin permutaci P1 a P2 je permutace P3, ktera vznikne slozenim zobrazeni P1 P2, tj. P3(x)=P1(P2(x)).  
Sestavte predikaty, ktere realizuji nasobeni a umocnovani permutaci reprezentovanych pomoci cyklu.  
  
2)Mate k dispozici predikat modry/1, ktery uspeje, pokud argument je modry. Sestavte predikat  
natretiny(+Seznam, -Prvni, -Druhy, -Treti),  
ktery rozdeli efektivnim zpusobem vstupni seznam na tri seznamy obsahujici priblizne stejne modrych prvku (Zretezeni seznamu Prvni, Druhy a Treti je seznam Seznam, pocty modrych prvku v seznamech Prvni, Druhy a Treti se mohou lisit nejvyse o 1). Pri jeho konstrukci nesmite pouzit zadnou aritmetiku (ani predikat length).  
  
HASKELL  
  
3) Ridka matice je reprezentovana jako trojice (m,n,s), kde m je pocet radek, n je pocet sloupcu a s je seznam trojic (i,j,aij) {kde i je cislo radky, j je cislo sloupce a aij je nenulova hodnota} usporadany vzestupne podle i a uvnitr radek podle j.  
Naprogramujte funkce, ktere v teto reprezentaci realizuji  
a) transpozici matic  
b) nasobeni matic  
c) umocnovani matic (dobrovolne  
Nejedna se tedy o pole v Haskellu  
  
4) Definujte prirozenou reprezentaci binarniho stromu, v jehoz uzlech je ulozena informace nejakeho typu (podtridy Ord).  
Naprogramujte funkci, ktera ze zadaneho binarniho vyhledavaciho stromu vypusti vsechny uzly, ktere obsahuji hodnotu klice, na kterem zadana funkce krit vrati hodnotu True.  
  
Ak mate riesenia, sem s nimi. Najzaujimavejsie asi bude riesenie toho prveho.
<{/ForumPost}>

<{ForumPost(poster="univ", timestamp=2007-05-22 14:55:31)}>


    % natretiny(+,-,-,-)
    
    natretiny(Seznam,Prvni,Druhy,Treti):-
    prvni_tretina(Seznam,Prvni,Zbytek),napoloviny(Zbytek,Druhy,Treti).
    
    
    % prvni_tretina(+,-,-)
    
    prvni_tretina(Seznam,Prvni,Zbytek):-
    tretina2(Seznam,Seznam,Prvni,Zbytek).
    
    % tretina2(+,+,-,-)
    
    tretina2(L1,L2,P,Zb):-
    odeber3modre(L1,L1Zb),!,odeber1modry(L2,PZb,P,L2Zb),tretina2(L1Zb,L2Zb,PZb,Zb).
    
    tretina2(_,L2,[],L2).
    
    % odeber1modry(+,+,-,-)
    
    odeber1modry([H|L],PZb,[H|L2],Zb):-
    modry(H),!,L2=PZb,Zb=L;odeber1modry(L,PZb,L2,Zb).
    
    % odeber2modre(+,-)
    
    odeber2modre([H|L],Zb):-
    modry(H),!,odeber1modry(L,_,_,Zb);odeber2modre(L,Zb).
    
    % odeber3modre(+,-)
    
    odeber3modre([H|L],Zb):-
    modry(H),!,odeber2modre(L,Zb);odeber3modre(L,Zb).
    
    
    % napoloviny(+,-,-)
    
    napoloviny(L,L1,L2):-polovina2(L,L,L1,L2).
    
    % polovina2(+,+,-,-)
    
    polovina2(L1,L2,P,Zb):-
    odeber2modre(L1,L1Zb),!,odeber1modry(L2,PZb,P,L2Zb),polovina2(L1Zb,L2Zb,PZb,Zb).
    
    polovina2(_,L2,[],L2).
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    % TEST
    
    :-op(100,xfy,->).
    
    modry(m).
    
    s([m,m,a,m,m,b,m,m]).
    s([a,m,b,m,c,m,d,m,e,m,f]).
    s([a,b,c,m,m,d,e,f,m,g,h,i,m,j,k,l]).
    
    test:-s(X),natretiny(X,L1,L2,L3),write(X->L1+L2+L3),nl,fail.


<{/ForumPost}>

<{ForumPost(poster="univ", timestamp=2007-05-22 14:57:36)}>


    data Tree a = Nil | ND (Tree a) a (Tree a)
    
    vypust::(a->Bool)->Tree a->Tree a
    
    vypust _ Nil = Nil
    
    vypust krit ND l v p| not krit v = lt v pt| lt == Nil = pt| pt == Nil = lt| otherwise ND ltBEZmax maxlt pt
        wherelt = vypust krit lpt = vypust krit p(ltBEZmax,maxlt)=bezMAX lt
    
    
    bezMAX::Tree a->(Tree a,a)
    
    bezMAX ND l v p| p == Nil = (l,v)| otherwise = (ND l v pt, maxpt)
        where(pt,maxpt)=bezMAX p


<{/ForumPost}>