-module('dp16a-gy7'). -compile(export_all). -author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu'). -vsn('$LastChangedDate: 2016-11-02 11:19:06 +0100 (Wed, 02 Nov 2016) $$'). %--------------------------------------------------------------------------- % I. RÉSZ: FÁK %--------------------------------------------------------------------------- % 1. fa_noveltje(level) -> level; fa_noveltje({C,Bfa,Jfa}) -> {C+1, fa_noveltje(Bfa), fa_noveltje(Jfa)}. % 2. fa_tukorkepe(level) -> level; fa_tukorkepe({C,Bfa,Jfa}) -> {C, fa_tukorkepe(Jfa), fa_tukorkepe(Bfa)}. % 3. fa_balerteke(level) -> error; fa_balerteke({C,level,_}) -> {ok, C}; fa_balerteke({_,Bfa,_}) -> fa_balerteke(Bfa). fa_jobberteke(level) -> error; fa_jobberteke({C,_,level}) -> {ok, C}; fa_jobberteke({_,_,Jfa}) -> fa_jobberteke(Jfa). % 4. rendezett_fa(level) -> true; rendezett_fa({C,Bfa,Jfa}) -> case fa_jobberteke(Bfa) of error -> true; {ok,J} -> J < C end andalso rendezett_fa(Bfa) andalso case fa_balerteke(Jfa) of error -> true; {ok,B} -> C < B end andalso rendezett_fa(Jfa). % 5. tartalmaz(_, level) -> false; tartalmaz(C, {C,_,_}) -> true; tartalmaz(C, {_,Bfa,Jfa}) -> tartalmaz(C, Bfa) orelse tartalmaz(C, Jfa). % 6. elofordul(_, level) -> 0; elofordul(C, {R,Bfa,Jfa}) -> if C =:= R -> 1; true -> 0 end + elofordul(C, Bfa) + elofordul(C, Jfa). % 7. utak(Fa) -> utak(Fa, []). % @spec utak(F::fa(), Eddigi::ut()) -> CimkezettUtak::[{C::term(), U::ut()}]. % A CimkezettUtak lista az F fa minden csomópontjához egy kételemű ennest % társít, amelynek első eleme (C) a csp. címkéje, második eleme (U) az % Eddigi útvonal és a csp. útvonala összefűzve. utak(level, _) -> []; utak({C,Bfa,Jfa}, Eddigi) -> Eddigi1 = Eddigi ++ [C], % Költséges művelet! [{C, Eddigi} | utak(Bfa, Eddigi1)] ++ utak(Jfa, Eddigi1). % 8. cutak_a(C, Fa) -> [CU || {C0,_} = CU <- utak(Fa), C0 =:= C]. cutak_b(C, Fa) -> cutak(C, Fa, []). % @spec ut(C::term(), F::fa(), Eddigi::ut()) -> % CimkezettUtak::[{C::term(), U::ut()}]. % A CimkezettUtak lista az F fa minden C címkéjű csomópontjához egy kételemű % ennest társít, amelynek első eleme C, második eleme az Eddigi útvonal és % és a csp. útvonala összefűzve. cutak(_, level, _) -> []; cutak(C, {R,Bfa,Jfa}, Eddigi) -> Eddigi1 = Eddigi ++ [R], Cutak = cutak(C, Bfa, Eddigi1) ++ cutak(C, Jfa, Eddigi1), if R =:= C -> [{C, Eddigi} | Cutak]; true -> Cutak end. % 9. cimkek(Fa) -> cimkek(Fa, []). cimkek(level, L) -> L; cimkek({R,Bfa,Jfa}, L) -> cimkek(Bfa, [R|cimkek(Jfa, L)]). %--------------------------------------------------------------------------- % II. RÉSZ: KIVÉTELEK %--------------------------------------------------------------------------- % 10. % Így ha nem két egész hányadosa, akkor function_clause error lesz, % nullával osztás esetén pedig badarith error. hanyados({tort, Sz, N}) when is_integer(Sz), is_integer(N) -> Sz/N. % Így nehézkesebb, de működik: hanyados2({tort, Sz, N}) -> if not is_integer(Sz) ; not is_integer(N) -> error(function_clause); N=:=0 -> error(badarith); true -> Sz/N end. % 11. hanyadosinf(T={tort,Sz,_N}) -> try hanyados(T) catch error:badarith when Sz>0 -> inf % őr csak maximalistáknak, mert a mínusz végtelennel most nem foglalkozunk end. %--------------------------------------------------------------------------- % III. RÉSZ: LUSTA LISTÁK %--------------------------------------------------------------------------- % @type lazy:list() = [] | [Head::any()|fun() -> Tail::lazy:list()]. % Lusta farkú lista: a fej mindig kiértékelődik, a farok lusta. % 12. infseq(N,D) -> [N|fun() -> infseq(N+D,D) end]. % 13. nth(1, [H|_]) -> H; nth(N, [_|T]) -> nth(N-1, T()). % 14. % előadásról bemásolva % @spec map(fun(), lazy:list()) -> lazy:list(). map(_, []) -> []; map(F, [H|T]) -> [F(H)|fun() -> map(F, T()) end]. % előadásról bemásolva %% F = N! (F az N faktorialisa). fac(0) -> 1; fac(N) -> N * fac(N-1). invfacs() -> map(fun(I) -> 1/fac(I) end, infseq(0,1)). % 15. sums([H|T]) -> [H|fun() -> [HT|TT] = T(), sums([HT+H|TT]) end]. % 16. euler(Epsilon) -> Eulers = sums(invfacs()), converge(Eulers, 0, math:exp(1), Epsilon). converge([H|T], N, Target, Epsilon) -> if abs(H-Target) < Epsilon -> {N,H}; true -> converge(T(), N+1, Target, Epsilon) end. test(fa) -> T1 = {4, {3,level,level}, {6, {5,level,level}, {7,level,level}}}, T2 = {a, {b, {x,level,level}, level}, {c, level, {d, {x,{e,level,level},level}, {a, {x,level,level},{x,level,level}}}}}, T3 = {4, {3, {2,level,level}, {1,level,level}}, {6, {5,level,level}, {7,level,level}}}, % lists:foldl(fun erlang:'and'/2, true, [fa_noveltje(T1) =:= {5,{4,level,level},{7,{6,level,level},{8,level,level}}}, fa_tukorkepe(T1) =:= {4,{6,{7,level,level},{5,level,level}},{3,level,level}}, fa_balerteke(T1) =:= {ok, 3}, fa_balerteke(level) =:= error, fa_balerteke(T2) =:= {ok, x}, fa_jobberteke(T1) =:= {ok, 7}, rendezett_fa(T1) =:= true, rendezett_fa(T2) =:= false, rendezett_fa(T3) =:= false, tartalmaz(x, T1) =:= false, tartalmaz(x, T2) =:= true, elofordul(x, T1) =:= 0, elofordul(x, T2) =:= 4, utak(T1) =:= [{4,[]},{3,[4]},{6,[4]},{5,[4,6]},{7,[4,6]}], utak(T2) =:= [{a,[]},{b,[a]},{x,[a,b]},{c,[a]},{d,[a,c]},{x,[a,c,d]}, {e,[a,c,d,x]},{a,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}], cutak_a(x,T1) =:= [], cutak_a(x,T2) =:= [{x,[a,b]},{x,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}], cutak_a(x,T1) =:= cutak_b(x,T1), cutak_a(x,T2) =:= cutak_b(x,T2), cimkek(T1) =:= [3,4,5,6,7] ]; test(egyeb) -> [ [hanyadosteszt(fun hanyados/1, T) || T <- [{tort, 1, 0}, {tort, 0.1, 1}, {tort, 1, 2}]] =:= [badarith, function_clause, 1/2], % abs(hanyados({tort,1,2}) - 1/2) < 0.001, % így illene [hanyadosteszt(fun hanyados2/1, T) || T <- [{tort, 1, 0}, {tort, 0.1, 1}, {tort, 1, 2}]] =:= [badarith, function_clause, 1/2], [hanyadosteszt(fun hanyadosinf/1, T) || T <- [{tort, 1, 0}, {tort, -1, 0}, {tort, 1, 2}]] =:= [inf, badarith, 1/2], begin L1=infseq(3,2), [nth(I,L1) || I<-[1,2,3]] =:= [3,5,7] end, begin L2=invfacs(), [nth(I,L2) || I<-[1,2,3]] =:= [1/(1),1/(1),1/(1*2)] end, abs(nth(10,sums(invfacs())) - math:exp(1)) < 0.001, abs(element(2,euler(0.0001)) - math:exp(1)) < 0.0001 ] % ) . hanyadosteszt(Fun, Tort) -> try Fun(Tort) catch error:Kiv -> Kiv end.