Materiały do matury z informatyki

Z algorytmów będziemy korzystali przy programowaniu, dlatego należy je bezwzględnie znać - nie musisz się ich uczyć na pamięć, wystarczy, że zrozumiesz ich sposób działania i będziesz wiedział, gdzie je znaleźć. Dobrym pomysłem jest założenie sobie pliku w Notatniku lub innym edytorze tekstu i zapisywanie w tym pliku poznanych algorytmów wraz z opisami.

Omówmy teraz krótko podstawowe elementy podanej definicji:

• "uporządkowany ciąg operacji" oznacza, iż operacje muszą być wykonywane w pewnym porządku, szczególnie wtedy, gdy następna operacja korzysta z wyniku operacji poprzedniej (istnieją też algorytmy równoległe, w których pewne operacje mogą być wykonywane równocześnie lub w dowolnej kolejności - takie algorytmy realizuje się  na komputerach wieloprocesorowych, my jednakże przyjmijmy sobie, że operacje będą występowały w algorytmie w zadanej kolejności, aby nie mieszać ci w głowie). Ponieważ ciąg ten musi być skończony, to należy wskazać operację pierwszą oraz ostatnią, która kończy wykonanie algorytmu. Operacja pierwsza może być tylko jedna (bo inaczej mamy problem, od której zacząć, a na domyślność komputera bym raczej tutaj nie liczył), natomiast operacji ostatnich może być wiele.
• "skończony ciąg operacji" oznacza, że wykonywane operacje muszą się kiedyś zakończyć, nie może być ich nieskończenie wiele, bo wtedy algorytm byłby wykonywany w nieskończoność, czyli nigdy nie otrzymalibyśmy wyniku, to co nam z takiego algorytmu?
• "jednoznacznie określony" oznacza, że każda operacja algorytmu jest znana i wiadomo, jak ją wykonać. Inaczej mamy algorytm łowienia tygrysa gołymi rękami: 1) podejdź do tygrysa od tyłu, 2) złap tygrysa za ogon, 3) przyciągnij tygrysa za ogon do siebie, 4) dawaj tygrysowi pięścią po łbie, aż padnie nieprzytomny, 5) zarzuć sobie nieprzytomnego tygrysa na plecy, 6) zanieś nieprzytomnego tygrysa do obozu. Proste? To do dzieła... powodzenia w łowieniu tygrysów.
• "zestaw danych" to informacja, którą potrzebuje algorytm przed rozpoczęciem wykonywania operacji. W każdym algorytmie należy określić dane wejściowe oraz dane wyjściowe, czyli to, co otrzymamy po zakończeniu pracy algorytmu. Nazywamy to specyfikacją wejścia/wyjścia (ang. Input/Output specification).
• "pewna klasa problemów" oznacza, iż algorytm musi być w miarę ogólny, nie jednostkowy. Na przykład znajdowanie wyniku 2 + 4.  Wynik oczywiście 6. Nie jest to dobry algorytm, natomiast algorytmem będzie znajdowanie wyniku sumowania dowolnych dwóch liczb, to już jest algorytm ogólny, uczyłeś tego w szkole podstawowej.

Opis słowny

Dawniej zapisywano algorytmy słownie i sposób ten obowiązuje do dzisiaj. Jednakże opis taki, musi spełniać podaną w poprzednim podrozdziale definicję, aby można było go zaliczyć do algorytmów.

Największy wspólny dzielnik dwóch liczb (NWD - ang. GCD Greatest Common Divider) to największa liczba naturalna, która dzieli bez reszty dwie dane liczby naturalne. Na przykład:

NWD(24,18) = 6, ponieważ 24 : 6 = 4 (dzieli się) i 18 : 6 = 3 (dzieli się).

Dzielenie bez reszty jest dzieleniem całkowitoliczbowym. Na przykład 9 : 2 = 4 (tyle całkowitą razy liczba 2 mieści się w liczbie 9) i reszta 1. Jeśli reszta wynosi 0, to liczba pierwsza jest podzielna przez drugą. Na przykład 12 : 4 = 3 i reszta 0, czyli liczba 12 jest podzielna przez liczbę 4. Jeśli reszta jest różna od 0, to liczby nie dzielą się, na przykład 12 : 5 = 2 i reszta 2, 12 nie jest podzielne przez 5.

NWD możemy znaleźć tak:

Wejście: a,b - liczby naturalne
Wyjście: a - wartość NWD liczb a i b

Od większej z liczb a, b odejmuj mniejszą dotąd, aż obie liczby a, b staną się równe.

Wtedy wynikiem NWD jest a (lub b, bo obie liczby a i b są równe).

Sprawdź, czy algorytm ten spełnia definicję:

• Porządek
• Skończoność
• Jednoznaczność i określoność
• Specyfikacja wejścia/wyjścia
• Ogólność

Testujemy:

a = 24, b = 18
a = 24 - 18 = 6
a = 6, b = 18, liczby nie są równe (b jest teraz większe), powtarzamy:

b = 18 - 6 = 12
a = 6, b = 12, liczby wciąż nie są równe (b jest większe), powtarzamy:

b = 12 - 6 = 6
a = 6, b = 6, liczby są równe, kończymy NWD = a = 6.

Schemat blokowy

	Symbol startowy, od którego rozpoczyna się wykonanie algorytmu
	Symbol końca algorytmu
	Strzałka określa kierunek wykonania, czyli kolejność operacji. Prowadzi do następnego symbolu w algorytmie.
	Symbol przetwarzania danych.
	Symbol 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. Nasz algorytm wyliczania NWD będzie wyglądał tak:

Wejście: a,b - liczby naturalne
Wyjście: a - wartość NWD liczb a i b

Czytaj w bloku wprowadzania oznacza odczyt wartości podanych obiektów, tutaj liczb a i b, których NWD algorytm ma policzyć.

Pisz w bloku wyprowadzania danych oznacza podanie wyniku do wiadomości użytkownika.

Strzałka ← w bloku przetwarzania danych oznacza, iż wynik wyrażenia po prawej stronie zostaje umieszczony w obiekcie po lewej stronie lewej. W ten sposób w algorytmie zmieniamy wartości a i b, czyli przetwarzamy dane.

Sprawdź, czy algorytm ten spełnia definicję:

• Porządek
• Skończoność
• Jednoznaczność i określoność
• Specyfikacja wejścia/wyjścia
• Ogólność

Lista kroków

Algorytm NWD opisany listą kroków wygląda następująco:

Wejście: a,b - liczby naturalne
Wyjście: a - wartość NWD liczb a i b

Użyte operacje:

Pseudokod

Pseudokod (ang. pseudocode) jest sposobem zapisu algorytmu przypominającym program komputerowy w wybranym języku programowania, jednak takim programem nie jest. W pseudokodzie programiści najczęściej zapisują ideę działania algorytmu, aby później zrealizować ten algorytm w programie. Zasady tworzenia pseudokodów są różne, nie ma tutaj jednolitej reguły. Ważna jest konsekwencja. Poniżej przykład naszego algorytmu w pseudokodzie:

Wejście: a,b - liczby naturalne
Wyjście: a - wartość NWD liczb a i b

wczytaj a, b
dopóki a ≠ b wykonuj
    jeśli a > b to
        a ← a - b
    w przeciwnym razie
        b ← b - a
wypisz a

Odstępy oznaczają operacje należące do tego samego bloku. Więcej na temat pseudokodu powiemy przy nauce programowania

Program komputerowy

Algorytmy są tak ważne, ponieważ pozwalają nam tworzyć programy. Nauka programowania polega właśnie na tworzeniu algorytmów w postaci programu komputerowego. Dlaczego zatem nie pisze się od razu algorytmu jako programu komputerowego? Chodzi o to, iż istnieje całe mnóstwo języków programowania, w których programy zapisuje się wg innych reguł. Jeśli chcemy mieć algorytm ogólny, który można przekształcić na program w dowolnym języku programowania, to musimy ten algorytm zapisać ogólnie - do tego celu służą właśnie poprzednio opisane sposoby.

Poniżej nasz algorytm w kilku językach programowania

Język C++

// Obliczanie NWD
//---------------

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

Język C (poprzednik C++)

/* Obliczanie NWD
 ----------------*/

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,b;

    scanf("%d %d",&a,&b);
    while(a !=b)
      if(a > b) a -= b;
      else      b -= a;
    printf("%d\n",a);

    return 0;
}

Język Pascal (bardzo dobry, lecz wychodzi niestety z użycia)

{
  Obliczanie NWD
  --------------
}
program NWD;

var
   a,b : integer;

begin
  readln(a,b);
  while a <> b do
    if a > b then dec(a,b)
    else          dec(b,a);
  writeln(a);
  readln;
end.

Język Free Basic

' Obliczanie NWD
' --------------

DIM a as INTEGER
DIM b as INTEGER

INPUT a,b

WHILE a <> b
  IF a > b THEN
    a = a - b
  ELSE
    b = b - a
  ENDIF
WEND

PRINT a

SLEEP

END

Język Python

# Obliczanie NWD
# --------------

a = int(input())
b = int(input())

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
print(a)

Programowaniem w języku C++ zajmiemy się od następnej lekcji. Językiem Python tutaj się nie zajmujemy, jeśli chcesz zdawać ten język na maturze, to zaopatrz się w podręcznik dla kursu rozszerzonego. Do zapisu algorytmów będziemy używać listy kroków i pseudokodu, ponieważ z nimi możesz spotkać się w zadaniach maturalnych. Jednakże próbuj samodzielnie zapisywać algorytmy również przy pomocy schematów blokowych, które znakomicie rozwijają myślenie algorytmiczne.