NWD(x, y)
Sep 22
Ostatnio siedząc na lekcjach matematyki w mojej nowej szkole doszedłem do wniosku, że prawie wszystko, co jest użyte w matematyce da się przedstawić w postaci kodu. Dostałem kilka zadań domowych dotyczące wyliczenia największego wspólnego dzielnika liczb A i B używając algorytmu Euklidesa. Pikuś, ale mnie się nie chce liczyć… Dla równie leniwych stworzyłem prosty kalkulator (kliknij tutaj aby otworzyć)
Założenia są proste:
- Podziel liczbę A przez B, wyciągnij liczbę całkowitą z dzielenia (oznacz K), czyli ile razy B mieści się w A
- Pobierz resztę (oznacz R) z dzielenia odejmując A od B * K
- Jeżeli R = 0 to NWD(A, B) jest równe B, jeżeli nie podstaw:
- A = B, B = R, po przypisaniu wróć do pkt 1
Działa pięknie :) Nie ma to jak leniwy programista…
A powiedz mi, czego, co jest “użyte w matematyce” nie da się przedstawić w postaci kodu?
@scanner: nie jestem w stanie Ci powiedzieć, bo nie jestem zorientowany w matematyce, co więcej… dopiero zaczynam swoja przygodę z tym przedmiotem tak na poważnie.
Póki co, chyba wszytsko da się przedstawić w postaci kodu, nawet operacje na zbiorach liczbowych (obiekty z elementami w tablicy), logikę (przecież to instrukcje warunkowe).
Narazie mogę stwierdzić, że wszystko co przerabiamy (a jest to pewnie niewiele) przekładam sobie na język programowania, bo inaczej bym tego nie skumał :)
Wszak algebra to podstawa wszelakich struktur danych w tym OOP. Bez tego ani rusz, więc watro się pouczyć.
Zawsze twierdziłem, że komputer powstał po to, żeby liczyć za mnie. Nigdy mi się nie chciało np. mnożyć macierzy ręcznie ;)
Informatka leży u podstaw Matematyki. NWD to algorytm dobry dla 2 klasy szkoły średniej. Może pierwszej. Ucz się matematyki. Ona uczy algorytmów :) I jak powiedział Scanner – wszystko co matematyczne da się przedstawić w Zero Jeden.
Ameryki nie odkryłeś :) Nie znalazłem jeszcze rzeczy, której nie da się policzyć za pomocą któregoś języka programowania (nieraz jest to dość trudne, patrz całki, ale wykonalne)
To jest ten gorszy z algorytmów do liczenia NWD :P
Lepszy polega na odejmowaniu od siebie tych liczb, jak poszukasz to znajdziesz.
Co do tego czy da się wszystkie problemy matematyki przenieść do komputera, może się da ale to jest często bardzo ciężkie. Do tego wspomniane mnożenie macierz aby było poprawne numerycznie i wydajne nie jest takie proste… no właśnie przy obliczeniach na komputerze najgorszą rzeczą jest poprawność numeryczna. Np. metoda Gaussa jest w pierwotnej wersji niepoprawna numerycznie… Ale to jest temat który jest ciężki, a sam jakoś nigdy w niego nie wnikałem.
Podzielę opinie przedmówcy, otóż w wyniku zastosowania dzielenia modulu w przedstawionym przez Ciebie algorytmie ilość wykonanych operacji elementarnych zwrasta kilkunastokrotnie dla dużych liczb. W Twojej wersji algorytmu występuje znacznie więcej operacji elementarnych niż w jego pierwotnej wersji którą to wymyślił Euklides. Otóż zauważ, że jeżeli algorytm napisany by był według poniższych kroków:
1. Jeżeli a != b, przejdź do kroku 2, w przeciwnym wypadku przejdź do kroku 3.
2. Jeżeli a > b to a = b – a w przeciwnym wypadku b = b – a;
3. Wypisz a.
Byłby znacznie szybszy… a czas działania algorytmu rzecz jasna efektywniejszy.
A co do poprawności numerycznej obliczania układów równań liniowych metodą Gaussa, swego czasu ją implementowałem… implementacja jest banalna, wystarczy tylko dobrze zrozumieć algorytm, a sprowadza się on do uzyskania macierzy trójkątnej, a następnie jej obliczenia – jest to metoda szybka i dająca bardzo dobre rezultaty. Jest z nią jeden problem, mianowicie kiedy na przekątnej głównej macierzy występują zera, ale i to można obejść poprzez odpowiednie wybieranie równań do eliminacji w algorytmie. Więc metoda ta nie stwarza żadnych problemów. Natomiast inaczej sytuacji się przedstawia w przypadku np.
- dla interpolacji – metody Lagrange’a, bądź
- dla całkowania – metoda Prostokątów.
Metody te obarczone są dość dużymi błędami wynikającymi z dokładności algorytmów.
Ogólnie błędy wyników metod numerycznych związane są z:
- oceną dokładności działania algorytmu metody – z jakim przybliżeniem działa i jak jest dokładny,
- dokładnością i ilością danych wejściowych, jeżeli dane te będą mało dokładne lub będzie ich mało, wynik może być obarczony błędem,
- błedami popełnionymi przez komputer w trakcie konwersji liczb pomiędzy układami liczbowymi jak i reprezentacją tych liczb w pamięci komputera,
- błędnymi związanymi z zaokrągleniami liczb.
Co się tyczy metod numerycznych miałem z tego egzamin rok temu, więc jeszcze co nieco pamiętam. Świetny przedmiot, polecam każdemu!
Pozdrawiam ;-)
Mała poprawka algorytmu, zorientowałem się dopiero po wysłaniu, a nie ma opcji edycji :-)
1. Jeżeli a != b, przejdź do kroku 2, w przeciwnym wypadku przejdź do kroku 3.
2. Jeżeli a > b to a = b – a w przeciwnym wypadku b = b – a;
Przejdź do kroku 1.
3. Wypisz a.
@Jakub Kozicki
Pamiętaj że Ty wiesz o tym że trzeba wybierać elementy i jest jeszcze parę rzeczy w metodzie Gaussa, które trzeba robić. Ale większość osób o tym nie ma zielonego pojęcia.
Tak jak banalna rzecz wymnożenie wszystkich elementów tablicy (zmiennoprzecinkowych), gdyby robić to na pałę może wyjść bardzo zły wynik (zakładając że są liczby bardzo małe i duże, oraz że jest ich sporo), dlatego przed mnożeniem dla poprawności numerycznej powinno się posortować tablicę i mnożyć od najmniejszych elementów, wtedy błąd będzie zminimalizowany.
Ale to wszystko trzeba się nauczyć, ale najpierw trzeba “wiem, że nie wiem”;)
Można też trochę prościej, dla przykładu kod w pythonie:
def nwd(a,b):
return a if b==0 else nwd(b,a%b)