Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek
Zmodyfikowano 26.10.2022

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

Materiały do matury z informatyki

Algorytm

SPIS TREŚCI

Definicja algorytmu

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.

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.

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. (ta definicja jest do nauki na pamięć, nie jest długa!).

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

Na początek:  podrozdziału   strony 

Zapis algorytmu

Algorytmy możemy zapisywać na wiele różnych sposobów.

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ę:

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

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, 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ę:

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ć specyfikację danych.

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

Krok 1: Czytaj a,b ; odczytujemy dane wejściowe
Krok 2: Jeśli a  = b, to idź do kroku 5 ; jeśli a = b, to NWD jest równe a
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 obiektom.
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.

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.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.