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