Zkouška 14.5.2007

neoangin
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 4. 6. 2006 10:51
Typ studia: Informatika Bc.
Bydliště: Blava/Praha
Kontaktovat uživatele:

Zkouška 14.5.2007

Příspěvek od neoangin »

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.
$ man woman
No manual entry for woman
univ
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 8. 3. 2007 17:18

reseni otazky c. 2 prolog

Příspěvek od univ »

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.
univ
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 8. 3. 2007 17:18

reseni otazky c. 4 haskell

Příspěvek od univ »

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
Odpovědět

Zpět na „2006“