PWrIIS

Edward Bieleninik

1

PWrIIS

Edward Bieleninik

2

Algorytm – sko czony system reguł okre laj cych kolejno

działa

wykonywanych na okre lonych obiektach (danych) w celu uzyskania rozwi zania
problemu.

Algorytm – ci le okre lona procedura obliczeniowa, która dla wła ciwych

danych wej ciowych

wyprodukuje dane

dane wyj ciowe

zwane wynikiem

działania algorytmu.

Algorytm - definicje

Pochodzenie wyrazu: od nazwiska matematyka perskiego „Al-Khowarizmi” z IX w.
Na łacin zostało przetłumaczone jako Algorismus.

Dane wej.

Dane wyj.

ALGORYTM

PWrIIS

Edward Bieleninik

3

Własno ci algorytmów:

1)

poprawno

– algorytm musi by poprawny

2)

sko czono

– algorytm musi umo liwi rozwi zanie problemu w

sko czonym czasie

3)

zło ono

– mierzy si czasem wykonania i zaj to ci pami ci odniesionych

do wielko ci danych

4)

uniwersalno

PWrIIS

Edward Bieleninik

4

Przykłady problemów algorytmicznych

• Zbadanie czy dana liczba naturalna jest pierwsza

• Znalezienie najwi kszego wspólnego dzielnika dwóch liczb

• Rozkład liczby na czynniki pierwsze

• Uporz dkowanie (posortowanie) ci gu liczb od najmniejszej do najwi kszej

• Rozwi zanie równania kwadratowego

• Rozwi zanie układu równa liniowych

PWrIIS

Edward Bieleninik

5

A

D

E

B

G

H

C

F

Problemy grafowe

• problem komiwoja era

Znale najkrótsz drog umo liwiaj c jednokrotne odwiedzenie wszystkich w złów.

• problem minimalnego pokrycia

Znale najkrótsze poł czenie wszystkich w złów

PWrIIS

Edward Bieleninik

6

A

D

E

B

G

H

C

F

Problem komiwoja era

(przykładowe rozwi zanie)

PWrIIS

Edward Bieleninik

7

A

D

E

B

G

H

C

F

Problem minimalnego pokrycia

(przykładowe rozwi zanie)

PWrIIS

Edward Bieleninik

8

Algorytm – sposoby zapisu

1) opis słowny

Musi by zrozumiały i jednoznaczny.

2) opis w postaci listy kroków

Poszczególne kroki zawieraj opis operacji, które maj by wykonane przez

algorytm. Mog równie wyst pi polecenia zmiany kolejno ci wykonywania

kroków.

3) schemat blokowy

4) program komputerowy

Jest najbardziej cisłym zapisem algorytmu.

PWrIIS

Edward Bieleninik

9

Algorytm - przykłady

Algorytm Euklidesa – znajdowanie najwi kszego wspólnego podzielnika 2 liczb.

Dane s dwie liczby naturalne a, b (a > b).

NWD(a,b):

1.

Je eli b = 0

2.

to Wynik = a

3.

w przeciwnym razie Wynik = NWD(b, a mod b)

NWD(30,21) =
NWD(21, 30 mod 21) = NWD(21,9) =
NWD(9, 21 mod 9) = NWD(9, 3) =
NWD(3, 9 mod 3) = NWD(3, 0) =
3

PWrIIS

Edward Bieleninik

10

Algorytm - przykłady

1.

Wprowad warto ci a, b;

2.

Je eli a<>0 to x=-b/a; Wyprowad x;

W przeciwnym razie Wyprowad „Złe dane”;

3.

Koniec;

1. Algorytm rozwi zania równania liniowego ax + b = 0

a<>0

x= -b/a

Czytaj a, b

Wypisz: Złe dane

K

P

T

N

Wypisz x

PWrIIS

Edward Bieleninik

11

Algorytm - przykłady

2. Algorytm obliczania n!

1. Czytaj n;

2.

silnia =1;

3.

Dla i = 2 do n wykonaj

silnia = silnia*i;

4. Wyprowad silnia;

5.

Koniec;

n! = 1*2*3* ... *n

3! = 1*2*3 = 6 4! = 1*2*3*4 = 3!*4 =
24

n! = (n-1)!*n

silnia=1

i<=n

i=2

silnia=silnia*i

i = i+1

P

T

N

Czytaj n

K

Wy wietl silnia

PWrIIS

Edward Bieleninik

12

Algorytm - przykłady

Obliczy sum ci gu n liczb:

a

1

, a

2

, a

3

, ..., a

n

Czytaj dane

Suma = 0;

Dla i = 1 Do n Wykonaj

Suma = Suma +a

i

Drukuj Suma;

Koniec

Suma=0

i<=n

i=1

Suma=Suma+a

i

P

i=i+1

Drukuj:

Suma, Iloczyn

N

T

Czytaj dane

K

PWrIIS

Edward Bieleninik

13

Algorytm - przykłady

Obliczy sum liczb czytanych z klawiatury.
Czytanie ko czy liczba 0.

Suma = 0;

Czytaj a:

Dopóki a<>0 Wykonaj

Suma = Suma + a;

Czytaj a;

Drukuj Suma;

Suma=0

Czytaj a

a<>0

Suma=Suma+a

Czytaj a

Drukuj Suma

T

N

K

P

PWrIIS

Edward Bieleninik

14

Wprowad

a,b,c

b= 0

x=-c/b

T

N

T

N

N

T

P

K

a=0

delta=b

2

-4ac

Złe dane

Wyprowad x

Wyprowad

x

1

, x

2

a

delta

b

x

2

1

−

−

=

delta>=0

Brak

pierwiastków

a

delta

b

x

2

2

+

−

=

ax

2

+ bx +c = 0

Równanie kwadratowe

PWrIIS

Edward Bieleninik

15

Algorytm – rozwi zanie równania kwadratowego

ax

2

+ bx +c = 0

1.

Czytaj a, b, c

2.

Je eli a = 0 to

Je eli b = 0 to Wyprowad „Złe dane”

W przeciwnym razie x = -c/b; Wyprowad x

W przeciwnym razie

delta = b

2

– 4ac

Je eli delta >= 0 to

Wyprowad

x

1

, x

2

W przeciwnym razie Wyprowad „Brak pierwiastków”

3. Koniec

a

delta

b

x

2

2

+

−

=

a

delta

b

x

2

1

−

−

=

PWrIIS

Edward Bieleninik

16

Algorytm – schemat blokowy

Konwencje dotycz ce schematów blokowych

pocz tek/koniec

operacja we/wy

blok wykonawczy

blok warunkowy

blok zło ony

PWrIIS

Edward Bieleninik

17

Algorytm – sekwencja czynno ci

Czynno 1

Czynno 2

Czynno 3

PWrIIS

Edward Bieleninik

18

Algorytm – warunek „je eli”

Warunek

Czynno 1

Czynno 2

T

N

Warunek

Czynno

T

N

Je eli <warunek> To

Czynno

Je eli <warunek> To

Czynno 1

W przeciwnym razie

Czynno 2

PWrIIS

Edward Bieleninik

19

Algorytm – wybór czynno ci

Czynno 2

Czynno 1

Przeł cznik

Czynno 3

Czynno 4

Wej

Wyj

PWrIIS

Edward Bieleninik

20

Algorytm – iteracje „dopóki” i „powtarzaj”

Warunek

Czynno

T

N

Warunek

Czynno

T

Dopóki <warunek> Wykonaj

Czynno

Powtarzaj

Czynno

A <warunek>

N

PWrIIS

Edward Bieleninik

21

Algorytm – iteracje „dla”

i<=n

Czynno

T

N

i=1

i=i+1

Dla i=1 Do n Wykonaj

Czynno