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