BAL - ćwiczenia nr 3

2 listopada 2011

Algorytmy iteracyjne (c.d.)

Algorithm 1 A3.1: Sortowanie tablic binarnych - zadanie “o fladze polskiej”

DANE WEJŚCIOWE: T (N )

(T jest N -elementową tablicą złożoną z zer i

jedynek, reprezentującą urny)
L ← 1
P ← N
dopóki L < P powtarzaj

dopóki T

L

= 0 powtarzaj

L ← L + 1

zakończ iterację
dopóki T

P

= 1 powtarzaj

P ← P − 1

zakończ iterację
jeśli L < P

zamień(T

L

, T

P

)

L ← L + 1
P ← P − 1

zakończ iterację
WYJŚCIE: T (N )

1

Algorithm 2 A3.2: Przeszukiwanie iteracyjne tablicy uporządkowanej

WE: T AB(N )- przeszukiwana tablica (uporządkowana), x - szukana wartość
L ← 1
P ← N
dopóki L ≤ P powtarzaj:

S ← [(L + P )/2]
jeśli T AB

S

= x

przerwij iterację

w p.p.

jeśli x < T AB

S

P ← S − 1

w p.p.

L ← S + 1

zakończ iterację
jeśli T AB

S

= x

WY: ”Element jest na pozycji”, S

w p.p.

WY: ”Elementu nie ma w tablicy”

Algorytmy rekurencyjne

Algorithm 3 A3.3 Przeszukiwanie rekurencyjne tablicy nieuporządkowanej

WE: T AB(N )-tablica do przeszukania, x - szukana wartość , lewy - indeks
elementu tablicy, od którego jest ona przeszukiwana

funkcja szukaj(T AB(N ), x, lewy)
jeśli lewy > N

WY: ”Elementu nie ma w tablicy”

w p.p.

jeśli T AB

lewy

= x

WY: ”Element jest na pozycji”, lewy

w p.p.

wywołaj procedurę szukaj(T AB(N ), x, lewy + 1)

zakończ funkcję

Aby przeszukać daną tablicę wywołujemy funkcję szukaj z argumentem lewy
równym 1.

Algorithm 4 A3.4 Ciąg Fibonacciego

funkcja Fib(N )
jeśli N = 0 lub N = 1

WY: N

w p.p.

WY: Fib(N -1) + Fib(N -2)

zakończ funkcję

2

Algorithm 5 A3.5 Algorytm NWD Euklidesa

funkcja NWD(m,n)
jeśli Mod(m, n) = 0

WY: n

w p.p.

WY: NWD(n, Mod(m, n))

zakończ funkcję

Algorithm 6 A3.4 Wieże Hanoi

procedura Hanoi(N, a, b)
jeśli N = 1

WY: ”Przesuń dysk z”, a, ”na”, b

w p.p.

wywołaj procedurę Hanoi(N-1, a, 3-a-b)
WY: ”Przesuń dysk z”, a, ”na”, b
wywołaj procedurę Hanoi(N-1, 3-a-b, b)

zakończ procedurę

Dla oryginalnego problemu wież Hanoi procedurę wywołujemy następująco:

Hanoi(64,0,1)

3