Algorytmy

Spis treści:



Co to jest algorytm



Schemat blokowy



Instrukcje

sterujące



Tablice jednowymiarowe



Tablice wielowymiarowe

Prowadzący
mgr inż. Agnieszka Godula, pok.715, B5

Co to jest algorytm?
Jak go przedstawić?



Algorytm

– to skończony, uporządkowany ciąg jasno zdefiniowanych

czynności, koniecznych do wykonania pewnego zadania. Algorytm to dokładny
przepis.



Program

to ciąg instrukcji, zapisanych w języku zrozumiałym dla komputera.

Ten ciąg instrukcji realizuje jakiś algorytm.



W jaki sposób można przedstawić algorytm?

Skrzynki START i STOP wskazują
początek i koniec każdego algorytmu. Ze
skrzynki START wychodzi tylko jedna
droga, do skrzynki STOP wchodzi, co
najmniej jedno połączenie.

W skrzynce instrukcyjnej umieszcza się
polecenia do wykonania (instrukcje) -
podstawienie, obliczenie,
wprowadzenie wartości.

Jak przedstawić algorytm? C.d.

W skrzynce warunkowej umieszcza
się warunek, który decyduje o
wyborze dalszej drogi
postępowania. Ze skrzynki
wychodzą dwa połączenia: TAK
(wybierane, gdy warunek jest
spełniony), NIE (gdy warunek nie
jest spełniony).

W skrzynce wejścia/wyjścia
umieszcza się wprowadzane dane
lub wyprowadzane wyniki. Ze
skrzynki wychodzi tylko jedno
połączenie.

Instrukcje sterujące – instrukcja warunkowa



Instrukcje sterujące to specjalne polecenia, dzięki którym można niejako
kierować wykonywaniem programu. Wyróżniamy instrukcje warunkowe i
bezwarunkowe.



Instrukcja if

(instrukcja warunkowa)



Instrukcję

if

(jeśli) stosuje się w sytuacji, gdy wykonanie pewnych czynności jest

od postawionego warunku lub wyrażenia.

if (warunek) instrukcja;

Zapis ten oznacza, że jeśli warunek jest spełniony wykonaj instrukcję. Gdy
warunek nie został spełniony wtedy instrukcja umieszczona za

if

zostanie

pominięta i nastąpi przejście do następnej linii kodu. Jeżeli warunek
zostanie spełniony zostanie wykonana tylko jedna instrukcja znajdująca się
bezpośrednio za

if

. Średnik stanowi zakończenie instrukcji.

if (warunek)
{
instrukcja1;
instrukcja2;
instrukcja3;
instrukcja4;
}

Teraz, jeśli warunek zostanie spełniony
zostaną wykonane wszystkie instrukcje
będące między klamrami. W klamrach
można umieścić dowolną ilość instrukcji.
Można też umieścić tam inne instrukcję
if

, tylko pamiętać należy o zamykaniu

klamer.

Np.
if (zmienna==0) {

instrukcja1;
instrukcja2; }

else if (zmienna==1) {

instrukcja3;
instrukcja4; }

Instrukcje sterujące – pętle (pętla while)



Pętla

to pewien fragment kodu, który jest wykonywany wielokrotnie.



Pętla while



While

oznacza

dopóki, podczas gdy. Pętla

while

jest wykonywana

dopóki postawiony warunek jest spełniony. Taka pętla może zawierać

jedną lub więcej instrukcji. Np.

while (5>3) instrukcja;



Taka pętla raczej nie znajdzie zastosowania w praktyce. Warunek jest

zawsze ten sam, zawsze jest on prawdziwy. Oznacza to, że pętla a tym

samym będąca w pętli instrukcja będzie wykonywana w nieskończoność.

Wówczas należy w pętli użyć zmiennej.Np.

while (zmienna !=0) instrukcja;



Tutaj instrukcja

będzie wykonywana dopóki wartość zmiennej będzie

różna od 0. Jeżeli pętla zawiera kilka instrukcji istnieje możliwość
umieszczenia ich w bloku. Np.

while (zmienna < 100)
{

instrukcja_1;
instrukcja_2;
instrukcja_3;

}

Warunek jest tutaj sprawdzany w momencie
wchodzenia do pętli. Oznacza to, że jeśli na początku
nie zostanie on spełniony to pętla nie wykona się
nawet jeden raz!

Instrukcje sterujące – pętle (pętla do while)



Pętla do while



Zasadnicza różnica między tą pętla a pętlą

while

jest taka, że tutaj

nastąpi przynajmniej jeden obieg. Pierwszy obieg jest niezależny od
warunku, ponieważ jego sprawdzenie nastąpi dopiero na końcu. Np.

do

{

instrukcja_1;

instrukcja_2;

instrukcja_3;

}

while (zmienna < 10);



Pętle

do while

stosowane są najczęściej w sytuacjach, gdy nieznana

jest ilość obiegów.

Instrukcje sterujące – pętle (pętla for)



Pętla for



Pętla

for

jest stosowana w sytuacjach, gdy można określić bliżej ile razy będzie

ona powtarzana. Słowo

for

oznacza dla. Np.

for

(wyrażenie_początek; warunek; instrukcja_co_obieg)

{

instrukcja_1;
instrukcja_2;
instrukcja_3;

}

Przykład
for (int i=0; i<100; i++)
{

instrukcja_1;
instrukcja_2;
instrukcja_3;

}

Instrukcje sterujące – schematy blokowe



C++

If (warunek)

{
…
…
}

STOP

i<n

NIE

TAK

A=b

i<n

STOP

i=i+1

A=b

TAK

NIE



C++

while (warunek)

{
…
…
}

Instrukcje sterujące – schematy blokowe c.d.



C++

For (i=0; i<n; i++)
{
…
…
}



C++

Do {
…
…
while (warunek)

}

i=i+1

A=a

STOP

i<n

TAK

NIE

i<n

i=0

A=b

i=i+1

STOP

i<n

i=0

A=b

i=i+1

STOP

TAK

NIE

Tablice



Tablicą

nazywamy złożoną strukturę danych, która zawiera zbiór

elementów tego samego typu.

Wyróżniamy:



tablice jednowymiarowe



tablice wielowymiarowe

Tablice jednowymiarowe



Tablica

jest to zbiór elementów tego samego typu. Każdy element

tablicy jest identyfikowany przez jego numer (indeks). Każdy element

tablicy posiada swoją wartość. Oto tablica

t

zawierająca

5 elementów

:

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie
nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu ( numer
żądanego elementu).
I tak w naszej tablicy o nazwie t:

t [1] = 5
t [2] =11
t [3] =8
t [4] =3
t [5] =2

Element t [i] dla i

równego 4 wynosi 3, dla i równego 2 wynosi 11.

Tablice jednowymiarowe
Schemat blokowy: wczytywanie elementów tablicy



Ponieważ tablica ma k- elementów, a więc k- razy nastąpi wczytywanie
elementu, stąd zastosowanie iteracji.

Spr. Dla k=5
i=1
1<=5 tak
Podaj 5

T[1]:=5

i=1+1=2
2<=5 tak
Podaj 11

T[2]:=11

i=2+1=3
3<=5 tak
Podaj 8

T[3]:=8

i=3+1=4
4<=5 tak
Podaj 3

T[4]:=3

i=4+1=5

5<=5 tak
Podaj 2

T[5]:=2

i=5+1=6
6<=5 nie
STOP

Tablice jednowymiarowe
Schemat blokowy: wypisujący elementy tablicy



Algorytm wypisujący elementy tablicy k- elementowej.

Tablice jednowymiarowe
Schemat blokowy: liczący średnią arytmetyczną elementów tablicy

Tablice jednowymiarowe
Schemat blokowy: wczytuje elementy i drukuje w odwrotnej kolejności

Wczytaj elementy do tablicy k-

elementowej, a następnie wydrukuj je w

odwrotnej kolejności.

Tablice wielowymiarowe

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy
tablicy oraz w nawiasach kwadratowych wartość indeksu ( numer żądanego
elementu). I tak w naszej tablicy o nazwie

t

zapis

t[3,4]

oznacza element w

trzecim

wierszu

i

czwartej kolumnie

, czyli element o wartości =3.

t [1,1] = 2
t [1,2] =6
t [1,3] =11
t [1,4] =0
t [2,1] =7

Element t [i, j] dla i

równego 2 i j równego 2 wynosi 5.

Tablice wielowymiarowe

Schemat blokowy: wypełniający tablicę kwadratową k x k

Tablice wielowymiarowe

Schemat blokowy: Szukający w tablicy m x n element maksymalny. Wypisujący

jego położenie i wartość.