II PWr

EB

1

Rozwiązywanie problemów z uŜyciem komputera:

1.

Zdefiniowanie i opis problemu

2.

Znalezienie rozwiązania

3.

Napisanie algorytmu

4.

Napisanie programu (zakodowanie algorytmu)

5.

Uruchomienie programu

6.

Testowanie programu

II PWr

EB

2

6.

Testowanie programu

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

wytworzy Ŝądane 

dane wyjściowe

zwane wynikiem 

działania algorytmu.

Algorytm - definicje

ALGORYTM

II PWr

EB

3

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

Dane wej.

Dane wyj.

ALGORYTM

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ść –

nie powinien być zawęŜany do wąskiego problemu  

II PWr

EB

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 układu równań liniowych

II PWr

EB

5

• Przydział pracowników do zadań

• Optymalizacja gospodarki materiałowej

• Zagadnienia transportowe

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

System powiązanych bloków opisujących kolejność czynności.

II PWr

EB

6

System powiązanych bloków opisujących kolejność czynności.

4) program komputerowy

Jest najbardziej ścisłym zapisem algorytmu.

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

Czytaj a, b

P

II PWr

EB

7

a<>0

x= -b/a

Czytaj a, b

Wypisz: Złe dane

K

T

N

Wypisz x

Algorytm - przykłady

2. Algorytm obliczania n!

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

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

n! = (n-1)!*n

silnia=1

P

Czytaj n

II PWr

EB

8

1.     Czytaj n;

2.

silnia =1;

3.

Dla i = 1 do n wykonaj

silnia = silnia*i;

4.     Wyprowadź silnia;

5.

Koniec;

i<=n

i=1

silnia=silnia*i

i = i+1

T

N

K

Wyświetl silnia

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 

Suma=0

i=1

P

N

T

Czytaj dane

II PWr

EB

9

Suma = Suma +a

i 

Drukuj Suma;

Koniec

i<=n

Suma=Suma+a

i

i=i+1

Drukuj: Suma

N

T

K

Algorytm - przykłady

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

Suma = 0;

Czytaj a:

Suma=0

Czytaj a

P

II PWr

EB

10

Dopóki a<>0 Wykonaj

Suma = Suma + a;

Czytaj a;

Drukuj Suma;

a<>0

Suma=Suma+a

Czytaj a

Drukuj Suma

T

N

K

Wprowadź

a,b,c

b= 0

x=-c/b

T

N

T

N

N

T

P

a=0

delta=b

2

-4ac

Złe dane

ax

2  

+ bx +c = 0

II PWr

EB

11

x=-c/b

N

T

K

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

+

−

=

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

II PWr

EB

12

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

−

−

=

Algorytm – schemat blokowy

Konwencje dotyczące schematów blokowych

początek/koniec

operacja we/wy

II PWr

EB

13

blok wykonawczy

blok warunkowy

blok złoŜony

Algorytm – sekwencja czynności

Czynność 1

Czynność 2

II PWr

EB

14

Czynność 3

Algorytm – warunek „jeŜeli”

Warunek

Czynność

T

N

JeŜeli <warunek> To

Czynność

II PWr

EB

15

Warunek

Czynność1

Czynność2

T

N

JeŜeli <warunek> To

Czynność1

W przeciwnym razie

Czynność2

Algorytm – wybór czynności

Czynność2

Czynność1

Przełącznik

Czynność3

Czynność4

Wej

II PWr

EB

16

Wyj

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

Warunek

Czynność

T

N

Dopóki <warunek> Wykonaj

Czynność

II PWr

EB

17

Warunek

Czynność

T

Powtarzaj

Czynność

AŜ  <warunek>

N

Algorytm – iteracje „dla”

i<=n

Czynność

T

N

i=1

Dla i=1 Do n Wykonaj

Czynność

II PWr

EB

18

i=i+1

K  O  N  I  E  C

II PWr

EB

19