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

1

II PWr

EB

2

Algorytm - definicje

Własno ci algorytmów:

Algorytm – sko czony system reguł okre laj cych kolejno działa

1)

poprawno

– algorytm musi by poprawny

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

2)

sko czono

– algorytm musi umo liwi rozwi zanie problemu w sko czonym czasie

Algorytm – ci le okre lona procedura obliczeniowa, która dla wła ciwych danych wej ciowych wytworzy dane dane wyj ciowe zwane wynikiem 3)

zło ono

– mierzy si

czasem wykonania i zaj to ci pami ci odniesionych działania algorytmu.

do wielko ci danych

4)

uniwersalno

Dane wej.

ALGORYTM

Dane wyj.

Pochodzenie wyrazu: od nazwiska matematyka arabskiego „Al-Khowarizmi”

z IX w. Na łacin zostało przetłumaczone jako Algorismus.

II PWr

EB

3

II PWr

EB

4

Przykłady problemów algorytmicznych Algorytm – sposoby zapisu

1) opis słowny

• Zbadanie czy dana liczba naturalna jest pierwsza Musi by zrozumiały i jednoznaczny.

• Znalezienie najwi kszego wspólnego dzielnika dwóch liczb 2) opis w postaci listy kroków

• Rozkład liczby na czynniki pierwsze Poszczególne kroki zawieraj opis operacji, które maj by wykonane przez algorytm. Mog równie wyst pi polecenia zmiany kolejno ci wykonywania

• Uporz dkowanie (posortowanie) ci gu liczb od najmniejszej do najwi kszej kroków.

• Rozwi zanie równania kwadratowego 3) schemat blokowy

• Rozwi zanie układu równa liniowych 4) program komputerowy

Jest najbardziej cisłym zapisem algorytmu.

II PWr

EB

5

II PWr

EB

6

Algorytm - przykłady

Algorytm - przykłady

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

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

1.

Wprowad warto ci a, b;

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

2.

Je eli a<>0 to x=-b/a; Wyprowad x; NWD(a,b):

W przeciwnym razie Wyprowad „Złe dane”; 1.

Je eli b = 0

3.

Koniec;

P

2.

to Wynik = a

Czytaj a, b

3.

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

T

NWD(30,21) =

a<>0

x= -b/a

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

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

Wypisz: Złe dane

Wypisz x

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

K

II PWr

EB

7

II PWr

EB

8

Algorytm - przykłady Algorytm - przykłady

P

2. Algorytm obliczania n!

Obliczy sum ci gu n liczb:

a , a , a , ..., a

1

2

3

n

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

Czytaj dane

P

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

Czytaj dane

24

Suma=0

Czytaj n

Suma = 0;

n! = (n-1)!*n

Dla i = 1 Do n Wykonaj i=1

silnia=1

Suma = Suma +ai

N

T

1. Czytaj n;

Drukuj Suma;

i<=n

i=2

2.

silnia =1;

Koniec

N

T

3.

Dla i = 2 do n wykonaj i<=n

Suma=Suma+a

Drukuj: Suma

i

silnia = silnia*i;

Wy wietl silnia

silnia=silnia*i

i=i+1

4. Wyprowad silnia;

K

5.

Koniec;

i = i+1

K

II PWr

EB

9

II PWr

EB

10

Algorytm - przykłady

P

ax2 + bx +c = 0

Obliczy sum

liczb czytanych z klawiatury.

P

Wprowad

Czytanie ko czy liczba 0.

a,b,c

Suma=0

N

T

a=0

Suma = 0;

Czytaj a

N

T

delta=b2-4ac

b= 0

Czytaj a:

x=-c/b

Złe dane

Dopóki a<>0 Wykonaj N

T

N

delta>=0

a<>0

T

− b − delta

Suma = Suma + a;

Brak

x =

Wyprowad x

1

2 a

pierwiastków

Czytaj a;

Drukuj Suma

− b + delta

Suma=Suma+a

x =

2

Drukuj Suma;

2 a

Wyprowad

Czytaj a

x , x

1

2

K

K

II PWr

EB

11

II PWr

EB

12

Algorytm – rozwi zanie równania kwadratowego Algorytm – schemat blokowy

ax2 + bx +c = 0

Konwencje dotycz ce schematów blokowych 1.

Czytaj a, b, c

2.

Je eli a = 0 to

pocz tek/koniec

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

W przeciwnym razie x = -c/b; Wyprowad x operacja we/wy

W przeciwnym razie

delta = b2 – 4ac

blok wykonawczy

Je eli delta >= 0 to

− b + delta

− b − delta

x =

2

x =

1

2 a

2 a

blok warunkowy

Wyprowad

x , x

1

2

W przeciwnym razie Wyprowad „Brak pierwiastków”

blok zło ony

3. Koniec

II PWr

EB

13

II PWr

EB

14

Algorytm – sekwencja czynno ci

Algorytm – warunek „je eli”

N

T

Warunek

Je eli <warunek> To Czynno

Czynno

1

Czynno

Czynno

2

N

T

Je eli <warunek> To Warunek

Czynno 1

Czynno

3

W przeciwnym razie

Czynno 2

Czynno 1

Czynno 2

II PWr

EB

15

II PWr

EB

16

Algorytm – wybór czynno ci Algorytm – iteracje „dopóki” i „powtarzaj”

Wej

N

T

Dopóki <warunek> Wykonaj Warunek

Czynno

Przeł cznik

Czynno

Czynno 1

Czynno 2

Czynno 3

Czynno 4

Powtarzaj

Czynno

Czynno

A

<warunek>

N

T

Wyj

Warunek

II PWr

EB

17

II PWr

EB

18

Algorytm – iteracje „dla”

i=1

Dla i=1 Do n Wykonaj Czynno

N

T

i<=n

K O N I E C

Czynno

i=i+1

II PWr

EB

19

II PWr

EB

20