Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
Jednym z podstawowych pojęć w informatyce jest algorytm (ang. algorithm). Słowo algorytm wywodzi się od arabskiego matematyka Muhammada ibn Mūsā al-Khwārizmī (arab. أبو عبد الله محمد بن موسى الخوارزمي,) który żył w latach od około 780 r. do około 850 r. Napisał on wiele dzieł rozwijających algebrę. W dziełach tych stosował opisy kolejnych operacji, które należy wykonać w celu rozwiązania np. równania kwadratowego.
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.
Algorytm opisujemy słowami przedstawiając kolejne operacje oraz sposób ich wykonania. Dla przykładu przedstawimy algorytm Euklidesa znajdowania NWD.
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.
Przykład:
Mamy liczby 21 i 18. Dopóki się nie zrównają od większej odejmujemy mniejszą:
(21,18) → (21-18,18)
(3,18) → (3,18-3)
(3,15) → (3,15-3)
(3,12) → (3,12-3)
(3,9) → (3,9-3)
(3,6) → (3,6-3)
(3,3) - koniec, NWD(21,18) = 3
Wykonanie algorytmu opisujemy przedstawiając kolejne kroki tego procesu. W każdym kroku opisujemy zwięźle wykonywaną operację. Istnieją pewne zasady tego opisu, które poznasz analizując kolejne algorytmy. Kroki są numerowane i wykonywane zgodnie z numerami, o ile nie zostanie nakazane inaczej. Przed listą kroków należy umieścić tzw. specyfikację danych. Jest to opis danych wejściowych i wyjściowych algorytmu. Dane wejściowe to informacja, którą musi otrzymać algorytm w celu rozwiązania problemu. Dane wyjściowe to wyniki pracy algorytmu.
a,b - liczby naturalne, których NWD oblicza algorytm
a lub b - wartość NWD pierwotnych liczb a i b.
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 |
Czytaj - powoduje odczyt danych i przypisanie ich podanym symbolom.
Pisz - powoduje wypisanie informacji
Idź do kroku n - powoduje, że następna operacja zostanie wykonana od kroku
n.
Jeśli
warunek, to operacja1. Inaczej operacja2
- jeśli warunek jest spełniony, to zostaje wykonana operacja1.
Inaczej wykonana zostanie operacja2.
Zakończ - powoduje zakończenie wykonywania algorytmu.
Algorytm opisywany jest w sposób graficzny za pomocą następujących symboli:
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.
Program komputerowy, np. w języku C++, jest również zapisem algorytmu przy pomocy dostępnych w danym języku instrukcji i struktur danych. W przypadku programu specyfikacja danych jest umieszczona wewnątrz jego kodu.
// 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; } |
Podany wyżej algorytm Euklidesa nie jest najlepszy, chociaż oczywiście działa. Rozważmy prosty przypadek:
a = 2000000000
b = 2
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ą:
(liczba większa) (liczba mniejsza) → (liczba mniejsza) (reszta z dzielenia liczby większej przez mniejszą)
Jeśli reszta wynosi zero, to NWD jest równy liczbie mniejszej. Sprawdźmy:
40 36 → 36 reszta z 40:36
równa 4
36 4 → 4
reszta z 36:4 równa 0
4 0 czyli NWD(40,36) = 4
Z powyższych rozważań otrzymujemy następujący algorytm:
Wejście:
a,b - liczby naturalne, których NWD oblicza algorytm
Wyjście:
a - wartość NWD pierwotnych liczb a i b.
Dane pomocnicze:
r - przechowuje wartość reszty z dzielenia a przez b
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:
Sprawdzania, czy dane dwie liczby naturalne są względnie pierwsze. Wynikiem powinno być słowo "TAK", jeśli są względnie pierwsze, lub słowo "NIE", jeśli nie są względnie pierwsze.
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