Algorytmy

Cz¦±¢ IV

wer. 1.2

Wojciech Myszka

30 listopada 2008

Spis tre±ci I

Spis tre±ci

Jak si¦ tworzy algorytmy?

Poszukiwania i w¦drówki

Dziel i zwyci¦»aj

Rekurencja

De nicje
Przykªad
Schemat blokowy
Inne zadania rekurencyjne

Ci¡g Fibonacciego

Spis tre±ci II

Najwi¦kszy wspólny dzielnik
Symbol Newtona

Wie»e Hanoi
Minimum i maksimum

Zachªanne algorytmy

Planowanie dynamiczne

Jak si¦ tworzy algorytmy?

Moja odpowied¹ jest krótka:

Nie wiem!

Jak si¦ tworzy algorytmy?

Moja odpowied¹ jest krótka:

Nie wiem!

Poszukiwania i w¦drówki

Czyli przegl¡d

1.

Bardzo cz¦sto zachodzi potrzeba obej±cia wszystkich
elementów struktury.

2.

W najprostszym przypadku struktura zadana jest
jawnie (tablica, wektor, drzewo).

3.

W wielu przypadkach

trzeba dobrze przyjrze¢ si¦

zagadnieniu, »eby struktur¦ zauwa»y¢.

4.

Gdy zadanie ma szereg wariantów

wystarczy

przejrze¢ je wszystkie

W ka»dym przypadku dziaªanie algorytmu sprowadza si¦
do przegl¡du wszystkich elementów struktury.

Przegl¡d

P¦tla

1.

Start

2.

i ← 0

3.

Zrób co±. . .

4.

i ← i + 1

5.

Je»eli i ≤ N przejd¹ do 3

6.

W przeciwnym razie

Koniec

Przegl¡d

Przykªad

I

Dany jest prosty wielok¡t wypukªy.

I

Nale»y znale¹¢ takie dwa punkty na jego obwodzie,
które dzieli najwi¦ksza odlegªo±¢.

Jak to rozwi¡za¢?

1

2

3

4

5

6

1 (4,13)
2 (14,8)
3 (15,2)
4 (10,0)
5 (4,0)
6 (0,5)

Przykªad cd

1

2

3

4

5

6

1

0

11,2 15,6

2 11,2

0

3 15,6

0

4

0

6

5

6

0

6,4

6

6,4

0

Przykªad cd

1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

a)

1

2

3

4

5

6

b)

c)

d)

e)

f)

Podziaª na mniejsze zadania

I

Gdy nie mo»emy rozwi¡za¢ du»ego zadania
czasami mo»na je podzieli¢ na kilka mniejszych

I

Je»eli to jest za du»e

dzielimy dalej. . .

Podziaª. . .

Przykªad

Mamy znale¹¢ maksimum i minimum z (bardzo dªugiej?)
listy liczb oznaczonej jako L.

Jedn¡ metod¦ ju» znamy: jest dosy¢ prosta. . .

De nicje

Za wikipedi¡

Rekursja albo rekurencja (ang. recursion, z ªac. recurrere,
przybiec z powrotem) to w logice, programowaniu
i w matematyce odwoªywanie si¦ (np. funkcji lub de nicji)
do samej siebie.

Przykªad

Silnia

Wersja klasyczna

0! = 1
n! = Q

n
i=1

i

albo
n! = 1 × 2 × 3 × · · · × n

Wersja inna

0! = 1
n! = n × (n − 1)!

Przykªad

Silnia

Wersja klasyczna

0! = 1
n! = Q

n
i=1

i

albo
n! = 1 × 2 × 3 × · · · × n

Wersja inna

0! = 1
n! = n × (n − 1)!

Przykªad

Kilka liczb

In[1]:= 10!
Out[1]= 3628800
In[3]:= 20!
Out[3]= 2432902008176640000
In[4]:= 30!
Out[4]= 265252859812191058636308480000000
In[5]:= 40!
Out[5]=
815915283247897734345611269596115894272000000000

Silnia

Schematy blokowe

Wersja klasyczna

1.

Je»eli n = 0, silnia równa si¦ 1; koniec algorytmu.

2.

silnia ← 1

3.

Powtarzaj dla i zmieniaj¡cego si¦ od 1 do n
silnia = silnia × i

4.

Koniec algorytmu.

Wersja rekurencyjna

1.

Funkcja Silnia (parametrem jest n)

2.

Je»eli n = 0; wynik podstaw 1; koniec programu

3.

wynik = wynik× Silnia(n − 1)

4.

koniec

Silnia

Schematy blokowe

Wersja klasyczna

1.

Je»eli n = 0, silnia równa si¦ 1; koniec algorytmu.

2.

silnia ← 1

3.

Powtarzaj dla i zmieniaj¡cego si¦ od 1 do n
silnia = silnia × i

4.

Koniec algorytmu.

Wersja rekurencyjna

1.

Funkcja Silnia (parametrem jest n)

2.

Je»eli n = 0; wynik podstaw 1; koniec programu

3.

wynik = wynik× Silnia(n − 1)

4.

koniec

Rekurencja na obrazkach: Droste Effect

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Rekurencja

Escher

Ci¡g Fibonacciego

Schemat

b(0) = 0
b(1) = 1
b(n) = b(n - 1) + b(n - 2), dla n ≥ 2

Ci¡g Fibonacciego

Schemat

b(0) = 0
b(1) = 1
b(n) = b(n - 1) + b(n - 2), dla n ≥ 2

0

0

1

1

2

1 =B2+B1

3

2 =B3+B2

4

3

5

5

6

8

7

13

8

21

9

34

10

55

11

89

12

144

13

233

14

377

15

610























0

100

200

300

400

500

600

700

0

2

4

6

8

10

12

14

16











Najwi¦kszy wspólny dzielnik

gcd(0,n)=n

gcd(k, n) =



n

dla k = 0;

gcd(n mod k, k)

dla k > 0.

Porówna¢ ze schematem blokowym ( metoda Euklidesa ),
który byª prezentowany wcze±niej

Najwi¦kszy wspólny dzielnik

gcd(0,n)=n

gcd(k, n) =



n

dla k = 0;

gcd(n mod k, k)

dla k > 0.

Porówna¢ ze schematem blokowym ( metoda Euklidesa ),
który byª prezentowany wcze±niej

Symbol Newtona

Wersja normalna

n
0

=

1

n
k

=

n(n−1)···(n−k+1)

k!

Wersja rekurencyjna

n
k

=

n−1

k

+

n−1
k−1

n
0

=

1

Wie»e Hanoi

Prosta zabawka dzieci¦ca

na patyku nanizanych jest pewna

liczba kr¡»ków tak, »e na wi¦kszym zawsze le»y kr¡»ek
mniejszy. Zadaniem naszym jest umieszczenie wszystkich
kr¡»ków na s¡siednim patyku (korzystaj¡c z jednego tylko

patyka pomocniczego) w tej samej kolejno±ci. Podczas

ka»dego ruchu pami¦ta¢ trzeba, »e kr¡»ek wi¦kszy nie mo»e
znale¹¢ si¦ nigdy na kr¡»ku mniejszym.

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























1

Wie»e Hanoi

Przykªad

Trzy kr¡»ki















 







2

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























3

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























4

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























5

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























6

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























7

Wie»e Hanoi

Przykªad

Trzy kr¡»ki

























8

Wie»e Hanoi

Przykªad

Dwa kr¡»ki

Wie»e Hanoi

Przykªad

Dwa kr¡»ki

















Wie»e Hanoi

Przykªad

Dwa kr¡»ki

















Wie»e Hanoi

Przykªad

Dwa kr¡»ki

















Wie»e Hanoi

Przykªad

Dwa kr¡»ki

















Wie»e Hanoi I

Czemu taka nazwa?

W wielkiej ±wi¡tyni Benares w Hanoi, pod kopuª¡, która

zaznacza ±rodek ±wiata, znajduje si¦ pªytka z br¡zu, na
której umocowane s¡ trzy diamentowe igªy, wysokie na
ªokie¢ i cienkie jak talia osy.

Na jednej z tych igieª, w momencie stworzenia ±wiata,
Bóg umie±ciª 64 kr¡»ki ze szczerego zªota. Najwi¦kszy
z nich le»y na pªytce z br¡zu, a pozostaªe jeden na
drugim, id¡c malej¡co od najwi¦kszego do najmniejszego.
Jest to wie»a Brahma.

Wie»e Hanoi II

Czemu taka nazwa?

Bez przerwy we dnie i w nocy kapªani przekªadaj¡ kr¡»ki
z jednej diamentowej igªy na drug¡, przestrzegaj¡c
niewzruszonych praw Brahma.
Prawa te chc¡, aby kapªan na sªu»bie braª tylko jeden
kr¡»ek na raz i aby umieszczaª go na jednej z igieª w ten
sposób, by nigdy nie znalazª si¦ pod nim kr¡»ek mniejszy.
Wówczas, gdy 64 kr¡»ki zostan¡ przeªo»one z igªy, na
której umie±ciª je Bóg w momencie stworzenia ±wiata, na
jedn¡ z dwóch pozostaªych igieª, wie»a, ±wi¡tynia,
bramini rozsypi¡ si¦ w proch i w jednym oka mgnieniu
nast¡pi koniec ±wiata .

Kiedy nast¡pi koniec ±wiata?

Wie»e Hanoi

Koniec ±wiata

I

Przy trzech kr¡»kach trzeba 7 ruchów (przy dwu

3!)

I

Gdy kr¡»ków jest 64

trzeba 2

64

−

1 ruchów, czyli

18446744073709551615

I

Zakªadamy, »e przeniesienie kr¡»ka zajmuje 1
sekund¦.

I

Rok ma 365 × 24 × 3600 sekund (31536000)

I

Praca ta zajmie 2

64

/

31536000 lat (prawie 585

miliardów lat)

Wie»e Hanoi

Koniec ±wiata

I

Przy trzech kr¡»kach trzeba 7 ruchów (przy dwu

3!)

I

Gdy kr¡»ków jest 64

trzeba 2

64

−

1 ruchów, czyli

18446744073709551615

I

Zakªadamy, »e przeniesienie kr¡»ka zajmuje 1
sekund¦.

I

Rok ma 365 × 24 × 3600 sekund (31536000)

I

Praca ta zajmie 2

64

/

31536000 lat (prawie 585

miliardów lat)

Wie»e Hanoi

Koniec ±wiata

I

Przy trzech kr¡»kach trzeba 7 ruchów (przy dwu

3!)

I

Gdy kr¡»ków jest 64

trzeba 2

64

−

1 ruchów, czyli

18446744073709551615

I

Zakªadamy, »e przeniesienie kr¡»ka zajmuje 1
sekund¦.

I

Rok ma 365 × 24 × 3600 sekund (31536000)

I

Praca ta zajmie 2

64

/

31536000 lat (prawie 585

miliardów lat)

Wie»e Hanoi

Koniec ±wiata

I

Przy trzech kr¡»kach trzeba 7 ruchów (przy dwu

3!)

I

Gdy kr¡»ków jest 64

trzeba 2

64

−

1 ruchów, czyli

18446744073709551615

I

Zakªadamy, »e przeniesienie kr¡»ka zajmuje 1
sekund¦.

I

Rok ma 365 × 24 × 3600 sekund (31536000)

I

Praca ta zajmie 2

64

/

31536000 lat (prawie 585

miliardów lat)

Wie»e Hanoi

Koniec ±wiata

I

Przy trzech kr¡»kach trzeba 7 ruchów (przy dwu

3!)

I

Gdy kr¡»ków jest 64

trzeba 2

64

−

1 ruchów, czyli

18446744073709551615

I

Zakªadamy, »e przeniesienie kr¡»ka zajmuje 1
sekund¦.

I

Rok ma 365 × 24 × 3600 sekund (31536000)

I

Praca ta zajmie 2

64

/

31536000 lat (prawie 585

miliardów lat)

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Jak rozwi¡za¢ ten problem?

I

Gdy kr¡»ek jest tylko jeden

problem nie istnieje.

I

Dla dwu kr¡»ków problem jest banalny.

I

Dla trzech

mo»na go podzieli¢ na trzy zadania:

1.

Przeniesienie dwu górnych kr¡»ków na trzeci
patyczek .

2.

Przeniesienie najwi¦kszego kr¡»ka na patyczek
drugi .

3.

Ponowne przeniesienie dwu kr¡»ków na najwi¦kszy. . .

Wie»e Hanoi

Przypadek ogólny

1.

Przenie±my z A na C N − 1 kr¡»ków.

2.

Pozostaªy kr¡»ek (najwi¦kszy!

ale z czego to

wynika?) przenie±my z A na B.

3.

Do pozostaªych (N − 1) kr¡»ków zastosujmy powy»szy
algorytm (patyk B mo»emy wykorzystywa¢ jako
roboczy, bo na samym spodzie znajduje si¦ kr¡»ek
najwi¦kszy).

4.

powy»sz¡ procedur¦ nale»y powtarza¢ a» do
zako«czenia zadania.

(Pierwszy patyczek nazwali±my A, drugi

B a trzeci

C.)

Wie»e Hanoi

Procedura (rekurencyjna)

Procedura przenie± N (kr¡»ków) z X na Y u»ywaj¡c Z:

1.

Je±li N = 1 to wypisz X → Y ;

2.

w przeciwnym razie (je»eli N > 1) wykonaj co

nast¦puje:

2.1

wywoªaj przenie± N − 1 z X na Z u»ywaj¡c Y;

2.2

wypisz X → Y ;

2.3

wywoªaj przenie± N − 1 z Z na Y u»ywaj¡c X;

3.

wró¢;

Zapis symboliczny A → B oznacza we¹ kr¡»ek z patyka
oznaczonego A i przenie± go na patyk oznaczony B
Procedura sªu»y jedynie do wypisywania instrukcji dla

operataora czªowieka .

Wie»e Hanoi

Realizacja

Start
przenie±¢ 3 z A na B u»ywaj¡c C

1.

przenie±¢ 2 z A na C u»ywaj¡c B

1.1

przenie±¢ 1 z A na B u»ywaj¡c C

1.1.1

A → B

1.2

A → C

1.3

przenie±¢ 1 z B na C u»ywaj¡c A

1.3.1

B → C

2.

A → B

3.

przenie±¢ 2 z C na B u»ywaj¡c A

3.1

przenie±¢ 1 z C na A u»ywaj¡c B

3.1.1

C → A

3.2

C → B

3.3

przenie±¢ 1 z A na B u»ywaj¡c C

3.3.1

A → B

Podziaª. . .

Przykªad

procedura znajd¹-min-i-max-w L;

1.

Je»eli lista skªada si¦ z jednego elementu to nadaj MAX i MIN
wªa±nie jego warto±¢, je±li lista skªada si¦ z dwu elementów to
nadaj MIN warto±¢ mniejszego z nich, a MAX wi¦kszego;

2.

W przeciwnym razie wykonaj co nast¦puje:

2.1

Podziel list¦ na poªowy L1 i L2;

2.2

wykonaj znajd¹-min-i-max-w L1 umieszczaj¡c
otrzymane warto±ci w MIN1 i MAX1

2.3

wykonaj znajd¹-min-i-max-w L2 umieszczaj¡c
otrzymane warto±ci w MIN2 i MAX2

2.4

nadaj MIN mniejsz¡ warto±¢ z MIN1 i MIN2

2.5

nadaj MAX wi¦ksz¡ warto±¢ z MAX1 i MAX2

3.

zako«cz z warto±ciami MIN i MAX

Zachªanne algorytmy

I

Czasami zadanie sprowadza si¦ do znalezienia
rozwi¡zania najlepszego w jakim± sensie

Popatrzmy na przykªad: Mamy sie¢ miast i leniwego
przedsi¦biorc¦, któremu zlecono uªo»enie torów
zapewniaj¡cych poª¡czenie mo»liwo±¢ przejazdu z
dowolnego miasta do ka»dego innego. Innych warunków
nie postawiono. . .
Koszt poªo»enia torów jest proporcjonalny do odlegªo±ci
pomi¦dzy miastami. Leniwy przesi¦biorca chce rozwi¡za¢
problem jak najta«szym kosztem.

Zachªanne algorytmy

Przykªad

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

14

11

14

11

16

10

3

26

17

12

7

15

13

6

9

8

4

(Rysunek nie zachowuje proporcji)

Calkowity koszt 63

Zachªanne algorytmy

Przykªad

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

14

11

14

11

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

10

3

26

14

17

12

7

15

13

11

16

6

9

8

4

a)

b)

c)

d)

e)

f)

g)

h)

Zachªanne algorytmy

Czemu taka nazwa?

Planowanie dynamiczne

I

Zaªó»my, »e mamy (podobnie jak w zadaniu
poprzednim) szereg miast.

I

W poprzednim zadaniu mieli±my znale¹¢ taki ukªad
poª¡cze«, który (a) jest najta«szy i (b) pozwala na
przejazd z dowolnego miasta do ka»dego innego.

I

Teraz mamy znale¹¢ najta«sz¡ (najkrótsz¡) drog¦ z
miasta A do miasta B korzystaj¡c z istniej¡cej sieci
poª¡cze«.

Planowanie dynamiczne

Przykªad

A

B

C

D

E

F

G

14

3

5

2

6

11

7

7

3

5

7

6

A

B

C

D

E

F

G

14

3

5

2

6

11

7

7

3

5

7

6

A

B

C

D

E

F

G

14

3

5

2

6

11

7

7

3

5

7

6

Graf

Rozwiazanie zachlanne (koszt 15)

Rozwiazanie optymalne (koszt 13)

Planowanie dynamiczne

I

Jak wida¢ metoda zachªanna nie daje najlepszego
rozwi¡zania.

I

Zatem potrzebna b¦dzie nieco inna metoda
post¦powania

znacznie bardziej przewiduj¡ca .

I

Aby doj±¢ z A do B w pierwszym kroku mam trzy

mo»liwo±ci:

1.

przej±¢ do C

2.

przej±¢ do D

3.

przej±¢ do E

I

koszt pierwszej to 5 + koszt przej±cia z C do B

I

koszt drugiej to 3 + koszt przej±cia z D do B

I

koszt trzeciej to 14 + koszt przej±cia z G do B

Programowanie dynamiczne

Na czym powinien polega¢ optymalny wybór?

I

Oznaczmy przez L(x) koszt przej±cia z w¦zªa x do
w¦zªa B

I

na ka»dym etapie podró»y, gdy mo»emy przej±¢ z
w¦zªa V do w¦zªów C

1

, C

2

,. . . C

N

wybieramy tak¡

drog¦ aby

odlegªo±¢-z-V-do-C

K

+

L(C

K

)

byªa minimalna

Mo»na to zapisa¢ tak:

L(V) = min

K

odlegªo±¢-z-V-do-C

K

+

L(C

K

)

Programowanie dynamiczne

Taki zapis sugeruje równie» tu zastosowanie rekursji

ale

ostrzegam! jest to niebezpieczne. . .