Zk 11.6.2009

Haskell
1.
Vytvořte funkci, která pro (nekonečný) seznam reálných čísel [xi] vstup a (krátký) konečný rostoucí seznam intervaly malých integerů [a1,a2,...,an] - představte si třeba [2,5,10,25] vytvoří nekonečný seznam, jehož k-tý prvek je "n-tice" klouzavých průměrů s intervaly [a1,a2,...,an] konče k-tým.

2. Definujte si typy reprezentující binární strom a obecný uspořádaný kořenový strom. Sestavte funkce, realizující převod seznamu (lesa) obecných stromů na jeho kanonickou reprezentaci pomocí binárního stromu ("levý syn" = "prvorozený syn", "pravý syn" = "mladší bratr") a zpět

Prolog
3. Sestavte predikáty hladiny(+Strom, -Seznam_Hladin) kde výstupní parametr je seznam seznamu prvků na jednotlivých hladinách vstupního binárního stromu Strom a k němu inverzní strom(-Strom, +Seznam_Hladin). Pochopitelně to může být jeden oboustranný predikát, bude-li efektivní (to inverzní musí vracet postupně všechny možnosti stromu)

4. Definujte predikát odpov(r1,r2) dvou proměnných, který pro každé dva seznamy (přirozených čísel a znaků * a ?) r1 a r2 uspěje pokud existuje "substituce jedno čísla za žolík ? a substituce posloupnosti čísel za znak *" takové, že dostanete stejné seznamy.
   Můžete předpokládá, že v každém ze seznamů, které jsou parametry, může být nanejvýše jedna hvězdička.

Nepřišlo mi to zas tak těžké, odevzdával jsem to po dvou hodinách, o pár chybách co jsem udělal ale vím. Na ústní jdu zítra, tak se dovím o zbylých chybách :D

U té trojky jde o binární strom nebo o binární vyhledávací strom? Nemohl byste mi někdo nastínit řešení, všechna má řešení se zdají být hrozně neefektivní.

Díky

ten strom je binární.

pozor, prolog umí sám od sebe parsovat výrazy ... může to pomoct.

jinak já měl tenhle ne úplně dobře, takže až tolik neporadim, jsem rád, že mám tu zkoušku za sebou (nakonec se ten haskell ukazuje jako mnohem jednodušší než ten prolog, aspoň podle mě)

zkusil jsem to :-) kdyby byl binární vyhledávací, tak je to jednodušší.. u toho binárního mně už napadlo několik způsobů, jak to řešit, ale žádný, který by vždy vrátil binární strom, vždycky se mi tam dostane i nebinární a musím zpátky backtrackovat nebo naopak nedostanu všechny bin. stromy.

(Dal jsem svoje ostatni vytvory na: http://martinvseticka.eu/index.php?sekc ... e&page=204)

Jestli jsem to pochopil správně, tak ta 4, by mohla vypadat takto:

/*
  4. Definujte predikát odpov(r1,r2) dvou proměnných, který pro každé
     dva seznamy (přirozených čísel a znaků * a ?) r1 a r2 uspěje pokud
     existuje "substituce jednoho čísla za žolík '?' a substituce
     posloupnosti čísel za znak '*'" takové, že dostanete stejné
     seznamy. Můžete předpokládá, že v každém ze seznamů, které jsou
     parametry, může být nanejvýše jedna hvězdička.
*/

odpov(R1,R2) :- 
        cutStart(R1,R2,R1c,R2c),  % kontroluji zda se shoduji zacatky obou seznamu, dokud nenarazim na hvezdicku,
                                               % vratim zbytky obou seznamu (hvezdicku ponechavam v seznamu)
        reverse(R1c,R1cr),        % otocim seznam
        reverse(R2c,R2cr),        % otocim seznam   
        cutStart(R1cr,R2cr,_,_).  % orezavam, tentokrat konce
        % cutStart bud failuje a pak seznamy nemohou byt stejne nebo nezfailuje a vratil by seznamy:
        % 1. pripad:   
        % ===========
        % L1=[*,neco, neco,...]  
        % L2=[neco, neco,...,*]  
        % coz je pripad, kdy bychom meli vratit "true" (
        % hvezdicka v L1 se predstavuje zacatek L2 az po hvezdicku; pro hvezdicku v L2 obdobne)
        % 
        % 2. pripad:
        % ===========
        % L1=[cislo/*]  
        % L2=[*/cislo]   
        % meli bychom vratit "true"    
% cutStart(+Sezn1,+Sezn2,-OrezanySezn1,-OrezanySezn2)
/* pokud procedura zjisti, ze se seznamy lisi ve dvou prvcich, tak nenavratne failuje */
cutStart([],[],[],[]):-!.       % oba dva seznamy jsou stejne (s prihlednuti k vyznamu '?') a neobsahuji hvezdicku
cutStart([],L2,[],L2):-!,fail.	% jeden seznam je kratsi nez druhy; fail
cutStart(L1,[],L1,[]):-!,fail.  % dtto
cutStart([H1|T1],[H2|T2],T3,T4):-integer(H1),integer(H2),H1=:=H2,!,cutStart(T1,T2,T3,T4). % dve stejna cisla
cutStart([H1|_],[H2|_],_,_):-integer(H1),integer(H2),H1=\=H2,!,fail.	  % dve ruzna cisla; konec
cutStart([H1|T1],[H2|T2],T3,T4):-(integer(H1);integer(H2);H1=='?',H2=='?'),         % vyznam '?'
        (H1=='?';H2=='?'),
        !,
        cutStart(T1,T2,T3,T4).
cutStart([H1|T1],[H2|T2],[H1|T1],[H2|T2]):-(H1=='*';H2=='*'),!.	  % konec na hvezdicce

Pozn. hvezdicku subsituuju za neprazdnou posloupnost cisel; oprava, aby to pocitalo i s prazdnou posloupnosti by nemela byt slozita)

Pozn. #2 Tady http://www.forum.matfyz.info/viewtopic.php?f=363&t=2641 někdo řešil stejný příklad, nicméně to pracuje tak, že to jde jedním směrem v obou seznamech a přijde mi, že je to méně efektivní než ten můj alg.

Him wrote:U té trojky jde o binární strom nebo o binární vyhledávací strom? Nemohl byste mi někdo nastínit řešení, všechna má řešení se zdají být hrozně neefektivní.

Nezeptal jsi se dostatečně :) Sice není vyhledávací, ale prvky na dané hladině jsou seřazené (na jejich pořadí záleží). Takže pokud mám hladinu 3 (max. 4 prvky) [a,b,c], tak tu hladinu mohu rekonstruovat jako [nil a b c], [a nil b c], [a b nil c] nebo [a b c nil], nikoli jako **. Muselo to umět na středník vyjmenovat všechny možné stromy s ohledem na tohle omezení.

Nástin:**

hladiny(Strom, Seznam) :- hladiny([Strom], [], [], Seznam).

hladiny([t(L,V,R)|T], VT, ST, Output) :- hladiny(T, [V|VT], [L,R|ST], Output).
hladiny([nil|T], VT, ST, Output) :- hladiny(T, VT, ST, Output).
hladiny([], VT, [], Output) :- reverse(VT, Output).
hladiny([], VT, ST, [O|Output]) :- reverse(VT, O), hladiny(ST, [], [], Output).

strom(Strom, Seznam) :- strom(0, Seznam, [Strom]).

strom(N, [H|T], Output) :-
    N1 is N + 1,
    strom(N1, T, Stromy),
    length(Stromy, L),
    N2 is (2 ^ N) - L,
    nastav().
strom(_, [], []).

nastav(N, [V|T], Stromy, [t(L,V,R)|Output]) :-
    vyber(R, Stromy, N, S1, N1),
    vyber(L, S1, N1, S2, N2),
    nastav(N2, T, S2, Output).
nastav(0, [], [], []).

% -co, +z čeho, +N1, -zbytek, -N2
vyber(nil, S, N1, S, N2) :-
    N1 > 0, % mohu dát nil?
    N2 is N1 - 1.
vyber(H, [H|T], N, T, N).

Snad si to ještě dobře pamatuji :)

Aha, tak to je jiná :) Díky za řešení!

Tu 4 jsem dělal trošku jinak:

match(?,_).
match(_,?).
match(A,A). % :- number(A). pokud je libo :)

odpov([*|A], B) :- reverse(A, RA), reverse(B, RB), odpovt(RA, RB).
odpov(A, [*|B]) :- reverse(A, RA), reverse(B, RB), odpovt(RB, RA).
odpov([A1|A], [B1|B]) :- match(A1, B1), odpov(A, B).
odpov([], []).

odpovt([], _).
odpovt(_, [*|_]).
odpovt([A1|A], [B1|B]) :- match(A1, B1), odpovt(A, B).

BTW: ani jeden z těch kódů jsem nezkoušel, píši je tak, jak si je pamatuji ze zkoušky a oba mi Kryl uznal jako správné.

Martin T. Mne prijde, ze myslenka je stejna. Jen to mas o dost kratsi, takze bych asi mel to svoje reseni trochu zrevidovat, kde by se to dalo zkratit :)

Him wrote:Martin T. Mne prijde, ze myslenka je stejna. Jen to mas o dost kratsi, takze bych asi mel to svoje reseni trochu zrevidovat, kde by se to dalo zkratit :)

Je to hodně podobné, já vím, dal jsem to sem protože mi přijde daleko méně náchylné na chybu. Máš tam spoustu testů a já si vystačil jen s jedním zakomentovaným (protože pokud budu věřit tomu, že vstup je jen 0-9,?,* , tak není potřeba) testem number. :-)

Ad ty hladiny:

%hladiny(+- Strom, +- Hladiny)
hladiny(nil, []).
hladiny(tree(Levy, Hodnota, Pravy), [[Hodnota] | T]) :- hladiny(Levy, TL), hladiny(Pravy, TP), bmerge(TL, TP, T).

bmerge([], X, X).
bmerge(X, [], X).
bmerge([X1|T1], [X2|T2],[X|T]) :- merge(X1, X2, X), bmerge(T1, T2, T).

merge([], X, X).
merge([X|T1], T2, [X|T]) :- merge(T1, T2, T).

A je to oboustranný predikát. Podle mého nejjednodušší řešení.

Slupka: Zkusil jsem vstup: hladiny(X,[[1],[2,3]]). -- a spadne mi z toho prolog, tobe to funguje?
Na dotaz: hladiny(X,[[1]]) -- to vrati dvakrat tree(nil, 1, nil), tj. jednou jsem pouzil strednik a po dalsim stredniku mi zase spadne prolog.

Him wrote:Slupka: Zkusil jsem vstup: hladiny(X,[[1],[2,3]]). -- a spadne mi z toho prolog, tobe to funguje?
Na dotaz: hladiny(X,[[1]]) -- to vrati dvakrat tree(nil, 1, nil), tj. jednou jsem pouzil strednik a po dalsim stredniku mi zase spadne prolog.

Hmm, tak to co jsem psal já, tak je pouze teoreticky správně (Kryl mi to uznal), z důvodu optimalizace výpočtu v SWI-Prologu to nerozdejchá. Ale když jsem si v SWI párkrát kliknul, tak jsem udělal drobnou úpravu (bohužel už nejde jeden obousměrný)

%hladiny(+- Strom, +- Hladiny)

hladiny(nil, []) :- !.
hladiny(tree(Levy, Hodnota, Pravy), [[Hodnota] | T]) :- hladiny(Levy, TL), hladiny(Pravy, TP), bmerge(TL, TP, T).

strom(tree(Levy, Hodnota, Pravy), [[Hodnota] | T]) :- bmerge(TL, TP, T), strom(Levy, TL), strom(Pravy, TP).
strom(nil, [[]]) :- !.
strom(nil, []) :- !.

bmerge([X1|T1], [X2|T2],[X|T]) :- !, merge(X1, X2, X), bmerge(T1, T2, T).
bmerge([], X, X) :- !.
bmerge(X, [], X) :- !.

merge([], X, X).
merge([X|T1], T2, [X|T]) :- merge(T1, T2, T).

Šlupka wrote:A je to oboustranný predikát. Podle mého nejjednodušší řešení.

Pěkné řešení :)

Šlupka wrote:Hmm, tak to co jsem psal já, tak je pouze teoreticky správně (Kryl mi to uznal), z důvodu optimalizace výpočtu v SWI-Prologu to nerozdejchá. Ale když jsem si v SWI párkrát kliknul, tak jsem udělal drobnou úpravu (bohužel už nejde jeden obousměrný)

Je tam este jedna chyba, ktora sposobuje ze napriklad predikat

strom( X, [[1], [2], [3, 4]] ).

vrati false (co je zle).

Opravil som to tak, ze riadok

strom(nil, [[]]) :- !.

som nahradil riadkom

strom(nil, L) :- listOfEmptyLists(L), !.
% kde
listOfEmptyLists([[]]).
listOfEmptyLists([[] | T]) :-listOfEmptyLists(T).