Największy wspólny dzielnik – implementacje

W poprzednim wpisie omawialiśmy czym są dzielniki liczb i jak je w sposób programistyczny znaleźć. Kolejnym, ważnym algorytmem jest algorytm znajdowania największego wspólnego dzielnika dwóch liczb. Wielu z Was pewnie teraz puka się po głowie, myśląc „po co to, na co to komu?”, jednak z algorytmem tym można się spotkać nawet w sytuacji codziennej. Wyobraź sobie, że masz ułamek 850/6625, a twoim zadaniem jest przedstawić go w postaci nieskracalnej. Co robisz jako pierwsze? Szukasz liczby, która podzieli jednocześnie licznik i mianownik bez pozostawiania reszty. Jako pierwsza na myśl nasuwa się liczba pięć — po skróceniu mamy 170/1325 — znowu możemy skrócić przez 5. Ułamek ten w postaci nieskracalnej wynosi więc 34/265. Podzieliliśmy obie liczby dwukrotnie przez 5, co oznacza, że ich największym wspólnym dzielnikiem była liczba 25. W ten sposób, choć może nieświadomie, wyznaczasz największy wspólny dzielnik dla dwóch liczb.  W dzisiejszym wpisie omówimy zatem jak wyznaczyć NWD dwóch liczb naturalnych i przedstawimy sobie implementacje w trzech popularnych językach programowania.

Algorytm wyznaczania największego wspólnego dzielnika

Zanim zaczniemy tworzyć implementacje, skonstruujemy najpierw algorytm, który opierać będziemy na istniejącym już algorytmie Euklidesa — wybitnego, greckiego matematyka. Skoro wyznaczamy NWD dwóch liczb, to musimy najpierw je pobrać od użytkownika — oznaczymy je jako n i k. Z racji, iż nie narzucamy użytkownikowi, że ma najpierw podać liczbę mniejszą, a potem większą, musimy w algorytmie rozróżnić która jest większa, a która mniejsza. Jeżeli więc n>k, to przy użyciu operatora modulo wyznaczymy resztę z dzielenia z n/k. W przeciwnym wypadku wyznaczymy resztę dzielenia z k/n. Jeżeli reszta ta będzie równa 0 (co oznacza, że liczba mniejsza jest dzielnikiem pierwszej), to drukujemy mniejszą liczbę jako wynik. W przeciwnym wypadku wywołujemy algorytm od nowa, z tym że wprowadzona zostanie mniejsza z tych dwóch liczb oraz wspomniana reszta z dzielenia.

Zjawisko, w którym algorytm wywołuje sam siebie, nazywamy rekurencją, o której przeczytasz dokładniej tutaj. Algorytm będzie wykonywał się, dopóki nie natrafi sytuacji, w której liczby będą przez siebie podzielne — będzie oznaczało to koniec jego pracy i odnalezienie wyniku. Algorytm ten możemy przedstawić na schemacie blokowym:

Schemat blokowy algorytmu wyznaczającego największy wspólny dzielnik dwóch liczb

Wyznaczanie największego wspólnego dzielnika w C++, Java i Python

Mając już rozpisany algorytm, możemy przystąpić do jego implementacji. Algorytm wyznaczania NWD pojawia się w wymaganiach na maturę z informatyki, dlatego postanowiłem pokazać jak zaimplementować go w trzech językach, które mamy do wyboru decydując się na to rozszerzenie.

Największy wspólny dzielnik – implementacja C++

Największy wspólny dzielnik – implementacja Java

Największy wspólny dzielnik – implementacja Python

Największy wspólny dzielnik — ciekawostki

  • Aby obliczyć NWD dla trzech liczb, wystarczy wyznaczyć p = NWD dwóch pierwszych liczb, a następnie policzyć NWD dla wcześniej p i ostatniej liczby.
  • Największy wspólny dzielnik możemy inaczej zapisać jako iloczyn liczb pierwszych, będących wspólnymi czynnikami dla obu liczb.
  • Pierwsze wzmianki o tym algorytmie znajdziemy w dziele „Elementy” Euklidesa — stąd też jego nazwa
  • NWD możemy użyć, aby obliczyć najmniejszą wspólną wielokrotność, o czym dowiesz się tutaj

Algorytm wyznaczania największej wspólnej wielokrotności to tylko jeden z wielu wymaganych przez CKE. Listę pozostałych algorytmów, wraz z odnośnikami do ich omówienia znajdziesz w tym wpisie.

grupa wsparcia matura z informatyki
You Might Also Like
1 Comment
Dodaj komentarz

icon