W poprzedniej odsłonie dotyczącej tematu NWW i NWD wspomniałem o tym, że dość często do wyznaczania NWD stosuje się tak zwany algorytm Euklidesa. Jest on prostym i szybkim algorytmem (sposobem) obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych. Być może warto poświęcić mu nieco uwagi, zwłaszcza że wydaje mi się, iż mam do zaproponowania ciekawy sposób realizacji tego algorytmu.
Algorytm Euklidesa najczęściej stosuje się do wyznaczania NWD większych liczb. Dlaczego? Przede wszystkim dlatego, że tradycyjny rozkład na czynniki pierwsze zajmie nam wówczas znacznie więcej czasu aniżeli za pomocą tego algorytmu. Pamiętajmy jednak, że oba sposoby są poprawne i można stosować je zamiennie.
W takim razie zobaczmy na czym polega ten algorytm, którego nazwa jest związana z nazwiskiem słynnego matematyka.
Oficjalna recepta na wyznaczenie NWD dla dwóch liczb za pomocą algorytmu Euklidesa:
KROK 1:
1. Wpisujemy większą liczbę w pierwszą kolumnę (dzielna).
2. Wpisujemy mniejszą liczbę w trzecią kolumnę (dzielnik).
3. Obliczamy liczbę całkowitą z dzielenia dzielnej przez dzielnik (całość).
4. W ostatniej kolumnie wpisujemy resztę z powyższego dzielenia (reszta z dzielenia).
KROK 2:
1. Dzielnik z pierwszego wiersza staje się dzielną w drugim wierszu.
2. Reszta z dzielenia z pierwszego wiersza staje się dzielnikiem w drugim wierszu.
3. Obliczamy liczbę całkowitą z dzielenia dzielnej przez dzielnik (całość).
4. W ostatniej kolumnie wpisujemy resztę z powyższego dzielenia (reszta z dzielenia).
KROK 3: Powtarzamy krok drugi (poprzedni) aż do uzyskana reszty zerowej (brak reszty).
KROK 4: Liczba, która jest przedostatnią resztą (tzn. ta poprzednia przed zerową) stanowi nasz NWD dla szukanych liczb.
Zerknijmy teraz na tabelę w której zostaną przedstawione dwa przykłady.
Przykład 1: wyznaczenie NWD dla liczb 3200 i 1408.
Algorytm Euklidesa najczęściej stosuje się do wyznaczania NWD większych liczb. Dlaczego? Przede wszystkim dlatego, że tradycyjny rozkład na czynniki pierwsze zajmie nam wówczas znacznie więcej czasu aniżeli za pomocą tego algorytmu. Pamiętajmy jednak, że oba sposoby są poprawne i można stosować je zamiennie.
W takim razie zobaczmy na czym polega ten algorytm, którego nazwa jest związana z nazwiskiem słynnego matematyka.
Oficjalna recepta na wyznaczenie NWD dla dwóch liczb za pomocą algorytmu Euklidesa:
KROK 1:
1. Wpisujemy większą liczbę w pierwszą kolumnę (dzielna).
2. Wpisujemy mniejszą liczbę w trzecią kolumnę (dzielnik).
3. Obliczamy liczbę całkowitą z dzielenia dzielnej przez dzielnik (całość).
4. W ostatniej kolumnie wpisujemy resztę z powyższego dzielenia (reszta z dzielenia).
KROK 2:
1. Dzielnik z pierwszego wiersza staje się dzielną w drugim wierszu.
2. Reszta z dzielenia z pierwszego wiersza staje się dzielnikiem w drugim wierszu.
3. Obliczamy liczbę całkowitą z dzielenia dzielnej przez dzielnik (całość).
4. W ostatniej kolumnie wpisujemy resztę z powyższego dzielenia (reszta z dzielenia).
KROK 3: Powtarzamy krok drugi (poprzedni) aż do uzyskana reszty zerowej (brak reszty).
KROK 4: Liczba, która jest przedostatnią resztą (tzn. ta poprzednia przed zerową) stanowi nasz NWD dla szukanych liczb.
Zerknijmy teraz na tabelę w której zostaną przedstawione dwa przykłady.
Przykład 1: wyznaczenie NWD dla liczb 3200 i 1408.
A teraz znacznie bardziej twórczy algorytm na wyznaczenie NWD dla dwóch liczb za pomocą algorytmu Euklidesa (jako bajka dla dzieci poziomu 10-11 lat):
KROK 1:
1. Wpisujemy większą liczbę w kolumnę o nazwie PANI. Dlaczego? Ponieważ pani ma pierwszeństwo i przechodzi w drzwiach jako pierwsza.
2. Wpisujemy mniejszą liczbę w kolumnę o nazwie PAN. Inaczej mówiąc, PAN wchodzi za PANIĄ i zamyka drzwi za nią (taki oto dżentelmen).
3. Obliczamy liczbę całkowitą z dzielenia PANI przez PANA i wpisujemy w kolumnę o nazwie całość.
4. W ostatniej kolumnie wpisujemy resztę z powyższego dzielenia (reszta z dzielenia). Można powiedzieć, że przy podziale PANI przez PANA powstaje całość, a do tego jeszcze reszta (dodatek). I ona jest bardzo ważna, bo będzie siadała na miejsce PANA.
KROK 2:
1. PAN z pierwszego wiersza wchodzi na miejsce PANI w wierszu drugim.
2. Reszta z dzielenia z pierwszego wiersza zajmuje miejsce PANA także w wierszu drugim.
3. Postępujemy tak jak poprzednio - czyli powtarzamy punkty 3 i 4 z poprzedniego kroku.
KROK 3: Powtarzamy krok drugi (poprzedni) aż do uzyskana reszty zerowej (brak reszty).
KROK 4: Liczba, która jest przedostatnią resztą (tzn. ta poprzednia przed zerową) stanowi nasz NWD dla szukanych liczb.
W naszym pierwszym przykładzie NWD dla liczb 3200 i 1408, to 128. Warto zobaczyć poniżej, że przy pomocy tradycyjnego rozkładu również otrzymamy tę samą wartość (liczbę). Różnica polega na tym, że nie zawsze jest tak łatwo ręcznie przeprowadzić rozkład obu liczb (w drugim przykładzie będzie to bardziej widoczne). Stąd bardziej efektywny sposób, czyli zastosowanie algorytmu Euklidesa.
Przykład 2: wyznaczenie NWD dla liczb 2618 i 1615. Całość procesu przebiega analogicznie jak w poprzednim przypadku. Warto zwrócić uwagę na to, że pomimo dłuższego rozpisania, za pomocą algorytmu Euklidesa będziemy mogli szybciej odnaleźć NWD.
Jeśli już dobrze opanujemy wyznaczenie NWD dla dwóch liczb, wówczas znacznie łatwiejsze będzie znajdywanie NWW.
Wiele osób słyszało o tym, że NWW jest definiowana wzorem, ale raczej wolą od niego trzymać się z daleka. Dlaczego? Otóż wydaje się on dość niezrozumiały, ale za chwilę zobaczymy, że... w rzeczywistości jest prosty jak drut!
Oto wzór na wyznaczanie Najmniejszej Wspólnej Wielokrotności: NWW(a,b) = a*b / NWD(a,b). Wygląda naprawdę świetnie, prawda? (a i b, to dowolne liczby całkowite).
A teraz spróbujemy przełożyć to zagadnienie z języka matematycznego na język 5-letniego dziecka. Niemożliwe?! No to przekonajmy się czy aby na pewno!
Jeżeli mamy dwie liczby całkowite, to obliczenie NWW wymaga tylko dwóch kroków:
1. Znajdujemy (wyznaczamy) NWD. Jak już wiemy możemy go zrealizować albo rozkładając podane liczby na czynniki pierwsze (dla małych liczb) albo za pomocą algorytmu Euklidesa (dla dużo większych liczb). Wybór oczywiście należy do nas.
2. Mnożymy przez siebie obie liczby, a następnie dzielimy przez wyznaczoną przed chwilą wartość NWD.
Zobaczmy na kilku przykładach jak prosto to wygląda. Ostrzegam, że jeśli nadal wierzysz, iż wyznaczanie NWW lub NWD jest naprawdę trudne, to po przejrzeniu tego rysunku możesz naprawdę potrzebować kilka głębszych oddechów...
Tak, to aż tak trudne. Ja również przecierałem wiele razy oczy ze zdziwienia. Jeśli to wyjaśnienie na powyższych przykładach zrobiło na tobie wrażenie, to znaczy, że moja praca okazała się wartościowa i zarazem przydatna.
Podsumowanie: Teraz zapewne zastanawiasz się do czego będą przydatne te NWW i NWD. Przecież o nich raczej nie słyszałeś, więc podejrzewasz, że to materiał na tyle abstrakcyjny, że nie warto sobie nim zaprzątać głowy. Czy tak rzeczywiście jest postaram się przekonać cię w następnym odcinku. Okazuje się bowiem, że tak niewinny i często zupełnie pomijamy temat może mieć więcej znaczenia i zastosowań praktycznych niż podpowiada nam intuicja.
Do spotkania następnym razem... ale zanim to nastąpi, to wcześniej serdecznie zachęcam do kilkukrotnego przeczytania tego zagadnienia (obu części) jak też do poćwiczenia na wybranych przykładach. Dzięki temu kolejna odsłona będzie miała dla ciebie jeszcze więcej sensu i wartości.
Poniżej podrzucam moim zdaniem ciekawe i przydatne bądź też wartościowe linki:
1. Najmniejsza wspólna wielokrotność - można wstawiać własne liczby i sprawdzać czy są zgodne z twoim rozwiązaniem.
http://www.math.edu.pl/narzedzia.php?opcja=nww
2. Największy wspólny dzielnik - można wstawiać własne liczby i sprawdzać czy są zgodne z twoim rozwiązaniem.
http://www.math.edu.pl/narzedzia.php?opcja=nwd
3. Algorytm Euklidesa - to taka mała ściągawka, która omawia w skrócie to co mi zajmuje 2-3 razy więcej miejsca.
http://www.math.edu.pl/algorytm-euklidesa
4. Algorytm Euklidesa - klasyczne ujęcie algorytmy przez Mistrza Matemaksa (czyli Michał Budzyński przedstawia).
https://www.matemaks.pl/algorytm-euklidesa.html
Wiele osób słyszało o tym, że NWW jest definiowana wzorem, ale raczej wolą od niego trzymać się z daleka. Dlaczego? Otóż wydaje się on dość niezrozumiały, ale za chwilę zobaczymy, że... w rzeczywistości jest prosty jak drut!
Oto wzór na wyznaczanie Najmniejszej Wspólnej Wielokrotności: NWW(a,b) = a*b / NWD(a,b). Wygląda naprawdę świetnie, prawda? (a i b, to dowolne liczby całkowite).
A teraz spróbujemy przełożyć to zagadnienie z języka matematycznego na język 5-letniego dziecka. Niemożliwe?! No to przekonajmy się czy aby na pewno!
Jeżeli mamy dwie liczby całkowite, to obliczenie NWW wymaga tylko dwóch kroków:
1. Znajdujemy (wyznaczamy) NWD. Jak już wiemy możemy go zrealizować albo rozkładając podane liczby na czynniki pierwsze (dla małych liczb) albo za pomocą algorytmu Euklidesa (dla dużo większych liczb). Wybór oczywiście należy do nas.
2. Mnożymy przez siebie obie liczby, a następnie dzielimy przez wyznaczoną przed chwilą wartość NWD.
Zobaczmy na kilku przykładach jak prosto to wygląda. Ostrzegam, że jeśli nadal wierzysz, iż wyznaczanie NWW lub NWD jest naprawdę trudne, to po przejrzeniu tego rysunku możesz naprawdę potrzebować kilka głębszych oddechów...
Tak, to aż tak trudne. Ja również przecierałem wiele razy oczy ze zdziwienia. Jeśli to wyjaśnienie na powyższych przykładach zrobiło na tobie wrażenie, to znaczy, że moja praca okazała się wartościowa i zarazem przydatna.
Podsumowanie: Teraz zapewne zastanawiasz się do czego będą przydatne te NWW i NWD. Przecież o nich raczej nie słyszałeś, więc podejrzewasz, że to materiał na tyle abstrakcyjny, że nie warto sobie nim zaprzątać głowy. Czy tak rzeczywiście jest postaram się przekonać cię w następnym odcinku. Okazuje się bowiem, że tak niewinny i często zupełnie pomijamy temat może mieć więcej znaczenia i zastosowań praktycznych niż podpowiada nam intuicja.
Do spotkania następnym razem... ale zanim to nastąpi, to wcześniej serdecznie zachęcam do kilkukrotnego przeczytania tego zagadnienia (obu części) jak też do poćwiczenia na wybranych przykładach. Dzięki temu kolejna odsłona będzie miała dla ciebie jeszcze więcej sensu i wartości.
Poniżej podrzucam moim zdaniem ciekawe i przydatne bądź też wartościowe linki:
1. Najmniejsza wspólna wielokrotność - można wstawiać własne liczby i sprawdzać czy są zgodne z twoim rozwiązaniem.
http://www.math.edu.pl/narzedzia.php?opcja=nww
2. Największy wspólny dzielnik - można wstawiać własne liczby i sprawdzać czy są zgodne z twoim rozwiązaniem.
http://www.math.edu.pl/narzedzia.php?opcja=nwd
3. Algorytm Euklidesa - to taka mała ściągawka, która omawia w skrócie to co mi zajmuje 2-3 razy więcej miejsca.
http://www.math.edu.pl/algorytm-euklidesa
4. Algorytm Euklidesa - klasyczne ujęcie algorytmy przez Mistrza Matemaksa (czyli Michał Budzyński przedstawia).
https://www.matemaks.pl/algorytm-euklidesa.html
5. Obliczanie NWD i NWW w nieco pogłębionym wydaniu. Można porównać opracowanie na podanej stronie z moim na tym blogu.
https://matematyka.opracowania.pl/obliczanie_nwd_i_nww/
Brak komentarzy:
Prześlij komentarz
Jeśli chcesz, aby twoja wiadomość nie została odrzucona przez system jako spam (usunięte), to podpisz się swoim imieniem lub pseudonimem. Dziękuję :)