obrazek

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.

Uporządkowanie operacji - działania wykonywane w algorytmie muszą posiadać określoną kolejność. Powinna być wskazana pierwsza operacja. Po wykonaniu każdej operacji musimy wiedzieć, którą z operacji wykonać jako następną. W algorytmie musi istnieć operacja ostatnia.
Skończona liczba operacji - od algorytmu żądamy praktyczności. Zatem ilość zawartych w nim operacji nie może być nieskończona, ponieważ wtedy wykonanie algorytmu nigdy by się nie zakończyło, nie mówiąc juz o problemach z jego opisaniem.
Określoność operacji - musimy wiedzieć jak wykonać każdą operację algorytmu. Co więcej, każda operacja nie może być różnie interpretowana - musi być jednoznaczna, czyli taka, aby można było ją wykonać tylko w jeden sposób.
Skończoność czasu wykonania - od algorytmu żądamy, aby dawał wynik w skończonym czasie. W przeciwnym razie nigdy byśmy nie otrzymali wyniku, co jest przecież równoznaczne z brakiem rozwiązania.
Ogólność - algorytm powinien dawać rozwiązanie wielu podobnych problemów. Złym algorytmem jest obliczanie sumy 2+2=4. Dobrym algorytmem jest natomiast sposób obliczania sumy dowolnych liczb.

Sposoby przedstawiania algorytmu

Opis słowny

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:

obrazek

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

Lista kroków

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.

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

Wejście:

a,b - liczby naturalne, których NWD oblicza algorytm

Wyjście:

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

Użyte operacje:

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 operacja₁. Inaczej operacja₂ - jeśli warunek jest spełniony, to zostaje wykonana operacja₁. Inaczej wykonana zostanie operacja₂.
Zakończ - powoduje zakończenie wykonywania algorytmu.

Schemat blokowy

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.

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

Wejście:

a,b - liczby naturalne, których NWD oblicza algorytm

Wyjście:

a lub b - wartość NWD pierwotnych liczb a i b.

Program komputerowy

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;
}

Algorytm Euklidesa

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:

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

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;
}

Ćwiczenia w programowaniu

Na podstawie algorytmu Euklidesa zaprojektuj algorytmy i napisz wg nich odpowiednie programy:

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.

Informatyka dla klas II

Algorytmy

Sposoby przedstawiania algorytmu

Opis słowny

Lista kroków

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

Wejście:

Wyjście:

Użyte operacje:

Schemat blokowy

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

Wejście:

Wyjście:

Program komputerowy

Algorytm Euklidesa

Algorytm Euklidesa wyznaczania NWD dwóch liczb a i b

Ćwiczenia w programowaniu