Algorytm Euklidesa
Algorytmy w matematyce
Na lekcjach matematyki używasz pisemnego mnożenia dwóch liczb. Czy umiesz przedstawiać opis słowny ,który wyjaśni ,jak obliczyć iloczyn dwóch liczb. Skrót NWD oznacza największy wspólny dzielnik dwóch lub więcej liczb. Jeden z najbardziej znanych , a jednocześnie najstarszych algorytmów ,liczy NWD. Jego autorem jest żyjący ok. roku 300 p.n.e. Euklides.
Algorytm Euklidesa jest rekurencyjny. Założenia tego algorytmu są proste.Jeśli mamy obliczyć NWD liczb m i n to :
-najpierw sprawdzamy czy liczba n=0
- jeśli tak jest , to NWD liczb m i n = m
-jeśli tak nie jest, to wprowadzamy rekurencyjnie algorytm dla liczb n oraz m mod n), czyli liczymy NWD dla liczb (n,(m mod n))
Przykład1
Obliczmy NWD dla liczb 108 i 138.liczba n to 138 i nie jest równa 0, należy wykonać algorytm dla n i (m mod n),czyli 138 i (108 mod 138) uzyskujemy liczbie 30.Znowu nie otrzymujemy 0.Wykonujemy dalej rekurencyjny algorytm i otrzymujemy liczby 30(108 mod 30)=18.dalej wykonujemy algorytm otrzymujemy 18 i (30 mod 18)czyli 12.Powtarzamy czynność 12 i (18 mod 12)=6;6 i (12 mod 6)=0.druga liczba jest równa 0 to NWD wynosi 6(równe pierwszej liczbie).
Wszystkie etapy teo działania :
NWD(108,138)=NWD (138,108)=NWD (108,30)=NWD (30,18)=NWD (18,12)=NWD (12,6)=NWD (6,0)=6
Przykład2
Kiedy mamy obliczyć największy wspólny dzielnik dla kilku liczb to liczymy NWD dla dwóch pierwszych ,potem dla otrzmanego wyniku i liczby trzeciej itd. dla liczb 84,96,32,24 NWD(84,96,32,24)=NWD (84,NWD(96,NWD932,24)))=NWD (84,NWD(96,8)0=NWD (84,8)=4
Przykład3
Jak zbudować algorytm za pomocą ,ktorego można obliczyć drugą i trzecią potęgę danej liczby?
START
-podaj liczbe a,
-oblicz kwadrat liczby a,
-oblicz sześcian liczby a,
-podaj wartość kwadratu liczby a,
-podaj wartosc sześcianu liczby a.
STOP