Strona główna > Zajęcia manualne z kodem > Mini-testy w trójkątach.

Mini-testy w trójkątach.

24/04/2009

Zadanie 9 Projektu Eulera polega na odszukaniu takiego trójkąta pitagorejskiego, w którym suma a, b i c wynosi 1000. Z wykorzystaniem mocy nawet niezupełnie współczesnych maszyn (takich, jak moja leciwa stacja robocza) jest to zadanie banalne – w najgorszym przypadku czeka nas wykonanie 1 x 109 mnożeń. Czyli jakieś 48 sekund dla programu w Erlangu czy też dwie i pół minuty dla sześciolinijkowego skryptu w Pythonie. Wniosek jest oczywisty: można rozwiązać to w ładniejszy sposób.

Niestety, moja pamięć zachowała jedynie szkolny wzór w postaci a2 + b2 = c2, należało więc odrobinkę się dokształcić. Ponieważ skorzystanie z półki z książkami wymaga wykonania szeregu skomplikowanych czynności i pewnej pracy fizycznej dlatego postanowiłem spróbować szczęścia z wyszukiwarką. I już pierwszy wynik dla frazy „trójkąt pitagorejski” dostarczył mi łatwo przyswajalnej wiedzy wraz z łopatologicznym rozwiązaniem problemu.

Ponieważ nadal pozostał we mnie niedosyt, dlatego postanowiłem dopisać do modułu jakiś prosty test jednostkowy. Na przykład taki, o jakim pisał Joe Armstrong. W tym przypadku postanowiłem testować funkcję pit/2, zajmującą się obliczaniem współczynników, wg. wcześniej poznanych zasad. Finalny program wygląda tak:

-module(z9b).
-compile(export_all).
%
%
main() ->
    main(2,1).
%
main(M, N) when M > N ->
    {A, B, C} = pit(M,N),
    if
        A+B+C == 1000 -> {A, B, C, A*B*C};
        true          -> main(M, N+1)
    end;
%
main(M, _N) ->
    main(M+1,1).
%
%
pit(M, N) ->
    {M*M-N*N, 2*M*N, M*M+N*N}.
%
%
test() ->
    {3,4,5}    = pit(2,1),
    {5,12,13}  = pit(3,2),
    {15,8,17}  = pit(4,1),
    {7,24,25}  = pit(4,3),
    {11,60,61} = pit(6,5),
    tests_passed.
%

Testowanie oparte jest na prostej cesze języka, mianowicie akceptuje on wyrażenia w postaci:

75> 1=1.
1
76> ala=ala.
ala
77> Zmienna1=3, Zmienna2=3.
3
78> Zmienna1=Zmienna2.
3

Wyrażenia mogą być też zgrupowane:

79> {1, ala, Zmienna1} = {1, ala, Zmienna2}.
{1,ala,3}

Natomiast podanie czegoś w stylu 1=2 czy ala=ula, zaowocuje zrzuceniem błędu badmatch.

83> {1, ala, Zmienna1} = {1, ula, Zmienna2}.

=ERROR REPORT==== 24-Apr-2009::20:05:54 ===
Error in process  with exit value: {{badmatch,{1,ula,3}},[{erl_eval,expr,3}]}

Przygotowany program może więc zachowywać się w następujący sposób:

91> c(z9b).
{ok,z9b}
92> z9b:test().
tests_passed
93> timer:tc(z9b, main, []).
{267,{[wynik ocenzurowano]}}

Oczywiście to bardzo prymitywny mechanizm, dobry dla prostych projektów. Zgodnie z tym, co napisał Joe do „prawdziwych” używa się nieco bardziej zaawansowanych narzędzi. Myślę, że należy mu wierzyć.

PS. Finalny program jest, bagatelka, jakieś sto osiemdziesiąt tysięcy razy szybszy niż wersja korzystająca z metod czołgowych. Przy jednokrotnym uruchomieniu ma to małe znaczenie, ale takie rzeczy lubią chować się w duuuużej pętli i wtedy…

PS2. Zgadza się, tytuł dobrałem tendencyjnie. A kiedyś Was zaskoczę. ;)

%d blogerów lubi to: