Algorytmy – wprowadzenie

Zajęcia 1

Algorytm

Algorytm

– w matematyce oraz informatyce to skończony, uporządkowany

ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego
rodzaju zadań.
Słowo "algorytm" pochodzi od starego angielskiego słowa algorism,
oznaczającego wykonywanie działań przy pomocy liczb arabskich (w
odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od
nazwiska Muhammed ibn Musa Alchwarizmi - matematyka perskiego z IX
wieku. Algorytm ma przeprowadzić system z pewnego stanu początkowego do
pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika.

Słowo „algorytm” wywodzi się od arabskiego przydomka al-chorezmi
noszonego przez matematyka, który nazywał się Muhammad ibn Musa
Alchwarizmi al-Chorezmi i który żył i pracował w IX w. w Bagdadzie. Słowo
algorytm jest zniekształconym brzmieniem jego nazwiska.

Za pierwszą programistkę komputerów uważa się Adę Lovelace, córkę
słynnego poety George’a Byrona. Ada Augusta Lovelace współpeacowała z
Charlesem Babbage’em w pierwszej połowie XIX w. przy projektowaniu
pierwszej programowalnej maszyny liczącej (maszyny tej jednak nie
skonstruowano). Tworzone przez Adę opisy rozwiązywania konkretnych zadań
obliczeniowych uznaje się za pierwsze programy. Ponad wiek później, w latach
1975-1981, jej imieniem nazwano jeden z języków programowania wysokiego
poziomu – Ada.

Problem i jego rozwiązanie

Najpierw pojawia się

problem

, następnie poszukujemy

algorytmu

rozwiązującego dany problem i na koniec piszemy

program

wykorzystując

jeden z istniejących języków programowania.

Algorytm

Program

Problem

Zależność między programem a algorytmem można
przedstawić też tak:

Program

komputerowy

Algorytm

Komputer

wykonuje

wykonuje

Dane i Szukane

Zawsze przy rozwiązywaniu problemu zastanawiamy się jakie są

dane

(D) i

szukane

(SZ) w danym problemie.

Przykład 1

Obliczyć wartość bezwzględną danej liczby a.
Dane: Liczba rzeczywista a:

D={a}

.

Szukane: Wartość bezwzględna z liczby a:

SZ=|a|

.

Przykład 2

Znajdź największą liczbę wśród liczb: a,b,c.
Dane: Liczby rzeczywiste a,b,c:

D={a,b,c}

Szukane: Największa z liczb a,b,c:

SZ=max(a,b,c)

.

Przykład 3

Sprawdź, czy dana liczba naturalna n jest parzysta.
Dane: Liczba naturalna n:

D={n}

Szukane: „TAK” jeśli liczba n jest parzysta, NIE” jeśli liczba n jest nieparzysta:

SZ=„TAK” lub SZ=„NIE”

Schemat Krokowy Algorytmu

Kroki Algorytmu:

• Zacznij algorytm

• Wprowadź dane

• Rozwiąż problem

• Wyprowadź szukane

• Zakończ algorytm

Schemat krokowy dla problemu z Przykładu 1

• Zacznij algorytm

• Wprowadź wartość liczby a

• Jeśli a>=0, to zmiennej SZ przypisz wartość a: SZ=a, w przeciwnym

wypadku zmiennej SZ przypisz wartość –a: SZ=-a

• Wyprowadź wynik: SZ

• Zakończ algorytm

Zadanie

Napisz schematy krokowe dla problemów z Przykładu 2 i Przykładu 3.

Schemat Blokowy Algorytmu

Zadanie

Narysuj schematy blokowe dla problemów z Przykładu 2 i Przykładu 3.

Start

Koniec

Wczytaj a

a>=0

Wypisz: SZ=-a

Wypisz: SZ=a

tak

nie

Schemat blokowy dla problemu z Przykładu 1:

Realizacja Algorytmu w języku programowania

Program w C++ realizujący problem z Przykładu 1:

#include <iostream>

using namespace std;

main()
{
double a,SZ;
cout << „Podaj a" << endl;
cin >> a;
if (a>= 0)
SZ:=a;
else
SZ:=-a;
cout << ’’Wartość bezwględna z liczby ’’ << a << ’’ wynosi ’’ << SZ << endl;
system("pause");
}

Algorytm Euklidesa

Algorytm Euklidesa

, to algorytm znajdowania największego wspólnego dzielnika

(NWD) dwóch liczb naturalnych. Nie wymaga rozkładania liczb na czynniki
pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie
zawarł go w swoim dziele Elementy.

Schemat jego działania jest następujący:

Przykład:

Zadanie

Znajdź NWD(450,882).

Algorytm Euklidesa

Algorytm Euklidesa

, to algorytm znajdowania największego wspólnego dzielnika

(NWD) dwóch liczb naturalnych. Nie wymaga rozkładania liczb na czynniki
pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie
zawarł go w swoim dziele Elementy.

Schemat jego działania jest następujący:

Przykład:

Zadanie

Znajdź NWD(450,882).

Algorytm Luhna

Algorytm Luhna

– jeden z najczęściej wykorzystywanych algorytmów służących do

sprawdzania poprawności wpisania danej liczby. Jest on używany m.in. do walidacji
numerów kart kredytowych, ciągów liczbowych, itd. Nazwa algorytmu pochodzi od
nazwiska niemieckiego naukowca Hansa Petera Luhna (1896–1964). Na końcu liczby
doklejana jest cyfra kontrolna określająca, czy poprzedzający ją ciąg cyfr jest wpisany
poprawnie.

Schemat jego działania jest następujący:

1. Dla każdej pozycji cyfry określone zostają wagi (mnożniki). Najczęściej jest to 2 dla
pozycji nieparzystych, 1 dla parzystych.
2. Każdą cyfrę liczby mnożymy przez odpowiadającą jej wagę.
3. Jeśli w wyniku mnożenia otrzymamy liczbę dwucyfrową, dodajemy cyfry do siebie
otrzymując liczbę jednocyfrową.
4. Dodajemy wszystkie otrzymane liczby do siebie.
5. Wykonujemy operację mod 10 na otrzymanej sumie (pozostawiamy jedynie cyfrę
jedności).
6. Następnie, jeśli otrzymana cyfra nie równa się 0, odejmujemy ją od 10. Otrzymujemy
cyfrę kontrolną, która jest "doklejana" do liczby.

Przykład:

Mamy liczbę 92480.
Wykonujemy mnożenie przez odpowiednie wagi:

9•2 = 18
2•1 = 2
4•2 = 8
8•1 = 8
0•2 = 0

Cyfry liczby 18 (jako dwucyfrowej) dodajemy do siebie, otrzymując 9.
Otrzymane liczby dodajemy do siebie: 9 + 2 + 8 + 8 + 0 = 27.
Wykonujemy operację mod 10: 27 mod 10 = 7.
7<>0, więc wykonujemy operację 10 – 7 = 3.
Cyfrę kontrolną 3 "doklejamy" do liczby, otrzymując 924803.

Praca domowa:

1. Na czy polega algorytm Fermata.
2. Zapoznaj się z dwoma dowolnymi algorytmami sortowania.