Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
Definicja formalna algorytmu jest następująca:
Algorytmem nazywamy uporządkowany, skończony ciąg jednoznacznie określonych operacji, których wykonanie w skończonym czasie nad pewnym zestawem danych daje rozwiązanie pewnej klasy problemów. |
Z definicji tej możemy wywnioskować kilka istotnych cech, które musi spełniać każdy algorytm.
NWD - największy wspólny dzielnik (ang. GCD - Greatest Common Divisor) liczb a i b jest największą liczbą naturalną, która jednocześnie dzieli a i b bez reszty.
Euklides zauważył, że NWD liczb a i b dzieli również ich różnicę. Fakt ten można prosto wyjaśnić geometrycznie:
Przy obliczaniu NWD liczb a i b postępujemy zatem w sposób następujący:
Dopóki liczby a i b są różne, odejmujemy od większej mniejszą. Gdy liczby a i b staną się równe, to NWD(a,b) jest wartością dowolnej z tych liczb.
Krok 1: | Czytaj a,b | ; wczytujemy dane wejściowe |
Krok 2: | Jeśli a = b, to idź do kroku 5 | ; jeśli a = b, to NWD jest a lub b |
Krok 3: | Jeśli a > b, to a ← a - b. Inaczej b ← b - a | ; jeśli a jest różne od b, to od większej liczby odejmujemy mniejszą |
Krok 4: | Idź do kroku 2 | ; wracamy do sprawdzania warunku w kroku 2 |
Krok 5: | Pisz a | ; wypisujemy NWD |
Krok 6: | Zakończ | ; koniec algorytmu |
Symbol startowy, od którego rozpoczyna się wykonanie algorytmu | |
Symbol końca algorytmu | |
Strzałka określa kierunek wykonania. Prowadzi do następnego symbolu w algorytmie. | |
Symbol przetwarzania danych | |
Symbol operacji wprowadzania danych lub wyprowadzania wyników. | |
Symbol decyzyjny. W zależności od wyniku testu idziemy drogą TAK, jeśli test jest spełniony lub drogą NIE, jeśli test nie jest spełniony. |
Schemat blokowy również wymaga specyfikacji danych wejściowych i wyjściowych.
a,b - liczby naturalne, których NWD oblicza algorytm
a lub b - wartość NWD pierwotnych liczb a i b.
// Obliczanie NWD algorytmem Euklidesa // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { int a,b; cin >> a >> b; while(a != b) if(a > b) a -= b; else b -= a; cout << a << endl; return 0; } |
Aby znaleźć NWD, należy wykonać 1000000000 odejmowań! Zastanówmy się, czy nie można przyspieszyć pracy tego algorytmu.
Od liczby większej można odjąć mniejszą tyle razy, ile ta mniejsza się w niej mieści. To co zostanie z większej liczby jest resztą z dzielenia jej przez liczbę mniejszą. Zatem po wykonaniu tej operacji z poprzednich dwóch liczb zostaje zawsze liczba mniejsza (dzielnik) oraz reszta z dzielenia większej liczby przez mniejszą:
Jeśli reszta wynosi zero, to NWD jest równy liczbie mniejszej. Sprawdźmy:
Z powyższych rozważań otrzymujemy następujący algorytm:
Wyjście:
Dane pomocnicze:
Krok 1: | Czytaj a,b | ; wczytujemy dane wejściowe |
Krok 2: | Jeśli b = 0, to idź do kroku 7 | ; jeśli b = 0, to a jest równe NWD |
Krok 3: | r ← reszta z dzielenia a przez b | |
Krok 4: | a ← b | ; liczbę większą zastępujemy mniejszą |
Krok 5: | b ← r | ; liczbę mniejszą zastępujemy resztą |
Krok 6: | Idź do kroku 2 | |
Krok 7: | Pisz a | ; wyprowadzamy wynik |
Krok 8: | Zakończ |
// Obliczanie NWD algorytmem Euklidesa // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { int a,b,r; cin >> a >> b; while(b) { r = a % b; a = b; b = r; } cout << a << endl; return 0; } |
Na podstawie algorytmu Euklidesa zaprojektuj algorytmy:
Obliczania NWW (najmniejszej wspólnej wielokrotności).
Skracania ułamków.
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe