Zk 11.6.2009
-
- Matfyz(ák|ačka) level I
- Příspěvky: 39
- Registrován: 7. 11. 2007 22:12
- Typ studia: Informatika Bc.
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
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
Re: Zk 11.6.2009
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
Díky
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
- kaja
- Matfyz(ák|ačka) level II
- Příspěvky: 99
- Registrován: 20. 12. 2007 00:53
- Typ studia: Informatika Bc.
- Login do SIS: bilek7am
- Bydliště: Miðgarðr
- Kontaktovat uživatele:
Re: Zk 11.6.2009
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ě)
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ě)
PONIES
Re: Zk 11.6.2009
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.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zk 11.6.2009
(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:
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.
Jestli jsem to pochopil správně, tak ta 4, by mohla vypadat takto:
Kód: Vybrat vše
/*
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. #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.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zk 11.6.2009
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í.Him píše: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í.
Nástin:
Kód: Vybrat vše
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).
Re: Zk 11.6.2009
Aha, tak to je jiná Díky za řešení!
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zk 11.6.2009
Tu 4 jsem dělal trošku jinak:
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é.
Kód: Vybrat vše
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).
Re: Zk 11.6.2009
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
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zk 11.6.2009
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.Him píše: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
-
- Matfyz(ák|ačka) level I
- Příspěvky: 39
- Registrován: 7. 11. 2007 22:12
- Typ studia: Informatika Bc.
Re: Zk 11.6.2009
Ad ty hladiny:
A je to oboustranný predikát. Podle mého nejjednodušší řešení.
Kód: Vybrat vše
%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í.
Re: Zk 11.6.2009
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.
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.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
-
- Matfyz(ák|ačka) level I
- Příspěvky: 39
- Registrován: 7. 11. 2007 22:12
- Typ studia: Informatika Bc.
Re: Zk 11.6.2009
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ý)Him píše: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.
Kód: Vybrat vše
%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).
Re: Zk 11.6.2009
Pěkné řešeníŠlupka píše:A je to oboustranný predikát. Podle mého nejjednodušší řešení.
- the21st
- Matfyz(ák|ačka) level I
- Příspěvky: 38
- Registrován: 23. 1. 2008 13:42
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Zk 11.6.2009
Je tam este jedna chyba, ktora sposobuje ze napriklad predikatŠlupka píše: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ý)
Kód: Vybrat vše
strom( X, [[1], [2], [3, 4]] ).
Opravil som to tak, ze riadok
Kód: Vybrat vše
strom(nil, [[]]) :- !.
Kód: Vybrat vše
strom(nil, L) :- listOfEmptyLists(L), !.
% kde
listOfEmptyLists([[]]).
listOfEmptyLists([[] | T]) :-
listOfEmptyLists(T).