algorytmy.pdf

1 / 15

ALGORYTMIKA

2 / 15

ALGORYTMIKA

Wprowadzenie do algorytmów.

START

1. Podstawowe okrelenia.

Algorytmika – dział informatyki, zajmuj cy si ró nymi aspektami tworzenia i analizowania

algorytmów.

we: a,b,c

delta:=b 2 -4ac

Algorytm

delta>0

Program ródłowy

delta

Delta=0

Program wynikowy

Rys. A. Ka dy program działa według okre lonego algorytmu.

delta

x 0

wy: brak pierw.

rzeczywistych

Algorytm – dokładny („krok po kroku”) opis rozwi zania postawionego problemu lub sposobu

osi gni cia jakiego celu.

Specyfikacja problemu (specyfikacja algorytmu) – opisanie problemu przez podanie danych ,

z których korzysta algorytm oraz okre lenie wyniku , który ma by efektem działania algorytmu.

W specyfikacji podajemy równie :

- warunki , jakie powinny spełnia dane i wyniki,

- ewentualne zale no ci mi dzy danymi i wynikami.

2. Metody opisu algorytmów.

wy: x 1 ,x 2

wy: x 0

STOP

Rys. B. Schemat blokowy algorytmu obliczania pierwiastków równania kwadratowego.

Elementy schematu – bloki:

a) Opis słowny

Kolejne kroki algorytmu przedstawiamy za pomoc słów j zyka naturalnego.

b) Pseudo-kod

W opisie kolejnych kroków algorytmu ł czymy j zyk naturalny (opis słowny) ze znanymi nam

elementami składni wybranego j zyka programowania.

Przykład 1.

Algorytm obliczania pierwiastków równania kwadratowego.

Krok 1 : Na podstawie współczynników równania kwadratowego oblicz warto delty:

D :=b*b-4*a*c .

Krok 2 : Je li D >0 to oblicz dwa pierwiastki:

x1:=(-b-pierwiastek( D ))/(2*a) , x2:=(-b+pierwiastek( D ))/(2*a) ;

wypisz ich warto na ekran i zako cz działanie algorytmu.

Krok 3 : W przeciwnym wypadku, je li D =0 to oblicz jeden pierwiastek:

x0:=-b/(2*a) ; wypisz jego warto na ekran i zako cz działanie algorytmu.

Krok 4 : W przeciwnym wypadku, (je li D <0 ) wypisz na ekran komunikat: „brak pierwiastków

rzeczywistych” i zako cz działanie algorytmu.

c) Składnia jzyka programowania

3. Graficzna reprezentacja algorytmów.

a) Schemat blokowy

START STOP

pocz tek i koniec algorytmu

blok wprowadzania i wyprowadzania danych

blok przeprowadzania oblicze

blok podejmowania decyzji

b) Drzewo

a b

Korze

a c

b c

Wierzchołki po rednie

(a) (c) (b) (c)

Wierzchołki ko cowe - li cie

Rys. C. Drzewo algorytmu wyznaczania najwi kszej spo ród trzech liczb.

3 / 15

ALGORYTMIKA

4 / 15

ALGORYTMIKA

5. Podział algorytmów.

Algorytmy iteracyjne.

a) Algorytm liniowy

Algorytm, w którym nie wyst puj bloki decyzyjne.

Iteracja – wielokrotne powtarzanie tej samej czynno ci (operacji).

1. Wielokrotne wykonywanie całego programu.

START

we: r

START

pole:= r 2

obw:=2 r

we: r

wy: pole,obw

pole:= r 2

obw:=2 r

STOP

wy: pole,obw

Rys. D. Algorytm liniowy – brak elementów decyzyjnych.

b) Algorytm nieliniowy (warunkowy)

Algorytm, w którym wyst puje, co najmniej jeden blok decyzyjny, tzw. algorytm z rozgał zieniami

(przykłady na rys. B i rys. C).

Koniec programu?

(T/N)

odp=’T’

wy: ’Cze ’

STOP

Rys. E. Algorytm iteracyjny – powtarzanie całego programu po decyzji u ytkownika.

2. Schemat Hornera - obliczanie wartoci wielomianu.

a) Operacje dodawania i mnoenia w wielomianach.

„+” „*”

w(x) = ax 2 + bx + c

w(x) = ax 3 + bx 2 + cx + d

w(x) = ax 4 + bx 3 + cx 2 + dx + e

Po odpowiednich przekształceniach zapisu wielomianu ilo operacji mno enia zmniejsza si .

„+” „*”

w(x) = ax 2 + bx + c = (ax + b)x + c

w(x) = ax 3 + bx 2 + cx + d = (ax 2 + bx + c)x + d = ((ax +b)x + c)x + d

w(x) = ax 4 + bx 3 + cx 2 + dx + e = (ax 3 + bx 2 + cx +d)x + e = ((ax 2 + bx + c)x + d)x + e =

= (((ax +b)x + c)x + d)x + e

5 / 15

ALGORYTMIKA

6 / 15

ALGORYTMIKA

b) Opracowanie algorytmu obliczania wartoci wielomianu.

Dla wielomianu 3 stopnia:

w 3 (x) = a 0 x 3 + a 1 x 2 + a 2 x + a 3 = (a 0 x 2 + a 1 x + a 2 )x + a 3 = ((a 0 x + a 1 )x + a 2 )x + a 3

wprowadzamy pomocnicz zmienn y i wykonujemy kolejne operacje przypisania ( := ):

Schemat blokowy algorytmu:

START

y := a 0

y := yx + a 1

y := yx + a 2

y := yx + a 3

we: n; a 0 ,...,a n ; x

y := yx + a i

dla i=1..3

i:=1

y:=a 0

Dla wielomianu n-tego stopnia:

w n (x) = a 0 x n + a 1 x n-1 + … + a n-1 x + a n

i>n

y := a 0

y := yx + a 1

y := yx + a 2

...

y := yx + a n-1

y := yx + a n

wy: y

y:=yx+a i

i:=i+1

y := yx + a i

dla i=1..n

STOP

Specyfikacja algorytmu:

Dane:

n – stopie wielomianu (nieujemna liczba całkowita),

a 0 , …, a n – współczynniki wielomianu (ilo współczynników: n-1),

x – warto argumentu.

Wyniki:

Warto wielomianu w(x) n -tego stopnia dla danej warto ci argumentu x .

Rys. F. Schemat blokowy algorytmu obliczania warto ci wielomianu (schemat Hornera).

3. Wyszukiwanie najwikszego (najmniejszego) elementu w zbiorze.

a) Wstpne informacje.

Odszukanie okre lonego elementu w zbiorze wymaga przejrzenia wszystkich jego elementów.

W zwi zku z tym musimy okre li ilo wszystkich elementów, tzw. moc zbioru. Wykonujemy to

zwykle dwoma metodami:

- poprzedzamy elementy zbioru liczb , która okre la ilo wszystkich elementów, lub

- przyjmujemy okre lony element za „wartownika”, który nie nale y do zbioru i wskazuje jego koniec.

Dodatkowo zakładamy te , e zbiór nie mo e by niesko czony oraz e elementy zbioru nie s

uporz dkowane.

Słowny opis algorytmu:

Krok 1: Przyjmij współczynnik a 0 wielomianu (stoj cy przy argumencie x o najwy szej pot dze) za

warto pocz tkow i przypisz do pomocniczej zmiennej y.

/ y:=a 0 /

Krok 2: Oblicz n razy warto wyra enia y:=yx+a i dla i=1, 2, …, n.

b) Algorytm wyszukiwania najwikszego elementu.

Specyfikacja algorytmu:

Dane:

n – liczba naturalna okre laj ca ilo liczb w zbiorze,

x 1 , x 2 , …, x n – ci g liczb zbioru.

Wynik:

max – najwi ksza spo ród liczb: x 1 , x 2 , …, x n .

Słowny opis algorytmu:

Krok 1: Przyjmij pierwszy element zbioru (x 1 ) jako max [ max:=x 1 ].

Krok 2: Dla kolejnych elementów x i (i = 1, 2, …, n) sprawdzaj czy max jest mniejsze od x i [ max<x 1 ]

i je li tak to przyjmij za max – x i [ max:=x 1 ].

7 / 15

ALGORYTMIKA

8 / 15

ALGORYTMIKA

Schemat blokowy algorytmu:

Algorytmy wyszukiwania danych.

START

1. Wyszukiwanie w zbiorze nieuporzdkowanym (liniowe).

Specyfikacja algorytmu:

Dane:

a[i] ( i=1..n ) – nieuporz dkowana n-elementowa, jednowymiarowa tablica ( a ),

x – poszukiwany element w tablicy a .

Wynik:

Poło enie (indeks – i ) elementu x w tablicy a lub informacja o braku elementu.

we: n; x 0 ,...,x n

i:=1

max:=x 1

Schemat blokowy algorytmu:

i>n

START

max<x i

we: a[i],i=1..n; x

max:=x i

i:=1

wy: max

i:=i+1

STOP

i:=i+1

i>n

Rys. G. Schemat blokowy algorytmu wyszukiwania najwi kszego elementu.

c) Złoono algorytmów wyszukiwania najwikszego lub najmniejszego elementu.

Zgodnie z widocznym na rys. F schematem algorytmu odszukanie najwi kszego b d najmniejszego

elementu w zbiorze wymaga wykonania n-1 porówna , gdzie n jest ilo ci wszystkich elementów.

Poniewa nie jest mo liwe wykonanie mniejszej liczby porówna (dla poprawnego działania

algorytmu), dlatego mo emy powiedzie , e powy szy algorytm jest optymalny pod wzgl dem

zło ono ci obliczeniowej . Optymalny, a wi c najszybszy.

a[i]=x

wy: ’brak

elementu’

wy: i

STOP

Ę WICZENIA :

1. Co nale y zmieni w algorytmie umieszczonym na rys. G, aby odszuka element najmniejszy?

2. Uzupełnij schemat algorytmu z rys. G o mo liwo odczytania pozycji, na której znajdował si

poszukiwany element.

3. Narysuj schemat blokowy algorytmu jednoczesnego wyszukiwania elementu najwi kszego

i najmniejszego.

Rys. H. Schemat blokowy algorytmu wyszukiwania „liniowego”.

Ę WICZENIA :

1. Uzupełnij schemat algorytmu z rys. H o mo liwo wypisania wszystkich pozycji, na których

znajdował si poszukiwany element.

2. Wyszukiwanie w zbiorze uporzdkowanym (binarne).

Specyfikacja algorytmu:

Dane:

a[i] ( i=1..n ) – uporz dkowana n-elementowa, jednowymiarowa tablica ( a ),

x – poszukiwany element w tablicy a .

9 / 15

ALGORYTMIKA

10 / 15

ALGORYTMIKA

Wynik:

Poło enie (indeks – i ) elementu x w tablicy a lub informacja o braku elementu.

Pomocnicze zmienne:

l , p – tymczasowy lewy i prawy koniec zakresu,

s – tymczasowy rodek zakresu.

Tworzenie algorytmów – przykłady.

1. Suma i rednia arytmetyczna.

Przykładowy algorytm korzysta z elementu zwanego wartownikiem . Warto tego elementu jest znana

u ytkownikowi. Jej wprowadzenie ko czy działanie algorytmu.

Specyfikacja algorytmu:

Dane:

x – kolejno wprowadzane liczby (wartownikiem jest dowolna całkowita liczba ujemna).

Wynik:

Suma s i rednia arytmetyczna sr wprowadzonych liczb.

Pomocnicze zmienne:

il – ilo wprowadzonych liczb.

Schemat blokowy algorytmu:

START

we: a[i],i=1..n; x

l:=1; p:=n

START

l>p

s:=0; il:=0

s:=(l+p) div 2

we: x

a[s]=x

wy: ’brak

elementu’

x 0

wy: s

a[s]<x

s:=s+x

il:=il+1

sr:=s/il

l:=s+1

p:=s-1

wy: s,sr

STOP

Rys. I. Schemat blokowy algorytmu wyszukiwania „binarnego”.

Rys. J. Schemat blokowy algorytmu obliczania sumy i redniej arytmetycznej liczb.

2. Silnia.

Zapis matematyczny:

dla n = 0

(0! = 1)

n! =

1 2 3 … n dla n 1

Specyfikacja algorytmu:

Dane:

n – liczba naturalna, z której obliczamy silni .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: