Danymi wejściowymi są dwie liczby naturalne, dla których szukamy NWD. Najpierw obliczamy resztę z dzielenia dwóch wybranych liczb. Następnie wartość drugiej z tych liczb przypisujemy, jako wartość pierwszej, a obliczoną wcześniej resztę z dzielenia zapisujemy jako drugą z tych liczb. Otrzymujemy dwie nowe liczby, dla których powtarzamy powyższy cykl operacji, dopóki druga z liczb nie będzie równa 0. Na koniec działania algorytmu największym wspólnym dzielnikiem jest pierwsza z tych liczb.
Aby można było łatwiej to sobie wyobrazić zapiszemy dwie liczby wejściowe jako a oraz b, gdzie a,b należą do zbioru liczb naturalnych.
- Oblicz resztę z dzielenia liczb a i b.
- Przypisz liczbie a liczbę b.
- Przypisz liczbie b resztę z dzielenia liczb a i b obliczoną w pierwszym kroku.
- Jeśli b jest różne od zera, przejdź do kroku 1.
Poniżej prezentuję program w języku C++ implementujący algorytm Euklidesa wykorzystujący operator modulo (reszty z dzielenia):
#include <iostream> using namespace std; int main() { int a, b, c; cout << "Wprowadz dwie liczby: "; cin >> a; cin >> b; while (b != 0) { c = a%b; a = b; b = c; } cout << "NWD tych liczb to: " << a << endl; return 0; }
Jest to pierwsza możliwa implementacja algorytmu Euklidesa stosującego resztę z dzielenia. Istnieje jeszcze jedna możliwa stosująca odejmowanie, ale o niej za chwilę. Zajmiemy się omówieniem programu. Najpierw tworzymy 3 zmienne a, b, c reprezentujące liczby całkowite. Następnie wartości liczb a oraz b pobieramy ze standardowego wejścia za pomocą obiektu cin. Wykonujemy pętlę while dopóki liczba b nie będzie równa 0. Wewnątrz pętli do zmiennej c przypisujemy resztę z dzielenia liczb a i b. Potem do liczby a przypisujemy liczbę b, a do liczby b przypisujemy wartość zmiennej c, czyli naszą resztę z dzielenia. Jeśli b równe jest zeru wychodzimy z pętli, w przeciwnym wypadku wracamy na jej początek. Po wyjściu z pętli pozostaje nam tylko wypisanie liczby a będącej największym wspólnym dzielnikiem na standardowe wyjście przy pomocy obiektu cout.
Druga implementacja tego algorytmu korzysta nie z operatora modulo i reszty z dzielenia, lecz z odejmowania liczb od siebie. Jest nieco wolniejsza, gdyż trzeba wykonać sporą liczbę odejmowań dla liczb, które się sporo od siebie różnią, jednak warto o niej wspomnieć. Danymi wejściowymi tutaj również są dwie liczby naturalne a, b. Algorytm polega na tym, że dopóki któraś z liczb nie osiągnie zera odejmujemy większą od mniejszej. Po czym większą z liczb zastępujemy różnicą tych liczb i tak do zera.
- Oblicz różnicę liczb a i b.
- Przypisz większej liczbie różnicę obliczoną w kroku pierwszym.
- Jeśli a i b są różne od zera, przejdź do kroku 1.
Program w języku C++ implementujący algorytm Euklidesa stosujący odejmowanie:
#include <iostream> using namespace std; int main() { int a, b, c; cout << "Wprowadz dwie liczby: " << endl; cin >> a; cin >> b; while (a != 0 && b != 0) { if (a > b) { c = a - b; a = c; } else { c = b - a; b = c; } } cout << "NWD: " << a + b << endl; return 0; }
Tak jak w poprzedniej implementacji i tutaj będą nam potrzebne trzy zmienne a, b i c będące typem całkowitym. Wprowadzamy je ze standardowego wejścia. Następnie deklarujemy pętlę while, która wykonuje się dopóki a i b są różne od zera. Wewnątrz pętli stosujemy instrukcję warunkową. W przypadku, gdy a jest większe od b, przypisujemy do zmiennej c różnicę liczb a i b. Następnie do zmiennej a przypisujemy zmienną c, czyli otrzymaną różnicę. W innych przypadkach tj. gdy a jest mniejsze lub równe b, przypisujemy do zmiennej c różnicę liczb b i a, po czym inicjujemy zmienną b za pomocą wartości tej różnicy. Gdy pętla zakończy swe działanie, któraś ze zmiennych (a lub b) przechowuje największy wspólny dzielnik wobec czego najprostszą metodą, aby go odczytać nie stosując instrukcji warunkowych jest dodanie obu wartości, gdyż jedna z nich na pewno jest równa zeru. Sumę obu wartości wypisujemy na standardowe wyjście, co jest równoznaczne z wypisaniem NWD.
Brak komentarzy:
Prześlij komentarz