Zkouška 14.5.2007

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí
Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouška 14.5.2007

reseni otazky c. 4 haskell

od univ » 22. 5. 2007 14:57

Kód: Vybrat vše

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
    where
	lt = vypust krit l
	pt = 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

reseni otazky c. 2 prolog

od univ » 22. 5. 2007 14:55

Kód: Vybrat vše

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

Zkouška 14.5.2007

od neoangin » 15. 5. 2007 10:26

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.

Nahoru