Matematyka
 
Brak innych książek z tego przedmiotu
 
Autorzy: Joanna Czarnowska, Jolanta Wesołowska, Wojciech Babiański, Lech Chańko
Wydawnictwo: Nowa Era
Rok wydania: 2014
Sformułuj algorytm wyznaczania największego wspólnego dzielnika 4.2 gwiazdek na podstawie 5 opinii

 

1. Wyznaczamy NWD dwóch liczb, na przykład NWD(x,y) i oznaczamy je jako w. 

2. Wyznaczamy NWD pozostałej liczby i w (NWD(z, w)). 

 

W każdym przykładzie mamy już zapisane liczby w postaci rozkłądu na czynniki pierwsze. 

Aby znaleźć NWD bierzemy tylko te czynniki pierwsze, które pojawiają się w rozkładzie obu liczb - jeśli w obu liczbach występuje ten sam czynnik pierwszy, ale w różnych potęgach, to bierzemy mniejszą potęgę. Jeśli czynnik występuje tylko w jednej liczbie, to nie bierzemy go do iloczynu. 

 

Zgodnie z algorytmem najpierw wyznaczamy NWD dwóch pierwych liczb:

 

NWD(x, y) oznaczamy jako w:

 

Wyznaczamy NWD danych trzech liczb, czyli NWD ostatniej liczby i liczby w:

 

 

 

 

 

Wyznaczamy NWD(x,y). Zauważmy, że nie ma sensu wymnażać, ponieważ dalej będziemy szukać NWD(z, w)