Zkouska 17.2.

Návštěvník · Příspěvek od **Návštěvník** » 17. 2. 2006 13:16

Ahoj! Tady je zadani vcerejsich malych prikladu:
Prolog

Vytvorte seznam vsech rostoucich posloupnosti prirozenych cisel s danym souctem (bez pouziti setof/bagof).

Kód: Vybrat vše

Projdete graf pomoci DFS a ke kazdemu vrcholu pridejte cas posledni pruchodu.

Haskell

Kód: Vybrat vše

Definujte binarni strom s daty pouze v listech. Vytvorte fci, ktera pro dany strom rozlozi listy do trid podle poctu skoku doprava pri ceste od korene k danemu listu.

Kód: Vybrat vše

Hladovym algoritmem najdete minimalni vrcholove pokryti (kazda hrana musi mit v pokryti alespon jeden vrchol).

Návštěvník · Příspěvek od **Návštěvník** » 17. 2. 2006 13:18

Ted se divam, ze jsem tam napsal spatne datum. Tohle je zkouska ze 16.2. I kdyz to je stejne jedno...

zapo · Příspěvek od **zapo** » 18. 2. 2006 16:42

To DFS bolo z 1 vrcholu, takze sa to nemuselo robit pre cely graf. Ak by nahodou niekomu mohlo pomoct riesenie, tak:

Kód: Vybrat vše

% DFS z vrcholu
% g(V,E), V=[a,b,...] E=[e(a,b),...]

% prejdi(+ES,+E,+Vrchol,+KdeBol,-KdeBOlOut,+TIn,-TOut,-Zoz)
prejdi([],_,_,KB,KB,T,T,[]).
prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
    (   A \= Vrchol;
        ( A=Vrchol, member(B,KdeBol) )
    ),
    prejdi(ES,E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz).
prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
    TIn1 is TIn + 1,
    A = Vrchol,
    not(member(B,KdeBol)),
    prejdi(E,E,B,[B|KdeBol],KBO,TIn1,TOut1,Zoz1),
    TOut2 is TOut1 + 1,
    prejdi(ES,E,Vrchol,KBO,KdeBolOut,TOut2,TOut,Zoz2),
    append(Zoz1,Zoz2,Zoz3),
    Zoz = [B-(TIn1,TOut2)|Zoz3].

% dfs(+g(V,E),-Zoznam)
dfs(g([],_),[]).
dfs(g([A|_],E),Zoznam):-
    prejdi(E,E,A,[A],_,0,T,Zoz),
    T2 is T + 1,
    Zoznam = [A-(0,T2)|Zoz].

Je to trocha upravene, a vypise to nie len cas vystupu ale aj cas vstupu. Zacina z 1. vrcholu.

Ako velky priklad bolo priblizne nieco taketo:

Distribuovany tvar polynomu viac premennych je dany zoznamom, obsahujucich absolutny clen a zoznam mocnin premennych pre dany clen.
Ulohou bolo dostat na vstupe zoznam premennych a polynom (s operaciamy plus, minus, krat a mocnina na prirodzene cislo), ktory trebalo previest na distribuovany tvar.

Na zaciatku sa mi to zdalo ako nieco nepochopitelne ale ked som sa nad tym zamyslel a Hric ukazal aj priklad, tak sa to celkom dalo a k mojmu riesenie v podstate ani nemal ziadne vyhrady

Ked tak este ten priklad, co ukazal:

Kód: Vybrat vše

premenne: [x, y, z]
polynom: ((x+3)*(y*z)^5)
dist. tvar: (abs - x, y, z)
     1 - 1, 5, 5
     3 - 0, 5, 5