RÓŻNORODNE ALGORYTMY OBLICZEŃ

I ICH KOMPUTEROWE REALIZACJE

Maciej M. Sysło

Uniwersytet Wrocławski

Uniwersytet UMK w Toruniu

[e-mail]

2

informatyka +

Algorytm, algorytmika

Algorytm

– opis rozwiązania krok po kroku

postawionego problemu lub sposobu
osiągnięcia jakiegoś celu

Pierwszy algorytm –

algorytm Euklidesa

300 p.n.e

algorytm

od

Muhammad

ibn Musa al-Chorezmi

IX w.

Algorytmika

– dziedzina zajmująca się algorytmami i

ich własnościami

informatyka +

3

Na str. 3-7 są zamieszczone
uwagi wstępne na temat
algorytmiki. Można je pominąć
i wrócić później.

Algorytmy a informatyka

Informatyka –

jedna z definicji:

dziedzina wiedzy i

działalności zajmująca się algorytmami

Czy zajmuje się też

algorytmami kulinarnymi?

Donald E. Knuth:

Mówi się często, że człowiek dotąd nie zrozumie czegoś,

zanim nie nauczy tego – kogoś innego.

W rzeczywistości,

człowiek nie zrozumie czegoś (

algorytmu

) naprawdę,

zanim nie zdoła nauczyć tego – komputera.

Ralf Gomory (IBM):

Najlepszym sposobem przyspieszania komputerów

jest obarczanie ich mniejszą liczbą działań (

szybszymi

algorytmami

)

informatyka +

4

Będziemy uczyć

komputery, czyli

programować je

!

Algorytmiczne rozwiązywanie problemu

Dla problemu – chcemy otrzymać rozwiązanie
komputerowe, które jest:

•

zrozumiałe

dla każdego, kto zna problemu

• poprawne

, czyli spełnia specyfikację (opis) problemu

• efektywne

, czyli nie marnuje czasu i pamięci komputera

Metoda rozwiązywania:

•

analiza

sytuacji problemowej

•

sporządzenie

specyfikacji

: wykaz danych, wyników i relacji

• projekt

rozwiązania

•

komputerowa realizacja rozwiązania –

implementacja

• testowanie poprawności

rozwiązania

•

dokumentacja

i

prezentacja

rozwiązania

informatyka +

5

Rozwiązywanie problemów z pomocą
komputerów

Objaśnienie dwóch terminów:

Problem

:

•problem, gdy nie podano nam, jak należy go rozwiązać, ale wiemy
wystarczająco, by poradzić sobie z nim
•a więc, problem jest dla każdego

nie tylko dla orłów

Programowanie:

•komputery wykonują tylko programy
•cokolwiek uruchamiamy na komputerze: Google, dokument w Word,
arkusz w Excel, naciśnięcie klawisza – jest programem
•każdy widoczny i niewidoczny efekt działania komputera to wynik
działania jakiegoś programu

Konkluzja:

powinniśmy

lepiej poznać programowanie

komputerów

informatyka +

6

Myślenie algorytmiczne
Myślenie komputacyjne
(ang. computational thinking)

informatyka +

7

Reklama firmy IBM z

1924 roku

Komputer to maszyna do

myślenia !!!

Różnorodne algorytmy obliczeń
i ich komputerowe realizacje PLAN

• Rozgrzewka (warm-up) – kilka krótkich programów
• Obliczanie wartości wielomianu – Schemat Hornera
• Liczby dziesiętne, binarne, … – system pozycyjny, zamiana

liczb między systemami

• Rekurencja: Wieże Hanoi, liczby Fibonacciego,

wyprowadzania liczb od początku

• Podnoszenie do potęgi – szybko!
• Algorytm Euklidesa
• Algorytmy zachłanne: wydawanie reszty, zmartwienie

kinomana, pakowanie plecaka, najdłuższa droga na
piramidzie

• Przeszukiwanie z nawrotami: wychodzenie z labiryntu i

rozstawianie hetmanów na szachownicy

informatyka +

8

Rozgrzewka przy komputerach

Rozgrzewka (warm-up)

– kilka krótkich programów:

• obliczanie pole trójkąta
• dodatkowo sprawdzanie, czy dane są dobre –

warunek

• obliczanie pola trójkąta dla ciągu danych –

iteracja

i

tablice

Ciekawe zadanie

dotyczące trójkątów:

Dane:

ciąg (bardzo długi) liczb

Odpowiedź:

czy z każdej trójki liczb z tego ciągu można

zbudować trójkąt?

Wskazówka:

istnieje rozwiązanie, w którym nie trzeba

sprawdzać warunku trójkąta dla każdej trójki liczb

informatyka +

9

Warsztaty
Algorytm, język programowania, komputer

informatyka +

10

Proces komputerowej realizacji
algorytmu:

•Opis algorytmu – słowny
•Zapis w języku programowania
(Pascal, C++)
•Kompilacja – przetłumaczenie na
język zrozumiały przez komputer
•Wykonanie
•Testowanie
•Dokumentacja

Obliczanie wartości wielomianu

Obliczanie wartości wielomianu jest bardzo ważną operacją w
komputerze, bo wartość każdej funkcji jest liczona jako wartość
wielomianu, np.

cos x = 1 – 0.49670x

2

+ 0.03705x

4

.

Wielomian stopnia 2:

w(x) = ax

2

+ bx + c = a*x*x + b*x + c 3 mnożenia 2 dodawania

w(x) = ax

2

+ bx + c = (a*x + b)*x + c

2

mnożenia 2 dodawania

Wielomian stopnia 3:

w(x) = ax

3

+ bx

2

+ cx + d = ((a*x + b)*x + c)*x + d 3 mnoż. 3 dod.

Wielomian stopnia n:

w

n

(x) = a

0

*x

n

+ a

1

*x

n-1

+ … + a

n-1

*x + a

n

=

= (a

0

*x

n-1

+ a

1

*x

n-2

+ … + a

n-1

)*x + a

n

= … =

= ((…((a

0

*x + a

1

)*x + a

2

)*x + … + a

n-2

)*x + a

n-1

)*x + a

n

informatyka +

11

Obliczanie wartości wielomianu
specyfikacja, algorytm

Problem Wielomian

– Obliczanie wartości wielomianu

Dane:

n – nieujemna liczba całkowita

a

0

, a

1

, a

2

, ..., a

n

– n + 1 współczynników wielomianu

z – wartość argumentu – obliczamy w

n

(z).

Wynik:

w

n

(z) – czyli wartość wielomianu w

n

(x) w punkcie x = z

Algorytm do obliczania wartości wielomianu:

w

n

(z) = ((…((a

0

*z + a

1

)*z + a

2

)*z + … + a

n-2

)*z + a

n-1

)*z + a

n

Schemat Hornera:

y := a

0

y := y*z + a

1

y := y*z + a

2

…..
y := y*z + a

n-1

y := y*z + a

n

informatyka +

12

y := a

0

y := y*z + a

i

dla i = 1, 2,

…, n

Specyfikacja
problemu – dokładny
opis problemu

n

mnożeń i

n

dodawań
Nie ma szybszego
algorytmu !!!

Schemat blokowy algorytmu Hornera

informatyka +

13

Instrukcja iteracyjna

Instrukcja

warunkowa:

rozgałęzienia

algorytmu

Ada Augusta,

córka Byrona,

uznawana powszechnie za pierwszą
programistkę komputerów,
przełomowe znaczenie

maszyny

analitycznej Ch. Babbage’a,

pierwowzoru dzisiejszych
komputerów, upatrywała właśnie „

w

możliwości wielokrotnego
wykonywania przez nią danego ciągu
instrukcji, z liczbą powtórzeń z góry
zadaną lub zależną od wyników
obliczeń

”, a więc w

iteracji

.

i := 0; y := a

0

Początkowe wartości

Czy i = n

Czyli, czy wyczerpano

wszystkie

współczynniki

Nie

Tak

i := i + 1

y := y*z +

a

i

Wyprowadź

wartość y

Koniec algorytmu

Pełny
schemat
blokowy
algorytm
u
Hornera

informatyka +

14

Algorytm Hornera w postaci programu
(Pascal)

program Horner;
var i,n :integer;

a,y,z :real;

begin
read(n); read(z);
read(a);
y:=a;
for i:=1 to n do begin
read(a);
y:=y*z+a
end;
write(y)
end.

informatyka +

15

nazwa programu
deklaracje, typy

zmiennych

blok programu – początek

czytaj n, czytaj z
czytaj pierwszy

współczynnik

początkowa wartość

wyniku

pętla od 1 do n
czytaj kolejny

współczynnik

powiększenie wyniku
iteracja – koniec
pisz wynik
blok programu – koniec

Algorytm Hornera – współczynniki w tablicy
(Pascal)

Program Horner_tablica;
var i,n :integer;
y,z:real;
a:array[0..100] of real {Co najwyzej 100 wspolczynnikow}
begin
read(n);
for i:=0 to n do read(a[i]);
writeln(' z y');
read(z);
while z <> 0 do begin
y:=a[0];
for i:=1 to n do y:=y*z+a[i];
write(' ',y:2:5); writeln;
read(z)
end
end.

informatyka +

16

Deklaracja

tablicy

Czytanie

współczynników

Instrukcja iteracyjna z
warunkiem

:

Obliczanie wartości tego
samego wielomianu tak
długo, jak długo argument
jest różny od zera, czyli z <>
0.

Zastosowania Algorytmu Hornera

1. Obliczanie wartości wielomianów.

2. Obliczanie wartości dziesiętnej liczb danych w

systemie o podstawie różnej od 10, np. liczb binarnych.

Uwaga: jest to bardzo prosta metoda, np. dla obliczeń
na kalkulatorze bez pamięci.

3. Szybkie potęgowanie (w dalszej części)

To są tylko niektóre zastosowania schematu Hornera.

informatyka +

17

System dziesiętny, system pozycyjny

Liczba dziesiętna:

357 ma wartość (dziesiętną):

357 = 3*100 + 5*10 + 7*1 = 3*10

2

+ 5*10

1

+ 7*10

0

a zatem liczba:

d

n-1

d

n-2

… d

1

d

0

która ma n cyfr

ma wartość:

d

n-1

*10

n-1

+ d

n-2

*10

n-2

+ … + d

1

*10

1

+ d

0

*10

0

10 –

podstawa systemu

{0, 1, 2, 3, …, 8, 9} – cyfry

2, 8, 16 – podstawy systemów używanych w komputerach

podstawa cyfry

2

0, 1

system binarny

8

0, 1, 2, 3, 4, 5, 6, 7

16

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

60

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, …

informatyka +

18

System binarny, przejście 2 → 10

Liczba binarna: 10101 = (10101)

2

ma wartość (dziesiętną):

1*2

4

+ 0*2

3

+ 1*2

2

+ 0*2

1

+ 1*2

0

= 2

4

+ 2

2

+ 1 = 16 + 4 + 1 =

21

a zatem liczba binarna: (b

n-1

b

n-2

… b

1

b

0

)

2

która ma n cyfr

ma wartość:

a = b

n-1

*2

n-1

+ b

n-2

*2

n-2

+ … + b

1

*2

1

+ b

0

*2

0

(*)

Jak szybko obliczać wartość dziesiętną binarnego rozwinięcia?
Wzór (*) jest wielomianem, w którym zamiast x jest 2.

A zatem wartość a obliczamy za pomocą schematu Hornera. .

informatyka +

19

Binarne
rozwinięci
e liczby a

Najbardziej
znaczący
bit

Najmniej
znaczący
bit

Otrzymywanie postaci binarnej liczb, czyli 10
→ 2

Szkolna metoda: dzielimy przez dwa
tak długo, jak długo iloraz jest
większy od zera – słupki:

dzielenie iloraz reszta

187|2 93

1

93|2 46

1

46|2 23

0

23|2 11

1

11|2 5

1

5|2 2

1

2|2 1

0

1|2 0

1

Reprezentacja od końca reszt:

187 = (10111011)

2

informatyka +

20

Program Rozwiniecie_binarne;
var a:integer;
begin
read(a);
while a <> 0 do begin
write(a mod 2,' ');
a:=a div 2
end
end.

Ciekawe pytanie: jaka jest
długość rozwinięcia binarnego
liczby n?

Bardzo prosty
program

Techniki algorytmiczne – rekurencja

Myślenie rekurencyjne:

– przykłady z życia: jedzenie, tańczenie

– Wieże Hanoi

– liczby Fibonacciego

– wyprowadzanie liczb od początku

– szybkie potęgowanie

– algorytm Euklidesa

Rekurencyjny algorytm:

Rozwiązując problem … odwołuje się do siebie

Korzyści:

Część pracy … zwalamy na komputer!

informatyka +

21

• Jedzenie kaszki z talerza – A. Jerszow

Jedz kaszkę

;

jeśli

talerz jest pusty

to

koniec jedzenia

w przeciwnym razie

weź łyżkę kaszki;

Jedz kaszkę

• Taniec

Tańcz

;

jeśli

nie gra muzyka

to

koniec tańczenia

w przeciwnym razie

zrób krok;

Tańcz

Procedura
rekurencyjna
wywołuje siebie

Warunek
początkowy
–
zatrzymuje
wywołania

Rekurencja – przykłady z życia

informatyka +

22

Opis gry i interaktywna zabawa:

Wieże Hanoi – przekładanie krążków

informatyka +

23

Zasady gry:

•przenosimy po jednym

•nigdy większy na
mniejszym

Algorytm iteracyjny:

•najmniejszy krążek ma
dwie możliwości –
ustalamy, którą
wybieramy
•na dwóch palikach,
tylko jeden krążek
można przenieść i tylko
na jedno miejsce

Hanoi (n, A, B, C) {z A na B za pomocą C}

if

n = 0

then

nic nie rób

else

begin

Hanoi (n – 1, A, C, B);
Największy krążek z A na B;
Hanoi (n – 1, C, B, A)

end

Procedura
rekurencyjna
wywołuje siebie

Warunek
początkowy
–
zatrzymuje
wywołania

Wieże Hanoi – Rekurencja

informatyka +

24

Rozwiązanie rekurencyjne:

kiedy można przenieść

największy krążek?

Odpowiedź:

gdy pozostałe będę na jednym paliku,

następnie możemy je przenieść na największy

Hanoi (n, A, B, C)

if

n = 0

then

nic nie rób

else

begin

Hanoi (n – 1, A, C, B);
Największy krążek z A na B;
Hanoi (n – 1, C, B, A)

end

h(n) =

h(n – 1) +
1 +
h(n – 1) =

h(n) = 2h(n – 1) + 1

h(0) = 0

Wieże Hanoi – Rekurencja –

liczba przestawień

h(n)

informatyka +

25

h(n) = 2h(n – 1) + 1 =

z tego samego wzoru: h(n – 1) = 2h(n – 2) + 1
stąd

h(n) = 2[2h(n – 2) + 1] + 1 =

= 2

2

h(n – 2) + 2 + 1 =

podobnie

h(n) = 2

3

 h(n – 3) + 2

2

+ 2 + 1 =

…
h(n) = 2

n

h(n – n) + 2

n - 1

+ … + 2 + 1 =

ostatecznie

h(n) = 2

n

– 1

= h(0) = 0

Wieże Hanoi – Rekurencja –

liczba przestawień

h(n)

informatyka +

26

s(n)

– liczba sposobów osiągnięcia schodka n

…

n

n–1

n–2

1

0







s(n) =

+ s(n –

2)

s(n –1)

s(1) =

s(2) =

dla n > 2

2

1

2

Chaotyczny profesor S.

Profesor S. bierze jeden
lub dwa schodki – na ile
sposobów wyjdzie na
piętro n

Myśl
rekurencyjnie!

informatyka +

27

F(n)

– liczba par królików po n miesiącach

n

n–1

n–2

1

2

F(n) =

+ F(n –

2)

F(n –

1)

F(1)=1

F(2)=1

dla n > 2:













3

Króliki, które
przeżywają

Króliki, urodzone
przez pary żyjące
ponad miesiąc

Liczby Fibonacciego:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Warunki
początkowe

Rekurencja
:

Rekurencja – króliki
Fibonacciego

informatyka +

28

Na początku jest jedna
para królików, która po
miesiącu rodzi kolejną
parę. Króliki nie umierają
i po miesiącu, co miesiąc
rodzą nową parę.

F

6

F

5

F

2

F

4

F

4

F

3

F

2

F

1

1

1

2

3

F

3

F

2

F

1

1

1

1

2

5

Powtórne
obliczanie F

4

Pamiętajmy: Rekurencja – może być
bardzo rozrzutna pod względem liczby
wykonywanych operacji i zajmowanej
pamięci

?

?

Liczby Fibonacciego – rozrzutna
rekurencja

informatyka +

29

F(n)

– liczba par królików po n miesiącach

n

n–1

n–2

1

2

= F(n)

F(n –

2)

F(n –

1)

F(1)=1

F(2)=1











3

Warunki
początkowe

Rekurencja jako iteracja dla n
> 2

F(n)

{n-ta liczba Fibonacciego obliczona iteracyjnie}

if

(n = 1)

lub

(n = 2)

then

F := 1

else

begin

a := 1; b := 1; {a i b – dwie poprzednie

wartości}

for

i := 3

to

n

do

begin

c := a + b; a := b; b := c

end

;

F := c

end



+

Liczby Fibonacciego – oszczędna
iteracja

informatyka +

30

Algorytm – drukowania cyfr liczby 3045

1. Najpierw drukuj cyfry liczby 304
2. Później drukuj cyfrę 5

Potrzebne są dwie operacje:

reszta z dzielenia

mod

: np. 3045

mod

10 = 5

dzielenie całkowite

div

: np. 3045

div

10 = 304

Liczbę 3045 drukuj w kolejności
cyfr:

5

4

0

3

Rekurencja – wyprowadzanie kolejnych cyfr
liczby

Liczba 304 to:
3045

div

10 =

304

Cyfra 5 to

reszta

:

3045

mod

10 = 5

Zauważmy: możemy
zastosować ten sam
algorytm ale do liczby
304 – REKURENCJA

informatyka +

31

KolejnaCyfra (m)

if

m < 10

then

write

(m)

else

begin

KolejnaCyfra

(m

div

10);

write

(m

mod

10)

end

Uwagi:

1. Można zastąpić 10 przez 2 i otrzymamy kolejne cyfry

binarne, od najbardziej znaczącej

2. Po zmianie kolejności poleceń – drukowanie cyfr od

końca

Warunek początkowy –
gdy liczba ma jedną
cyfrę.

Rekurencja – wyprowadzanie kolejnych cyfr
liczby

Wywołanie rekurencyjne
dla liczby bez ostatniej
cyfry

Drukowanie
ostatniej
cyfry

informatyka +

32

KolejnaCyfra (3045)

KolejnaCyfra (304)

KolejnaCyfra (30)

KolejnaCyfra (3)

write

(3045

mod

10) = 5

write

(304

mod

10) = 4

write

(30

mod

10) = 0

write

(3)

= 3

Kolejno
drukowan
e cyfry

Powrót z wywołań
rekurencyjnych

Wywołania rekurencyjne

304 = 3045 div
10

Rekurencja – wyprowadzanie kolejnych cyfr
liczby

informatyka +

33

Podnoszenie do potęgi, 1

Problem potęgowania

Dane:

m – liczba naturalna,
x – liczba rzeczywista

Wynik:

y = x

m

Przykład:

m = 22

Sposób 1

.

Rozłóż m na sumę potęg liczby 2 mamy: 22 = 2 + 4 + 16
A stąd: x

22

= x

2+4+16

= x

2

*x

4

*x

16

Kolejne mnożenia:

x

2

, x

4

= (x

2

)

2

, x

8

= (x

4

)

2

, x

16

= (x

8

)

2

, y = x

2

*x

4

= x

6

, y =

y*x

16

Liczba mnożeń:

6

(kwadrat to jedno mnożenie)

informatyka +

34

Ważne działanie w kryptografii,
gdzie potęguje się duże liczby, np.
1234567891234567890

12345678912345678

9012

Sposób 2.

(przykład dla m = 22)

 Znajdź rozwinięcie binarne liczby m;

22 = (10110)

2

 Przedstaw wykładnik w postaci schematu Hornera;

22 = 1*2

4

+ 0*2

3

+ 1*2

2

+ 1*2

1

+ 0*2

0

= (((2 + 0)2 + 1)2 + 1)2

+0

 Z postaci wykładnika określ kolejność mnożeń:

x

(((2+0)2+1)2+1)2+0

= x

(((2+0)2+1)2+1)2

= (x

(((2+0)2+1)2+1

)

2

= (x

(((2+0)2+1)2

x)

2

=

= (x

(((2+0)2+1

)

2

x)

2

= (x

(((2+0)2

x)

2

x)

2

= (x

(((2+0

)

2

x)

2

x)

2

= (((x

2

)

2

x)

2

x)

2

=

x

22

 Kolejne mnożenia:

x

2

, x

4

= (x

2

)

2

, x

5

= (x

4

)x, x

10

= (x

5

)

2

, x

10

x = x

11

, (x

11

)

2

= x

22

Liczba mnożeń:

6

, jak w Sposobie 1, ale są liczone inne iloczyny.

informatyka +

35

Podnoszenie do potęgi, 2

Podnoszenie do potęgi, 3

Algorytm rekurencyjny,

korzysta ze spostrzeżenia:

jeśli m jest parzyste, to x

m

= (x

m/2

)

2

jeśli m jest nieparzyste, to x

m

= (x

m –1

)x (m – 1 staje się

parzyste).

Przykład:

m = 22

x

22

= (x

11

)

2

= ((x

10

) x)

2

= ((x

5

)

2

x)

2

= (((x

4

)x)

2

x)

2

= (((x

2

)

2

x)

2

x)

2

= x

22

Kolejne mnożenia:

x

2

, x

4

= (x

2

)

2

, x

5

= (x

4

)x, x

10

= (x

5

)

2

, x

10

x = x

11

,

(x

11

)

2

= x

22

Liczba mnożeń:

6

, jak w Sposobie 1 i 2, liczone jak w

Sposobie 2.

informatyka +

36

Potega (x, n)

{ x

n

}

if

n = 1

then

Potega := x

else

if

n – parzyste

then

Potega := Potega (x, n/2)^2 {x

n

=

(x

n/2

)

2

}

else

Potega := Potega (x, n – 1)*x {x

n

= (x

n–

1

)x}

Realizacja
rekurencyj
na

Algorytm Euklidesa, 1

 Uważany za pierwszy algorytm – powstał 300 p.n.e.
 Chociaż Chińczycy i Hindusi wcześniej tworzyli przepisy

obliczeniowe.

 Przez długie lata był synonimem algorytmu i od niego

zaczynały wszystkie książki akademicki.

 Ma bardzo wiele zastosowań praktycznych i teoretycznych:

 arytmetyka, czyli obliczenia na liczbach całkowitych
 kryptografia – RSA
 łamigłówki

 Przykład:

Czy za pomocą naczyń 6 i 10 litrowych można

napełnić pojemnik 15 litrami wody – wodę można dolewać
lub pobierać z pojemnika tylko całymi naczyniami.

informatyka +

37

Algorytm Euklidesa, 2

Problem NWD(m,n) – Największy Wspólny Dzielnik
Dane:

m, n – liczby naturalne (można przyjąć, że m ≤ n)

Wynik: NWD(m,n)

– Największy wspólny dzielnik liczb m i n.

Przykłady:

NWD(42,14) = 14
NWD(24,16) = 8
NWD(13,21) = 1

13 i 21 są

względnie pierwsze

NWD(0,31) = 31

0 jest podzielne przez każdą liczbę

Zasada, wykorzystana w algorytmie –

Twierdzenie o ilorazie i

reszcie

n = q*m + r, gdzie 0 ≤ r < m

q – iloraz, r – reszta.

informatyka +

38

Algorytm Euklidesa, 3

Wnioski:

1.Jeśli

r = 0

, to m dzieli n, czyli NWD(m,n) = m

2.Jeśli

r ≠ 0

, to mamy r = n – qm, czyli każda liczba, która dzieli n oraz

m dzieli również r, w szczególności największa taka liczba.

Stąd mamy:

NWD(m,n) = NWD(r,m)

Przykład:

NWD(25,70)

= NWD(20,25) = NWD(5,20) = NWD(0,5) =

5

NWD(25,70):

70 = 2*25 + 20

NWD(20,25)

25 = 1*20 + 5

NWD(5,20) 20 = 4*5 + 0 r = 0, więc NWD( , ) = 5

Generowane liczby maleją: 70, 25, 20, 5, 0 więc

algorytm jest

skończony

informatyka +

39

Algorytm Euklidesa, 4 – dwie realizacje

program Euklides;
var m,n,r:integer;
begin
read(m,n);
while m>0 do begin
r:=n mod m;
n:=m;
m:=r
end;
write(n)
end.

informatyka +

40

Realizacja z funkcją:

program Euklides_funkcja;
var m,n:integer;

function NWD(m,n:integer):integer;
var r:integer;
begin
while m>0 do begin
r:=n mod m; n:=m; m:=r
end;
NWD:=n
end;

begin
read(m,n);
writeln(NWD(m,n))
end.

Funkcja

Wywołani
e funkcji
w
programi
e

Przypisanie
funkcji
wartości

Algorytm Euklidesa, 5 – realizacja
rekurencyjna

program Euklides_rekurencja;
var m,n:integer;

function NWD_rek(m,n:integer):integer;
begin
if m>n then NWD_rek:=NWD_rek(n,m)
else if m = 0 then NWD_rek:=n
else NWD_rek:=NWD_rek(n mod m,m)
end;

begin
read(m,n);
writeln(NWD_rek(m,n))
End.

informatyka +

41

Funkcja
rekurencyj
na

Wywołania
rekurencyj
ne

Reszta z
dzielenia
n przez m

Algorytm Euklidesa, 6 – zagadki

Przykład 1.

Czy za pomocą naczyń 6 i 10 litrowych można napełnić

pojemnik 15 litrami wody – wodę można dolewać lub pobierać z
pojemnika tylko całymi naczyniami.

Jeśli istnieje rozwiązanie, to istnieją takie x i y, że

6x + 10y = 15

Czy istnieją? Uzasadnij odpowiedź.

Rozwiązanie 1.

W tym przypadku nie istnieje rozwiązanie. Istnieje,

gdy prawa strona jest wielokrotnością NWD(6,10).

Przykład 2.

W jednym pojemniku są klocki o wysokości p, a w

drugim – o wysokości q. Czy zawsze można zbudować wieże z
każdego rodzaju klocków, które mają tę samą wysokość? Jeśli jest
to możliwe, to jaka jest najmniejsza wysokość takich wież?

Rozwiązanie 2.

Zawsze możliwe. Najmniejsza wysokość NWW(p,q).

Pytanie 3.

Jaki zachodzi związek między NWD(m,n) i NWW(m,n)?

Mamy NWW(m,n) = (m*n)/NWD(m,n)

informatyka +

42

Techniki algorytmiczne
– przybliżone i dokładne – idee

• W wielu sytuacjach postępujemy intuicyjnie, podejmując

decyzje

, które wydają się nam

najlepsze

, chociaż nie

potrafimy tego uzasadnić –

podejście zachłanne

• Jednak czasem musimy przejrzeć wszystkie możliwości –

dobrze jest mieć pewność, że przeglądamy (pośrednio
lub bezpośrednio) wszystkie, ale bez powtórzeń –
metoda

przeszukiwania z nawrotami

• Stara zasada – korzystać z tego, co już znamy –

strategia

dziel i zwyciężaj

• Komputery

staramy się używać wtedy, gdy bez niech nie

potrafimy sobie poradzić. A najlepiej, gdyby komputery
wykonywały za nas dużą część roboty.

Rekurencja – czyli

jak zwalić robotę na komputer

informatyka +

43

Techniki algorytmiczne
– przybliżone i dokładne

• Podejście zachłanne:

– wydawanie reszty

– zmartwienie napalonego kinomana

– pakowanie najcenniejszego plecaka

– najdłuższa droga w piramidzie

• Przeszukiwanie z nawrotami

– poszukiwanie wyjścia z labiryntu

– rozmieszczanie hetmanów na szachownicy

• Strategia dziel i zwyciężaj

– poszukiwanie elementów w zbiorze

uporządkowanym

informatyka +

44

Metoda zachłanna: wydawanie reszty –
problem

Problem Reszty.
Dane:

nominały, np. 1 gr, 2 gr, 5 gr, … K – kwota do

wydania

Wynik:

Utworzyć K z najmniejszej liczby banknotów i monet

Dyskusja:

•jak wydają sprzedawcy?
•jaki mamy pomysł?
•czy potrafimy uzasadnić, że nasz pomysł da najlepsze
rozwiązanie?

Konkluzja – algorytm zachłanny:

Wydawaj sukcesywnie, zawsze możliwie największy
nominał banknotu lub monety

informatyka +

45

Dla sprzedawcy to także
dobre kryterium – ma
mniej okazji, by się
pomylić

Metoda zachłanna: wydawanie reszty – w
arkuszu

Rozwiązanie w arkuszu –

w arkuszu można również
wykonywać algorytmy

informatyka +

46

Ćwiczenie na
warsztatach:

utworzyć

taki arkusz

Metoda zachłanna: wydawanie reszty –
program

Program Zachlanna_reszta_PL;

var i,ile,kwota_int:integer;

kwota :real;

nominal:array[1..14] of integer

=(20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1);

reszta :array[1..14] of integer;

begin

write('kwota'); read(kwota);

kwota_int:=round(kwota*100);

for i:=1 to 14 do begin

ile:=kwota_int div nominal[i];

reszta[i]:=ile;

kwota_int:=kwota_int-ile*nominal[i]

end;

for i:=1 to 8 do

writeln(nominal[i] div 100,' zl.: ',reszta[i]);

for i:=9 to 14 do

writeln(nominal[i],' gr.: ',reszta[i])

end.

informatyka +

47

Nominały w
groszach

Zamiana kwoty na
grosze

Obliczanie
wielkości kolejnych
nominałów

Metoda zachłanna: wydawanie reszty – jak
dobrze?

Pytanie:

jak dobry jest algorytm zachłanny?

Czy zawsze tworzy resztę z najmniejszej
liczby banknotów i monet?

Sytuacje:

•brakuje niektórych nominałów w kasie, np. 5 gr. i 10 gr.

•pojawia się nowa moneta, np. 21 gr.

Fakt:

Istniejące w świecie nominały, gdy tylko jest ich
dostatecznie dużo w kasie, gwarantują, że algorytm
zachłanny daje zawsze najmniejszą liczbę banknotów i
monet

informatyka +

48

Metoda zachłanna: zmartwienie kinomana

Sytuacja:
Dane:

program filmów w Multikinie na dany dzień

Wynik:

Kinoman chce jednego dnia zobaczyć jak najwięcej filmów

w Multikinie

Strategia:

Wybieraj filmy, które kończą się możliwie jak

najwcześniej

Uzasadnienie:

Pozostaje więcej czasu na następne filmy

Konkluzja:

Jest to

optymalny

algorytm.

informatyka +

49

1

2

3

4

X

X

X

X

X

X

X

Metoda zachłanna: pakowanie plecaka

Ogólny problem plecakowy
Dane:

n rzeczy (towarów, produktów itp.), w

nieograniczonej ilości:
i-ta rzecz waży w

i

jednostek i ma wartość p

i

:

W – maksymalna pojemność plecaka.

Wynik:

ilości poszczególnych rzeczy (mogą być zerowe),

których całkowita waga nie przekracza W i których
sumaryczna wartość jest największa wśród wypełnień
plecaka rzeczami o wadze nie przekraczającej W.

Decyzyjny problem plecakowy – 0-1 (zero-jedynkowy)

Rzeczy są tylko w pojedynczych ilościach – decyzja:

bierzemy albo nie

informatyka +

50

Metoda zachłanna: pakowanie plecaka

Przykład:

wartość towaru:
waga towaru:

Zachłanne kryteria wyboru rzeczy do plecaka:

1. Najcenniejsze najpierw: 7 x nr 5 + 1 x nr 4 = 7x10 + 1x7 =

77

2. Najlżejsze najpierw:

23 x nr 6 = 23x2 = 46

3. Najcenniejsze w stosunku do swojej wagi najpierw, czyli w

kolejności nierosnących wartości ilorazu p

i

/ w

i

Kolejność: 7/2, 10/3, 4/2, 2/1, 5/3, 6/6

11 x nr 4 + 1 x nr 6 = 11x7 + 1x2 =

79 NAJLEPSZE

OPTYMALNE:

10 x nr 4 + 1 x nr 4 = 10x7 + 1x10 =

80

Żadne zachłanne nie jest optymalne – na ogół tak jest

informatyka +

51

Pojemnoś
ć plecaka

Metoda zachłanna: najdłuższa droga z
piramidy

Dane:

Piramida liczb:

Wynik:

Znaleźć najdłuższą drogę z korzenia

Algorytm zachłanny.

1. Zacznij w korzeniu
2. Wybieraj większą liczbę poniżej.

informatyka +

52

3

5

7

8

2

5

4

5

7

5

3

6

3

4

2

Droga z
korzenia

Długość drogi
zachłannej:

niebieska:

3+7+5+7+4

= 26

Długość drogi
najdłuższej:

różowa:

3+5+8+5+6 =

27

Przeszukiwanie z nawrotami

Opis sytuacji:

• Duża przestrzeń możliwych rozwiązań.
• Nie znamy innej metody znalezienia rozwiązania niż

przeszukanie tej przestrzeni

• Decydujemy się przeszukać całą przestrzeń, ale

– chcemy to zrobić systematycznie

– każde rozwiązanie powinno się pojawić, bezpośrednio lub

pośrednio, ale żadne nie więcej niż raz

• Może nas interesować znalezienie wszystkich

rozwiązań

Przykłady:

• Wychodzenie z labiryntu – duża liczba możliwych dróg

• Ustawianie figur na szachownicy – duża liczba

możliwych układów

informatyka +

53

Przeszukiwanie z nawrotami:
wychodzenie z labiryntu

Opis sytuacji:
Labirynt:

pola = kwadraty, brak zamkniętych komnat

Cel:

znaleźć wyjście z dowolnego pola

Algorytm:

1. Wybieraj kierunki w kolejności:

G

(do góry),

L

(w lewo),

P

(w prawo),

D

(do dołu) – patrzymy zawsze przed siebie

2. Jeśli nie ma przejścia –

cofnij się

na pole, z którego

przyszedłeś.

informatyka +

54

Nawrót

Przeszukiwanie z nawrotami:
wychodzenie z labiryntu

Droga z pola 4a:

G-3a, G-2a, G-1a – do Góry już nie można iść,

ale można iść w Prawo

P-1b – z tego pola nie ma już przejść G, L, P –

cofamy się

B-1a – także nie ma innego przejścia – cofamy

się

B-2a – podobnie, cofamy się
B-3a – podobnie, cofamy się – z 3a można iść

jeszcze w Prawo

P-3b – istnieje przejście w Lewo
L-2b – istnieje przejście w Prawo
P-2c – istnieje przejście w Lewo

WYJŚCIE z labiryntu

informatyka +

55

Przeszukiwanie z nawrotami:
rozmieszczanie hetmanów na szachownicy

Opis sytuacji:
Szachownica:

n x n, hetman –

atakuje po wszystkich liniach

Cel:

ustawić jak największą liczbę

nie atakujących się hetmanów

Algorytm:

Poruszamy się kolumnami, od lewej

do prawej, a w kolumnach od góry.

1. Ustaw hetmana

w danej kolumnie

na nie atakowanym polu.

2. Jeśli nie można, to

cofnij się

do

poprzedniej kolumny i wybierz
następne pole

informatyka +

56

Nawrót

Przeszukiwanie z nawrotami:
rozmieszczanie hetmanów na szachownicy

informatyka +

57

a4

b2: brak pola w

c

d2 !!!

c4

b1

nawrót a: a3

c3: brak pola

w d

nawrót do b:

b1

Przeszukiwanie z nawrotami:
rozmieszczanie hetmanów na szachownicy

informatyka +

58

Drzewo
poszukiwania
ustawień:

Ustawieni
e 4
hetmanów

Oś
symetrii
drzewa

Odbicie
symetrycz
ne
rozwiązani
a

informatyka +

59

Zgadywana liczba:

17

w przedziale [1 : 20]

Metoda:

połowienia przedziału

Kolejne kroki:

strzałka wskazuje wybór;

kolor czerwony

– ciąg do przeszukania:

5 p

oró

wn

ań

zam

ias

t

20

!!!

Strategia dziel i zwyciężaj – przykład
– poszukiwanie elem. w zbiorze
uporządkowanym

Pokrewne zajęcia w Projekcie Informatyka +

Wykład+Warsztaty (Wszechnica Poranna):

• Wprowadzenie do algorytmiki i programowania – wyszukiwanie

i porządkowanie informacji

• Proste rachunki wykonywane za pomocą komputera.
• Techniki algorytmiczne – przybliżone (heurystyczne) i dokładne.

Wykłady (Wszechnica Popołudniowa):

• Czy wszystko można policzyć na komputerze?
• Porządek wśród informacji kluczem do szybkiego wyszukiwania.
• Dlaczego możemy się czuć bezpieczni w sieci, czyli o

szyfrowaniu informacji.

• Znajdowanie najkrótszych dróg, najniższych drzew, najlepszych

małżeństw

informatyka +

60

Pokrewne zajęcia w Projekcie Informatyka +

Kursy (24 godz.) – Wszechnica na Kołach:

• Algorytmy poszukiwania i porządkowania. Elementy języka

programowania

• Różnorodne algorytmy obliczeń i ich komputerowe realizacje
• Grafy, algorytmy grafowe i ich komputerowe realizacje
 

Kursy (24 godz.) – Kuźnia Informatycznych Talentów – KIT dla Orłów:

• Przegląd podstawowych algorytmów
• Struktury danych i ich wykorzystanie
• Zaawansowane algorytmy

Tendencje – Wykłady 

• Algorytmy w Internecie, K. Diks
• Czy P = NP, czyli jak wygrać milion dolarów w Sudoku, J. Grytczuk
• Między przeszłością a przyszłość informatyki, M.M Sysło

informatyka +

61