Algorytmy

Cz¦±¢ II

wer. 1.5

Wojciech Myszka

16 listopada 2008

Zapis algorytmu

1.

Sªowami. Nale»y u»ywa¢ prostych zda« (raczej
równowa»ników zda«) w trybie rozkazuj¡cym.

2.

Schematy blokowe. O tym za chwil¦. . .

3.

Tablice decyzyjne. O tym pó¹niej. . .

4.

Pseudoj¦zyk

rodzaj formalnego zapisu podobny

do. . .

5.

J¦zyk programowania. Nast¦pny semestr??? Wcale!!?

Zapis algorytmu

1.

Sªowami. Nale»y u»ywa¢ prostych zda« (raczej
równowa»ników zda«) w trybie rozkazuj¡cym.

2.

Schematy blokowe. O tym za chwil¦. . .

3.

Tablice decyzyjne. O tym pó¹niej. . .

4.

Pseudoj¦zyk

rodzaj formalnego zapisu podobny

do. . .

5.

J¦zyk programowania. Nast¦pny semestr??? Wcale!!?

Zapis algorytmu

1.

Sªowami. Nale»y u»ywa¢ prostych zda« (raczej
równowa»ników zda«) w trybie rozkazuj¡cym.

2.

Schematy blokowe. O tym za chwil¦. . .

3.

Tablice decyzyjne. O tym pó¹niej. . .

4.

Pseudoj¦zyk

rodzaj formalnego zapisu podobny

do. . .

5.

J¦zyk programowania. Nast¦pny semestr??? Wcale!!?

Zapis algorytmu

1.

Sªowami. Nale»y u»ywa¢ prostych zda« (raczej
równowa»ników zda«) w trybie rozkazuj¡cym.

2.

Schematy blokowe. O tym za chwil¦. . .

3.

Tablice decyzyjne. O tym pó¹niej. . .

4.

Pseudoj¦zyk

rodzaj formalnego zapisu podobny

do. . .

5.

J¦zyk programowania. Nast¦pny semestr??? Wcale!!?

Zapis algorytmu

1.

Sªowami. Nale»y u»ywa¢ prostych zda« (raczej
równowa»ników zda«) w trybie rozkazuj¡cym.

2.

Schematy blokowe. O tym za chwil¦. . .

3.

Tablice decyzyjne. O tym pó¹niej. . .

4.

Pseudoj¦zyk

rodzaj formalnego zapisu podobny

do. . .

5.

J¦zyk programowania. Nast¦pny semestr??? Wcale!!?

Zapis algorytmu

Schemat blokowy

Schemat blokowy (ang. block diagram, owchart)
diagram, na którym procedura, system albo program
komputerowy, s¡ reprezentowane przez opisane gury
geometryczne poª¡czone liniami zgodnie z kolejno±ci¡
wykonywania czynno±ci wynikaj¡cych z przyj¦tego
algorytmu rozwi¡zania zadania.
Schemat blokowy pozwala dostrzec istotne etapy algorytm
i logiczne zale»no±ci mi¦dzy nimi.
Zale»nie od przedstawianego zagadnienia stosowane s¡
ró»ne zestawy gur geometrycznych zwanych blokami,
których ksztaªty reprezentuj¡ umownie rodzaje
elementów skªadowych.

Schemat blokowy

Blok graniczny

Blok graniczny oznacza on
pocz¡tek, koniec, przerwanie
lub wstrzymanie wykonywania
dziaªania, np. blok startu
programu.

Schemat blokowy

Blok wej±cia-wyj±ci

Blok wej±cia-wyj±cia
przedstawia czynno±¢
wprowadzania danych do
programu i przyporz¡dkowania
ich zmiennym dla pó¹niejszego
wykorzystania jak i
wyprowadzenia wyników
oblicze«, np. czytaj z, pisz
z+10.

Schemat blokowy

Blok obliczeniowy

Blok obliczeniowy oznacza
wykonanie operacji w efekcie,
której zmieni¡ si¦ warto±ci,
posta¢ lub miejsce zapisu
danych, np. z = z + 1.

Schemat blokowy

Blok decyzyjny

Blok decyzyjny przedstawia
wybór jednego z dwóch
wariantów wykonywania
programu na podstawie
sprawdzenia warunku
wpisanego w ów blok, np.
a = b.

Schemat blokowy

Blok wywoªania podprogramu

Blok wywoªania podprogramu
oznacza zmian¦ wykonywanej
czynno±ci na skutek wywoªania
podprogramu, np. MAX(x,y,z)

Schemat blokowy

Blok fragmentu

Blok fragmentu przedstawia
cz¦±¢ programu zde niowanego
odr¦bnie, np. sortowanie.

Schemat blokowy

Blok komentarza

Blok komentarza pozwala
wprowadza¢ komentarze
wyja±niaj¡ce poszczególne
cz¦±ci schematu co uªatwia
zrozumienie go czytaj¡cemu,
np. wprowadzenie danych.

Schemat blokowy

Š¡cznik wewn¦trzny

Š¡cznik wewn¦trzny sªu»y do
ª¡czenia odr¦bnych cz¦±ci
schematu znajduj¡cych si¦ na
tej samej stronie, powi¡zane
ze sob¡ ª¡czniki oznaczone s¡
tym samym napisem, np. A1, 7.

Schemat blokowy

Š¡cznik zewn¦trzny

Š¡cznik zewn¦trzny sªu»y do
ª¡czenia odr¦bnych cz¦±ci
schematu znajduj¡cych si¦ na
odr¦bnych stronach, powinien
by¢ opisany jak ª¡cznik
wewn¦trzny, pozatym powinien
zawiera¢ numer strony, do
której si¦ odwoªuje, np. 4.3,
2,B2.

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Wersja sªowna

1.

Wybierz dowoln¡ osob¦ z sali, traktuj j¡ jako
najwi¦ksz¡ (i postaw przy drzwiach).

2.

Czy zostaªy jakie± osoby na sali? je»eli tak

przejd¹

do punktu

5

.

3.

Je»eli nie

najwi¦ksz¡ osob¡ jest ta stoj¡ca przy

drzwiach.

4.

Koniec algorytmu

5.

We¹ kolejn¡ osob¦ z sali.

6.

Porównaj j¡ z t¡ stoj¡c¡ przy drzwiach

czy jest

wi¦ksza?

7.

Je»eli nie

przejd¹ do

2

8.

Je»eli tak

zamienia osob¦ stoj¡c¡ przy drzwiach;

przejd¹ do

2

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

nie

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

nie

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

tak

nie

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

tak

nie

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

tak

nie

nie

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

tak

nie

nie

tak

Wybór osoby najwy»szej na sali

Schemat blokowy

Start

Wybierz

kogo-

kolwiek

Czy kto±

zostaª?

We¹

kolejn¡

osob¦

Czy

wi¦ksza?

Najwi¦kszy

przy

drzwiach

Koniec

Zamie«

przy

drzwiach

tak

nie

nie

tak

Algorytm Euklidesa

Sªownie

1.

[Znajdowanie reszty] Podziel m przez n i niech r
oznacza reszt¦ z tego dzielenia. (Mamy 0 ≤ r < n.)

2.

[Czy wyszªo zero?] Je±li r = 0 zako«cz algorytm;
odpowiedzi¡ jest n.

3.

[Upraszczanie] Wykonaj m ← n, n ← r i wró¢ do
kroku

1

.

Algorytm Euklidesa

Schemat blokowy

Zapiszmy teraz Algorytm Euklidesa w postaci schematu
blokowego:

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

nie

tak

Tablice decyzyjne

I

Alternatywa dla schematu blokowego.

I

Bardzo wygodne w przypadku opisu problemów z
ogromn¡ ilo±ci¡ decyzji.

I

Nie¹le nadaje si¦ do opisu problemów z »ycia
wzi¦tych .

I

‘rednie zastosowanie w przypadku problemów
obliczeniowych.

I

Dzi± ju» nieco zapomniane.

Tablice decyzyjne c.d

Pomysª tak, gdzie± z lat 50 (zeszªego wieku)!
Tablica decyzyjna to mieszanka warunków i decyzji które
nale»y podejmowa¢ w zale»no±ci od ich speªnienia.

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Zakup samochodu

cena nadmierna

cena OK

cena niedoszaco-
wana

Samochód speªnia
wszystkie wyma-
gania

Targuj si¦; jak si¦
nie uda

wró¢

nast¦pnego dnia i
targuj si¦; kup na-
wet jak nie uda si¦
zbi¢ ceny

Targuj si¦; kup
niezale»nie od wy-
niku targów

kup

Samochód

nie

speªnia wszystkich
wymaga« ale stan
i wyposa»enie s¡
akceptowalne

Rezygnuj

Targuj si¦; kup je-
»eli zbiªe± cen¦

Targuj si¦; kup
niezale»nie od wy-
ników targów

Samochód

nie

speªnia wymaga«

Rezygnuj

Rezygnuj

Targuj si¦ o dodat-
ki; kup je±li cena
dodatków jest roz-
s¡dna

Wkªadanie palta

R1 R2 R3

C1 Pada

T

T

N

C2 Zimno

T

N

T

A1 Wªó» ocieplany pªaszcz przeciwdesz-

czowy

X

A2 Wªó» zwykªy pªaszcz przeciwdeszczo-

wy

X

A3 Wªó» ciepªy pªaszcz

X

Wkªadanie palta c.d.

W tabeli pomin¦li±my warunek:
Pada N
Zimno N
nie wymaga on »adnej specjalnej akcji, cho¢ mo»na by go
doda¢ de niuj¡c akcj¦: Nie wkªadaj »adnego pªaszcza .

Przykªad: sklepik

Kolejny przykªad to tablica decyzyjna opisuj¡ca dziaªania
zwi¡zane z przyj¦ciem i realizacj¡ zamówienia.
Tablica uwzgl¦dnia te» polityk¦ rmy, któr¡ mo»na opisa¢
tak:

1.

Firma obsªuguje tylko zarejestrowanych klientów.

2.

Firma dostarcza tylko towary znajduj¡ce si¦ na li±cie
towarów.

Sklepik c.d.

C1 Towar na li±cie

T N

T

C2 Klient zarejestrowany

T

N T

C3 Wystarczaj¡cy zapas towaru

T

N

A1 Zarezerwuj towar

X

A2 Zarejestruj transakcj¦

X

A3 Zapisz zamówienie na li±cie do reali-

zacji

X

A4 Wy±lij towar

X

A5 Odrzu¢ transakcj¦

X

X

Struktura steruj¡ca

Tworz¡c algorytm zapisujemy go jako ci¡g polece«. Po
cichu zakªadamy, »e poszczególne dziaªania w sposób
naturalny nast¦puj¡ po sobie. (W algorytmach kucharskich
b¦dzie to co± takiego: . . . Delikatnie doªó» czekolad¦, [a
potem] ponownie lekko podgrzej. . .
Czasami b¦d¡ pojawia¢ si¦ dziaªania warunkowe (Jeśli
. . . co±. . . to . . . co±. . . ).

Iteracje (p¦tle)

Iteracja ograniczona

Niektóre algorytmy sugeruj¡

powtarzanie pewnych dziaªa« (Wykonaj
. . . co±. . . N razy) ±ci±le okre±lon¡ liczb¦ razy.

Iteracja warunkowa

Czasami czynno±¢ trzeba powtarza¢

tak dªugo, a» zostanie speªniony jaki± warunek.

P¦tle mo»na zagnie»d»a¢ jedne w drugich!

Przekazanie sterowania

Skok bezwarunkowy

ma posta¢ przejd¹ do G ( G" to

okre±lone miejsce programu

algorytmu).

Skok warunkowy

przejd¹ do G je»eli speªniony jest jaki±

warunek.

Du»a liczba skoków (do przodu, do tyªu) zmniejsza
czytelno±¢ algorytmu.
Skoki powoduj¡ równie» problemy techniczne: czy mo»na

wyskoczy¢ ze ±rodka p¦tli? Czy mo»na do ±rodka p¦tli

wskoczy¢?

Podprogramy

Podprogram

wyodr¦bniony zestaw instrukcji (osobny

algorytm) realizuj¡cy pewne zamkni¦te dzieªo : ma
dobrze

1

zde niowany zestaw danych (parametrów)

wej±ciowych, zestaw danych wyj±ciowych i relacj¦
(zale»no±¢) pomi¦dzy nimi.

I

Oszcz¦dno±¢ kodu (ta sama czynno±¢ wykonywana
kilkakrotnie w ró»nych miejscach programu).

I

Przejrzysto±¢ kodu ( du»y problem dzielimy na
mniejsze, dobrze zde niowane fragmenty).

1

U»ywaj¡c sªowa dobrze b¦d¦ miaª na my±li precyzyjnie .

Zmienna

Rodzaj pudeªka do którego mo»na co± wªo»y¢, wyj¡¢. (Tak
jak pokój hotelowy.) Zmienna zazwyczaj ma jak¡± nazw¦
(przez któr¡ si¦ do niej odwoªujemy). Warto±¢ zmiennej
(zawarto±¢ pokoju hotelowego) zmienia si¦ w razie
potrzeb.
W algorytmach u»ywamy zmiennych do przechowywania
(pami¦tania) ró»nych warto±ci. Zakªadamy wówczas, »e to
co tam wstawimy nie ulega zmianie (zniszczeniu) w sposób
samorzutny.
Fakt przypisania warto±ci do zmiennej zaznaczamy w
algorytmach w bardzo ró»ny sposób. Najprostszy b¦dzie
taki: X = 5, X := X + 1 czy X ← A + B.

Wektor, tablica I

Zestaw warto±ci w których wprowadzili±my rodzaj
uporz¡dkowania (dyskutuj¡c na temat wyszukiwania warto±ci
maksymalnej mówili±my we¹my pierwsz¡ warto±¢

albo

jako± tak). Je»eli szereg zmiennych tego samego typu ustawimy
jedn¡ za drug¡ (i zaczniemy si¦ do nich odwoªywa¢ przez
numer: pierwsza, druga, . . . )

mamy do czynienia z wektorem

(zwanym czasami tablic¡ jednowymiarow¡). Jest to pewna
analogia do pi¦tra w hotelu: jest tam szereg pokoi.

Wektor, tablica II

Nazw¦ przypisujemy caªemu wektorowi, do poszczególnych jego
elementów b¦dziemy odwoªywa¢ si¦ przez numer, co
zapisujemy najcz¦±ciej jako± tak: V(I) (zawarto±¢ I tej komórki
wektora V) albo tak V[J]. I (J) nazywany bywa indeksem
wektora.

V(1) V(2) V(3) V(4) V(5)

Analogiczny zapis matematyczny:

V

1

V

2

V

3

V

4

V

5

Tablica (wielowymiarowa) I

Struktura grupuj¡ca dane w sposób bardziej zªo»ony.

Czasami mamy potrzeb¦ grupowania danych w struktury
bardziej zªo»one ni» wektory. Struktura numerowana za
pomoc¡ dwu indeksów nazywana bywa tabel¡.

Nasuwa si¦ tu analogia do caªego hotelu: pierwszym
indeksem jest numer pi¦tra drugim

numer pokoju na

Tablica (wielowymiarowa) II

pi¦trze. My mówi¢ b¦dziemy o wierszach (poziome
wektory) lub kolumnach (pionowe) tablicy.

Odwoªanie do elementu tabeli zapisywane bywa tak:
W(I, J) albo W[I, J] lub rzadziej jako W[I][J].

W najprostszych sytuacjach tablice maja wszystkie
wiersze (kolumny) jednakowej dªugo±ci. Mo»liwe s¡
jednak i bardziej ogólne przypadki.

Tablica (wielowymiarowa) III

Zapis matematyczny:

v

1,1

v

1,2

v

1,3

v

2,1

v

2,2

v

2,3

v

3,1

v

3,2

v

3,3

v

4,1

v

4,2

v

4,3

Zapis algorytmiczny :

V(1, 1) V(1, 2) V(1, 3)
V(2, 1) V(2, 2) V(2, 3)
V(3, 1) V(3, 2) V(3, 3)
V(4, 1) V(4, 2) V(4, 3)

Kolejka

I

Struktura bardzo podobna do wektora.

I

Dane dostarczane s¡ do jednego ko«ca .

I

Do odbioru danych sªu»y drugi koniec .

Stos

I

Struktura podobna do wektora.

I

Dane dostarczane s¡ do jednego ko«ca .

I

Ten sam koniec sªu»y do ich odbioru.

Drzewo albo hierarchia

I

Struktura z porz¡dkiem.

I

Wyró»nia si¦ specjalny obiekt b¦d¡cy pocz¡tkiem
caªej struktury: korze«.

I

Inne elementy to nast¦pniki albo potomstwo.

I

Ka»dy obiekt mo»e mie¢ kilku równowa»nych
potomków.

I

Ka»dy potomek to w¦zeª drzewa.

I

Obiekty, które nie maj¡ potomków to li±cie.

I

Gaª¡¹ to droga od korzenia do li±cia.

Drzewo

root

left

right

child

a

b

child

Inne struktury danych

I

Listy (pewne podobie«stwo do wektorów czy tablic).

I

Bazy danych (pewne podobie«stwo do tablic).

I

Grafy (pewne podobie«stwo do drzew).

Cz¦±¢ I

Dygresja

Raz jeszcze wybór osoby najwy»szej

(na sali)

1.

Wysoko±ci wszystkich osób zostaªy zapisane w tablicy
o nazwie W. (Powinno by¢ wysoko±¢, ale za du»o
miejsca zajmuje.)

2.

Zmienna N zawiera liczb¦ osób w sali (dªugo±¢ tablicy
W).

3.

Zmienna MAX po zako«czeniu algorytmu zawiera
najwi¦ksz¡ warto±¢ zapisan¡ w W (wysoko±¢ osoby
najwy»szej).

4.

I

zmienna pomocnicza.

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

nie

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

nie

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

tak

nie

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

tak

nie

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

tak

nie

nie

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

tak

nie

nie

tak

Najwi¦ksza warto±¢ w tablicy

Start

MAX =

W[1]

I = 1

I < N?

I= I + 1

W[I] >

MAX

Wydrukuj

MAX

Koniec

MAX =

W[I]

tak

nie

nie

tak

Banalny problem

1.

Dopóki X 6= 1, dopóty wykonuj X ← X − 2.

2.

Zatrzymaj si¦.

Gdy X = 7 algorytm wygeneruje nast¦puj¡ce warto±ci X:
7, 5, 3, 1
i zatrzyma si¦. . .
Gdy X = 8 b¦dzie nieco inaczej:
8, 6, 4, 2, 0, -2, -4, -6, -8,. . .
i algorytm nie zatrzyma si¦.
Jak wida¢ wszystko dziaªa tylko dla liczb dodatnich
nieparzystych, bo w przypadku liczb parzystych udaje
nam si¦ min¡¢ jedynk¦.

Banalny problem

1.

Dopóki X 6= 1, dopóty wykonuj X ← X − 2.

2.

Zatrzymaj si¦.

Gdy X = 7 algorytm wygeneruje nast¦puj¡ce warto±ci X:
7, 5, 3, 1
i zatrzyma si¦. . .

Gdy X = 8 b¦dzie nieco inaczej:
8, 6, 4, 2, 0, -2, -4, -6, -8,. . .
i algorytm nie zatrzyma si¦.
Jak wida¢ wszystko dziaªa tylko dla liczb dodatnich
nieparzystych, bo w przypadku liczb parzystych udaje
nam si¦ min¡¢ jedynk¦.

Banalny problem

1.

Dopóki X 6= 1, dopóty wykonuj X ← X − 2.

2.

Zatrzymaj si¦.

Gdy X = 7 algorytm wygeneruje nast¦puj¡ce warto±ci X:
7, 5, 3, 1
i zatrzyma si¦. . .
Gdy X = 8 b¦dzie nieco inaczej:
8, 6, 4, 2, 0, -2, -4, -6, -8,. . .
i algorytm nie zatrzyma si¦.

Jak wida¢ wszystko dziaªa tylko dla liczb dodatnich
nieparzystych, bo w przypadku liczb parzystych udaje
nam si¦ min¡¢ jedynk¦.

Banalny problem

1.

Dopóki X 6= 1, dopóty wykonuj X ← X − 2.

2.

Zatrzymaj si¦.

Gdy X = 7 algorytm wygeneruje nast¦puj¡ce warto±ci X:
7, 5, 3, 1
i zatrzyma si¦. . .
Gdy X = 8 b¦dzie nieco inaczej:
8, 6, 4, 2, 0, -2, -4, -6, -8,. . .
i algorytm nie zatrzyma si¦.
Jak wida¢ wszystko dziaªa tylko dla liczb dodatnich
nieparzystych, bo w przypadku liczb parzystych udaje
nam si¦ min¡¢ jedynk¦.

Problem bardziej skomplikowany. . .

1.

Dopóki X 6= 1, dopóty wykonuj:

1.1

Je±li X jest liczb¡ parzyst¡ to ustaw X ← X/2.

1.2

W przeciwnym razie ustaw X ← 3X + 1

2.

Zatrzymaj si¦

Zacznijmy od 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10,
5, 16, 8, 4, 2, 1
Jak b¦dzie dla innych liczb?

Problem bardziej skomplikowany. . .

1.

Dopóki X 6= 1, dopóty wykonuj:

1.1

Je±li X jest liczb¡ parzyst¡ to ustaw X ← X/2.

1.2

W przeciwnym razie ustaw X ← 3X + 1

2.

Zatrzymaj si¦

Zacznijmy od 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10,
5, 16, 8, 4, 2, 1

Jak b¦dzie dla innych liczb?

Problem bardziej skomplikowany. . .

1.

Dopóki X 6= 1, dopóty wykonuj:

1.1

Je±li X jest liczb¡ parzyst¡ to ustaw X ← X/2.

1.2

W przeciwnym razie ustaw X ← 3X + 1

2.

Zatrzymaj si¦

Zacznijmy od 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10,
5, 16, 8, 4, 2, 1
Jak b¦dzie dla innych liczb?

Problem bardziej skomplikowany. . . I

1.

Dopóki X 6= 1, dopóty wykonuj:

1.1

Je±li X jest liczb¡ parzyst¡ to ustaw X ← X/2.

1.2

W przeciwnym razie ustaw X ← 3X + 1

2.

Zatrzymaj si¦

Problem bardziej skomplikowany. . . II

Okazuje si¦, »e powy»szy algorytm albo ko«czy dziaªanie
stosunkowo szybko, albo generuje niesko«czony ci¡g
chaotycznych liczb.

Nie udaªo si¦ nikomu ani udowodni¢, »e generowane
sekwencje zaczynaj¡ si¦ powtarza¢ (co oznacza, »e
algorytm nie zatrzyma si¦ nigdy) ani dowie±¢, »e dla

Problem bardziej skomplikowany. . . III

jakiej± konkretnej warto±ci pocz¡tkowej X algorytm
zatrzyma si¦.

Uczeni w pi±mie wierz¡, »e algorytm zatrzymuje si¦ dla
liczb dodatnich. . .