Instytut Informatyki
Politechnika lska
Analiza Algorytmw
Opracowal: Zbigniew Czech
materiay dydaktyczne
Gliwice, luty 1997
Spis tresci
1 Dowodzenie poprawnoci algorytmw
4
1.1 Aksjomaty arytmetyki liczb
: : : : : : : : : : : : : : : : : : : : : : :
5
1.2 Prawa rachunku zda
: : : : : : : : : : : : : : : : : : : : : : : : : : :
5
1.3 Reguy dowodzenia (wnioskowania)
: : : : : : : : : : : : : : : : : : :
6
1.4 Dowodzenie skoczono ci algorytm w
: : : : : : : : : : : : : : : : : :
9
2 Zoono obliczeniowa algorytmw
9
2.1 Obliczanie warto ci wielomianu
: : : : : : : : : : : : : : : : : : : : :
9
2.2 Mnoenie liczb cakowitych
: : : : : : : : : : : : : : : : : : : : : : : : 10
2.3 Znajdowanie maksymalnego (minimalnego) elementu
: : : : : : : : : 11
2.4 Jednoczesne znajdowanie maksymalnego i minimalnego elementu
: : : 11
2.5 Mnoenie dw ch
n-bitowych liczb dw jkowych : : : : : : : : : : : : : 12
2.6
Sortowanie przez czenie
: : : : : : : : : : : : : : : : : : : : : : 13
3 Kopce i kolejki priorytetowe
13
3.1 Procedury operujce na kopcu
: : : : : : : : : : : : : : : : : : : : : : 13
3.2 Operacje na kolejkach priorytetowych
: : : : : : : : : : : : : : : : : : 15
3.3 Sortowanie przez kopcowanie
: : : : : : : : : : : : : : : : : : : : : : : 15
4 Wyszukiwanie
17
4.1 Wyszukiwanie liniowe (proste)
: : : : : : : : : : : : : : : : : : : : : : 17
4.2 Wyszukiwanie liniowe z zastosowaniem wartownika
: : : : : : : : : : 17
4.3 Algorytm wyszukiwania liniowego realizowanego w tablicy rekord w
uporzdkowanych rosnco wedug kluczy
: : : : : : : : : : : : : : : : 18
4.4 Wyszukiwanie binarne (logarytmiczne)
: : : : : : : : : : : : : : : : : 18
4.5 Drzewa poszukiwa binarnych
: : : : : : : : : : : : : : : : : : : : : 18
4.6 Wyszukiwanie mieszajce
: : : : : : : : : : : : : : : : : : : : : : : : 23
4.6.1 Mieszanie otwarte
: : : : : : : : : : : : : : : : : : : : : : : : : 23
4.6.2 Mieszanie zamknite
: : : : : : : : : : : : : : : : : : : : : : : 25
4.7 Minimalne, doskonae funkcje mieszajce
: : : : : : : : : : : : : : : : 27
5 Operacje na tekstach
29
5.1 Wyszukiwanie naiwne"
: : : : : : : : : : : : : : : : : : : : : : : : : 29
5.2 Algorytm Knutha, Morrisa i Pratta (KMP)
: : : : : : : : : : : : : : : 30
5.3 Wyszukiwanie niezgodno ciowe
: : : : : : : : : : : : : : : : : : : : : 31
5.4 Algorytm Boyera i Moora (BM)
: : : : : : : : : : : : : : : : : : : : : 32
6 Sortowanie
33
6.1 Sortowanie przez proste wstawianie
: : : : : : : : : : : : : : : : : : : 33
6.2 Algorytm Shella, czyli sortowanie za pomoc malejcych przyrost w
: 36
6.3 Sortowanie przez proste wybieranie
: : : : : : : : : : : : : : : : : : : 37
6.4 Sortowanie przez prosta zamian
: : : : : : : : : : : : : : : : : : : : 39
6.5 Sortowanie szybkie { algorytm Quicksort
: : : : : : : : : : : : : : : : 41
6.6 Inna wersja algorytmu Quicksort
: : : : : : : : : : : : : : : : : : : : 44
2
6.7 Czasy wykonania program w sortowania
: : : : : : : : : : : : : : : : 47
7 Selekcja
47
8 Algorytmy sortowania, w ktrych korzysta si ze szczeglnych wa-
snoci kluczy
48
8.1 Sortowanie kubekowe
: : : : : : : : : : : : : : : : : : : : : : : : : : 49
8.2 Sortowanie pozycyjne
: : : : : : : : : : : : : : : : : : : : : : : : : : : 50
9 Sortowanie plikw sekwencyjnych
52
9.1 czenie proste
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52
9.2 czenie naturalne
: : : : : : : : : : : : : : : : : : : : : : : : : : : : 56
10 Algorytmy zachanne (aroczne)
59
10.1 Kolorowanie zachanne
: : : : : : : : : : : : : : : : : : : : : : : : : : 59
10.2 Problem komiwojaera
: : : : : : : : : : : : : : : : : : : : : : : : : : 59
10.3 Znajdowanie najtaszych dr g | Algorytm Dijkstry
: : : : : : : : : 60
11 Algorytmy grafowe
60
11.1 Przeszukiwanie grafu w gb
: : : : : : : : : : : : : : : : : : : : : : : 60
11.2 Przeszukiwanie grafu wszerz
: : : : : : : : : : : : : : : : : : : : : : : 62
11.3 Wyznaczanie cykli podstawowych (fundamentalnych)
: : : : : : : : : 64
11.4 Minimalne drzewa rozpinajce
: : : : : : : : : : : : : : : : : : : : : : 65
11.5 Wyznaczanie cykli Eulera
: : : : : : : : : : : : : : : : : : : : : : : : 66
12 Wyszukiwanie wyczerpujace. Algorytm z powrotami
67
13 Przeszukiwanie heurystyczne
67
13.1 Przeszukiwanie wszerz
: : : : : : : : : : : : : : : : : : : : : : : : : : 67
13.2 Przeszukiwanie w gb z iteracyjnym pogbianiem
: : : : : : : : : : 68
13.3 Przeszukiwanie wedug strategii najlepszy wierzchoek jako pierwszy" 68
14 Generowanie permutacji
69
15 Literatura
71
16 Pytania
72
17 Podzikowania
76
3
1 Dowodzenie poprawnoci algorytmw
Przed dowodem poprawno ci
f
(
n > 0)
and
(
m > 0)
g
warunek wstpny (asercja wej ciowa)
begin
iloczyn := 0
N := n
repeat
iloczyn := iloczyn + m
N := N
;
1
until
N = 0
end
f
iloczyn
=
n
m
g
warunek ostateczny (asercja wyj ciowa)
Po przeprowadzeniu dowodu
f
(
n > 0)
and
(
m > 0)
g
begin
iloczyn := 0
N := n
repeat
f
Niezmiennik: (
iloczyn + N
m = n
m)
and
(
N > 0)
g
iloczyn := iloczyn + m
N := N
;
1
f
(
iloczyn + N
m = n
m)
and
(
N
0)
g
until
N = 0
f
(
iloczyn + N
m = n
m)
and
(
N = 0)
g
end
f
iloczyn = n
m
g
Proces obliczeniowy
Instrukcje
Wyniki oblicze
Niezmiennik ptli
n = 5 m = 8
iloczyn := 0
N := n
iloczyn = 0N = 5m = 8 ( 0 + 5
8 = 40)
and
(N > 0)
iloczyn := iloczyn + m N := N
;
1 iloczyn = 8N = 4m = 8 ( 8 + 4
8 = 40)
and
(N > 0)
iloczyn := iloczyn + m N := N
;
1 iloczyn = 16N = 3m = 8 (16 + 3
8 = 40)
and
(N > 0)
iloczyn := iloczyn + m N := N
;
1 iloczyn = 24N = 2m = 8 (24 + 2
8 = 40)
and
(N > 0)
iloczyn := iloczyn + m N := N
;
1 iloczyn = 32N = 1m = 8 (32 + 1
8 = 40)
and
(N > 0)
iloczyn := iloczyn + m N := N
;
1 iloczyn = 40N = 0m = 8 (40 + 0
8 = 40)
and
(N = 0)
4
Procedura assert oraz przykad jej u ycia
procedure
assert
(
b:
Boolean
t:
string
)
if not
b
then write
(
t)
assert((n > 0)
and
(
m > 0), \not 1")
begin
iloczyn := 0
N := n
repeat
assert((iloczyn+ N
m = n
m)
and
(
N > 0), \not 2")
iloczyn := iloczyn + m
N := N
;
1
assert((iloczyn+ N
m = n
m)
and
(
N
0), \not 3")
until
N = 0
assert((iloczyn + N
m = n
m)
and
(
N = 0), \not 4")
end
assert(iloczyn = n
m, \not 5")
1.1 Aksjomaty arytmetyki liczb
Przemienno dodawania i mnoenia
x + y = y + x
x
y = y
x
czno dodawania i mnoenia
(
x + y) + z = x + (y + z)
(
x
y)
z = x
(
y
z)
Rozdzielno dodawania i odejmowania wzgldem mnoenia
x
(
y + z) = x
y + x
z
x
(
y
;
z) = x
y
;
x
z
Inne
x + 0 = x
x
0 = 0
x
1 =
x
1.2 Prawa rachunku zda
e1, e2, e3 | zdania
1. Prawa przemiennoci
(
e1
^
e2)
(
e2
^
e1)
(
e1
_
e2)
(
e2
_
e1)
(
e1
e2)
(
e2
e1)
5
2. Prawa acznoci
e1
^
(
e2
^
e3)
(
e1
^
e2)
^
e3
e1
_
(
e2
_
e3)
(
e1
_
e2)
_
e3
3. Prawa rozdzielnoci
e1
_
(
e2
^
e3)
(
e1
_
e2)
^
(
e1
_
e3)
e1
^
(
e2
_
e3)
(
e1
^
e2)
_
(
e1
^
e3)
4. Prawa De Morgana
:
(
e1
^
e2)
:
e1
_
:
e2
:
(
e1
_
e2)
:
e1
^
:
e2
5. Prawo podwjnego przeczenia
:
(
:
e1)
e1
6. Prawo wyl czonego rodka
e1
_
:
e1
true
7. Prawo zaprzeczenia
e1
^
:
e1
false
8. Prawo implikacji
e1
)
e2
:
e1
_
e2
9. Prawo rwnowanoci
(
e1
e2)
(
e1
)
e2)
^
(
e2
)
e1)
10. Prawa upraszczania alternatywy
e1
_
e1
e1
e1
_
true
true
e1
_
false
e1
e1
_
(
e1
^
e2)
e1
11. Prawa upraszczania koniunkcji
e1
^
e1
e1
e1
^
true
e1
e1
^
false
false
e1
^
(
e1
_
e2)
e1
12. Prawo identycznoci
e1
e1
1.3 Reguy dowodzenia (wnioskowania)
F
1
...F
n
G
6
F
1
:::F
n
oraz
G sa predykatami (asercjami).
Znaczenie
: Je li
F
1
...F
n
s prawdziwe (zaoenia), to mona udowodni!, e
G
jest prawdziwe (teza).
Instrukcja przypisania
f
A(x
E)
g
x := E
f
A
g
Instrukcja zloona
f
A
g
P
1
f
B
g
f
B
g
P
2
f
C
g
f
A
g
begin
P
1
P
2
end
f
C
g
Uoglniona regua dowodzenia dla instrukcji zloonej
f
A
i
;1
g
P
i
f
A
i
g
dla i = 1 ... n
f
A
0
g
begin
P
1
P
2
...
P
n
end
f
A
n
g
Reguy dowodzenia wane dla kadej instrukcji
1
:
f
A
g
P
f
B
g
B
)
C
f
A
g
P
f
C
g
2
: A
)
B
f
B
g
P
f
C
g
f
A
g
P
f
C
g
Jednoczesny zapis obu regul
A
)
B
f
B
g
P
f
C
g
C
)
D
f
A
g
P
f
D
g
Instrukcja alternatywy
f
A
^
B
g
P1
f
C
g
f
A
^
:
B
g
P2
f
C
g
f
A
g
if
B
then
P1
else
P2
end if
f
C
g
Instrukcja warunkowa
f
A
^
B
g
P
f
C
g
f
A
^
:
B
)
C
g
f
A
g
if
B
then
P
end if
f
C
g
Instrukcja iteracji \dopki"
f
A
^
B
g
P
f
A
g
f
A
g
while
B
do
P
end while
f
A
^
:
B
g
Instrukcja iteracji \powtarzaj"
f
A
g
P
f
C
g
f
C
^
:
B
)
A
g
f
A
g
repeat
P
until
B
f
C
^
B
g
Instrukcje iteracji \dla"
1.
for
x := a
to
b
do
S
end for
7
o znaczeniu
if
a
b
then
x := x
1
S
x := x
2
S
:::
x := x
n
S
end if
gdzie
x
1
=
a, x
n
=
b oraz x
i
=
succ(x
i
;1
) dla
i = 2,..., n.
2.
for
x := b
downto
a
do
S
end for
o znaczeniu
if
b
a
then
x := x
1
S
x := x
2
S
:::
x := x
n
S
end if
gdzie
x
1
=
b, x
n
=
a oraz x
i
=
pred(x
i
;1
) dla
i = 2, ..., n.
Reguy dowodzenia
f
(
a
x
b)
^
P("a :: x))
g
S
f
P("a :: x])
g
f
P(" ])
g
for
x := a
to
b
do
S
end for
f
P("a :: b])
g
f
(
a
x
b)
^
P((x :: b])
g
S
f
P("x :: b])
g
f
P(" ])
g
for
x := b
downto
a
do
S
end for
f
P("a :: b])
g
Przykad
f
Algorytm dzielenia cakowitego:
q = x
div
y.
g
f
(
x
0)
and
(
y > 0)
g
begin
q := 0
r := x
while
r
y
do
f
(
x = q
y + r)
and
(
r
0)
and
(
r
y)
g
r := r
;
y
q := 1 + q
end while
end
f
(
x = q
y + r)
and
(0
r < y)
g
8
1.4 Dowodzenie skoczono ci algorytmw
Przykad 1
f
(
n > 0)
and
(
m > 0)
g
begin
iloczyn
:= 0
N
:=
n
repeat
f
0
< N = N
0
g
iloczyn
:=
iloczyn + m
N
:=
N
;
1
f
0
N < N
0
g
until
N = 0
end
Przykad 2
f
(
x
0)
and
(
y > 0)
g
begin
q := 0
r := x
while
r
y
do
f
r > 0
g
r := r
;
y
f
r zmniejsza si pozostajc nieujemne bo r
y
g
q := 1 + q
f
r
0
g
end while
end
2 Zoono obliczeniowa algorytmw
2.1 Obliczanie warto ci wielomianu
W(x) = a
n
x
n
+
a
n
;1
x
n
;1
+
::: + a
2
x
2
+
a
1
x + a
0
Algorytm 1
: Bezpo redni (na podstawie wzoru)
begin
W := a"0]
for
i := 1
to
n
do
p := x
for
j := 1
to
i
;
1
do
p := p
x
f
Potgowanie zastpione mnoeniami.
g
end for
9
W := a"i]
p + W
end for
end
Algorytm 2
: Hornera
W(x) = (a
n
x
n
;1
+
a
n
;1
x
n
;2
+ ... +
a
2
x + a
1
)
x + a
0
=
= ((
a
n
x
n
;2
+
a
n
;1
x
n
;3
+ ... +
a
2
)
x + a
1
)
x + a
0
=
...
= ((...(
a
n
x + a
n
;1
)
x + a
n
;2
)
x + ... + a
2
)
x + a
1
)
x + a
0
begin
W := a"n]
for
i := n
;
1
downto
0
do
W := W
x + a"i]
end for
end
2.2 Mno enie liczb cakowitych
Zadanie:
Naley wymnoy! dwie liczby cakowite dodatnie:
n
m, n
m
Algorytm 1
begin
iloczyn := 0
N := n
repeat
iloczyn := iloczyn + m
N := N
;
1
until
N = 0
end
Algorytm 2
begin
iloczyn := 0
N := n
s := m
while
N > 0
do
if
odd
(
N)
then
iloczyn := iloczyn + s
end if
N := N
div
2
s := 2
s
end while
end
10
2.3 Znajdowanie maksymalnego (minimalnego) elementu
Algorytm 1
begin
Max := A"1]
i := 1
while
i < n
do
i := i + 1
if
A"i] > Max
then
Max := A"i]
end if
end while
end
Algorytm 2
(z wartownikiem)
begin
i := 1
while
i
n
do
Max := A"i]
A"n + 1] := Max
f
Ustawienie wartownika.
g
i := i + 1
while
A"i] < Max
do
i := i + 1
end while
end while
end
2.4 Jednoczesne znajdowanie maksymalnego i minimalnego
elementu
Zadanie
: Naley znale$! jednocze nie maksymalny i minimalny element w
n-elemen-
towym zbiorze
S
Algorytm 1
: Szukanie elementu maksymalnego i minimalnego oddzielnie
begin
Max := dowolny element zbioru S
for
pozostaych element w
x ze zbioru S
do
if
x > Max
then
Max := x
end if
end for
end
11
W podobny spos b mona znale$! element minimalny.
Algorytm 2
: Metoda dziel i zwyciaj" (ang. divide and conquer)
Ograniczenie
: Liczba element w zbioru
S winna by! potg liczby 2, tj. n = 2
k
dla
pewnego
k.
procedure
MaxMin
(
S)
begin
if
#
S = 2
then
Niech
S =
f
a b
g
f
a | element maksymalny
b | element minimalny.
g
return
(
MAX
(
a b)
MIN
(
a b))
else
Podzieli!
S na dwa r wne podzbiory S1 i S2
(
max1 min1) :=
MaxMin
(
S1)
(
max2 min2) :=
MaxMin
(
S2)
return
(
MAX
(
max1 max2)
MIN
(
min1 min2))
end if
end
2.5 Mno enie dwch
n
-bitowych liczb dwjkowych
function
mult(x y n: integer):
integer
f
x oraz y s liczbami cakowitymi ze znakiem (x y
2
n
).
n jest poteg liczby 2. Wartosci funkcji jest x
y.
g
s:
integer
f
s przechowuje znak x
y.
g
m1, m2, m3:
integer
f
Warto ci iloczyn w cze ciowych.
g
a, b, c, d:
integer
f
Lewe i prawe po wki
x i y.
g
begin
s :=
sign
(
x)
sign
(
y)
x :=
abs
(
x)
y :=
abs
(
y)
f
Uczynienie
x i y dodatnimi.
g
if
n = 1
then
if
(
x = 1)
and
(
y = 1)
then
return
(1)
else
return
(0)
end if
else
a := bardziej znaczce
n
2
bit w
x
b := mniej znaczce
n
2
bit w
x
c := bardziej znaczce
n
2
bit w
y
d := mniej znaczce
n
2
bit w
y
m1 :=
mult
(
a c
n
2
)
12
m2 :=
mult
(
a
;
b d
;
c
n
2
)
m3 :=
mult
(
b d
n
2
)
return
(
s
(
m1
2
n
+ (
m1 + m2 + m3)
2
n
2
+
m3))
end if
end
f
mult
g
2.6 Sortowanie przez czenie
procedure
SORT
(
i j:
integer
)
begin
if
i = j
then
return
(
x
i
)
else
m := (i + j
;
1)
= 2
return
(
CZENIE
(
SORT
(
i m)
SORT
(
m + 1 j)))
end if
end
3 Kopce i kolejki priorytetowe
3.1 Procedury operujce na kopcu
procedure
przemie w gr
(
p:
integer
)
f
Element
A"p] przemieszczany jest w g r kopca.
Warunek wstpny:
kopiec(1 p
;
1) i
p > 0.
Warunek ostateczny:
kopiec(1 p).
g
var
d r:
integer
f
d | dziecko, r | rodzic
g
begin
d := p
loop
f
Niezmiennik:
kopiec
(1
p) z wyjtkiem by! moe
relacji pomidzy
A"d] i jego rodzicem. 1
d
p.
g
if
d = 1
then
break
end if
r := d
div
2
if
A"r]
A"d]
then
break
end if
zamiana(A"r] A"d])
d := r
end loop
end
f
przemie w gre
g
Procedura
przemie w gr
z uyciem wartownika
13
procedure
przemie w gr
(
p:
integer
)
var
d:
integer
x: ...
f
Typ zgodny z typem
A.
g
begin
x := A"p]
A"0] := x
f
Ustawienie wartownika.
g
d := p
loop
r := d
div
2
if
A"r]
x
then
break
end if
A"d] := A"r]
d := r
end loop
A"d] := x
end
f
przemie w gr
g
procedure
przemie w d
(
p:
integer
)
f
Element
A"1] przemieszczany jest w d kopca.
Warunek wstpny:
kopiec
(2
p) i p
0.
Warunek ostateczny:
kopiec
(1
p).
g
var
d r:
integer
begin
r := 1
loop
f
Niezmiennik:
kopiec
(1
p) z wyjtkiem by! moe relacji
pomidzy
A"r] i jego dzie!mi. 1
r
p.
g
d := 2
r
if
d > p
then
break
end if
f
d jest dzieckiem lewym r
g
if
(
d + 1
p)
cand
(
A"d + 1] < A"d])
then
d := d + 1
end if
f
d jest najmniejszym dzieckiem r
g
if
A"r]
A"d]
then
break
end if
zamiana(A"r] A"d])
r := d
end loop
end
f
przemie w d
g
14
3.2 Operacje na kolejkach priorytetowych
1. Uczynienie kolejki pust
n := 0
2. Operacja
wstaw
procedure
wstaw(t)
begin
if
n
n max
then
bd
else
n := n + 1
A"n] := t
f
kopiec
(1
n
;
1)
g
przemie w gr
(
n)
f
kopiec
(1
n)
g
end if
end
f
wstaw
g
3. Operacja
usu min
procedure
usu min
(
t)
begin
if
n < 1
then
bd
else
t := A"1]
A"1] := A"n]
n := n
;
1
f
kopiec
(2
n)
g
przemie w d
(
n)
f
kopiec
(1
n)
g
end if
end
f
usu min
g
3.3 Sortowanie przez kopcowanie
type
typ rekordowy =
record
klucz:
typ klucza
f
Typ skalarny.
g
f
Pozostae skadowe rekordu.
g
end
var
A:
array
"1
:: n]
of
typ rekordowy
f
Sortowana tablica.
g
15
Zmody kowana procedura przemie w d
procedure
przemie w d
(
l p:
integer
)
f
Element
A"l] przemieszczany jest w d kopca.
Warunek wstpny:
kopiec
(
l + 1 p) i l
p.
Warunek ostateczny:
kopiec
(
l p).
g
var
d r:
integer
t:
typ rekordowy
begin
r := l t := A"r]
loop
f
Niezmiennik:
kopiec
(
l p) z wyjtkiem by! moe relacji
pomidzy
r i jego dzie!mi. l
r
p.
g
d := 2
r
if
d > p
then
break
end if
f
d jest dzieckiem lewym r.
g
if
(
d < p)
cand
(
A"d + 1]:klucz > A"d]:klucz)
then
d := d + 1
end if
f
d jest najwikszym dzieckiem r.
g
if
t:klucz
A"d]:klucz
then
break
end if
A"r] := A"d]
r := d
end loop
A"r] := t
end
f
przemie w d
g
procedure
sortowanie przez kopcowanie
f
Sortowana jest tablica
A"1 :: n].
g
var
i:
integer
begin
f
Faza 1: Budowanie kopca.
g
for
i := n
div
2
downto
1
do
f
Niezmiennik:
kopiec
(
i + 1 n).
g
przemie w d
(
i n)
f
kopiec
(
i n).
g
end for
f
kopiec
(1
n).
g
f
Faza 2: Wa ciwe sortowanie.
g
for
i := n
downto
2
do
f
Niezmiennik:
kopiec
(1
i) i posortowane(i + 1 n)
16
i
A"1 :: i]:klucz
A"i + 1 :: n]:klucz.
g
zamiana(A"1] A"i])
f
kopiec
(2
i
;
1) i
posortowane(i n)
i
A"1 :: i
;
1]
:klucz
A"i :: n]:klucz.
g
przemie w d
(1
i
;
1)
f
kopiec
(1
i
;
1) i
posortowane(i n)
i
A"1 :: i
;
1]
:klucz
A"i :: n]:klucz.
g
end for
f
posortowane(1 n)
g
end
f
sortowanie przez kopcowanie
g
&
4 Wyszukiwanie
4.1 Wyszukiwanie liniowe (proste)
procedure
wyszukiwanie liniowe 1(x: typ klucza
var
jest:
Boolean
var
i: 1 :: n + 1)
begin
i := 1
while
(
i
n)
cand
(
A"i]:klucz <> x)
do
i := i + 1
end while
jest := i <> (n + 1)
end
4.2 Wyszukiwanie liniowe z zastosowaniem wartownika
procedure
wyszukiwanie liniowe 2(x: typ klucza
var
jest:
Boolean
var
i: 1 :: n + 1)
begin
A"n + 1]:klucz := x
f
Wartownik.
g
i := 1
while
A"i]:klucz <> x
do
i := i + 1
end while
jest := i <> (n + 1)
end
17
4.3 Algorytm wyszukiwania liniowego realizowanego w ta-
blicy rekordw uporzdkowanych rosnco wedug klu-
czy
procedure
wyszukiwanie liniowe 3(x: typ klucza
var
jest:
Boolean
var
i: 1 :: n + 1)
begin
i := 1
A"n + 1]:klucz :=
1
f1
> x
g
while
A"i]:klucz < x
do
i := i + 1
end while
jest := A"i]:klucz = x
end
4.4 Wyszukiwanie binarne (logarytmiczne)
procedure
wyszukiwanie binarne(x: typ klucza
var
jest:
Boolean
var
m: 1 :: n)
var
lewy prawy: 0 :: n + 1
begin
lewy := 1
prawy := n
jest :=
false
repeat
m := (lewy + prawy)
div
2
if
A"m]:klucz = x
then
jest :=
true
else
if
A"m]:klucz < x
then
lewy := m + 1
else
prawy := m
;
1
end if
end if
until
jest
or
(
lewy > prawy)
end
f
wyszukiwanie binarne
g
4.5 Drzewa poszukiwa binarnych
type
wierzchoek drzewa
=
record
klucz: typ klucza
18
lewy prawy: ^
wierzchoek drzewa
end
odsyacz
= ^
wierzchoek drzewa
procedure
szukaj
(
x:
klucz
var
t:
odsyacz
)
f
Szukanie klucza
x w drzewie wskazanym przez t.
g
var
v:
odsyacz
begin
v := t
while
(
v
6
=
nil
)
cand
(
v^.
klucz
6
=
x)
do
if
x < v^.
klucz
then
v := v^.
lewy
else
v := v^.
prawy
end if
end while
return
(
v)
f
je li
v =
nil
to
x nie wystpuje w drzewie
g
end
f
szukaj
g
procedure
wstaw
(
x:
klucz
var
t:
odsyacz
)
f
Wstawianie klucza
x do drzewa wskazanego przez t.
g
var
v:
odsyacz
begin
v := t
while
(
v
6
=
nil
)
cand
(
v^.
klucz
6
=
x)
do
f
szukania klucza
x
g
if
x < v^.
klucz
then
v := v^.
lewy
else
v := v^.
prawy
end if
end while
if
v
6
=
nil then
f
x jest w drzewie
g
return
else
Wstawienie
x na koniec cieki
end if
end
f
wstaw
g
procedure
usu
(
x:
klucz
var
t:
odsyacz
)
f
Usuwanie klucza
x z drzewa wskazanego przez t.
g
var
v w:
odsyacz
begin
v := t
while
(
v
6
=
nil
)
cand
(
v^.
klucz
6
=
x)
do
f
szukania klucza
x
g
19
if
x < v^.
klucz
then
v := v^.
lewy
else
v := v^.
prawy
end if
end while
if
v =
nil then
f
x nie wystpuje w drzewie
g
return
else
if
(
v^:
lewy
=
nil
)
or
(
v^:
prawy
=
nil
)
then
f
brak lewego lub prawego poddrzewa
g
Usu wierzchoek
v^ z drzewa
else
w := v^:
prawy
while
w^ nie jest kocem cieki w drzewie
do
w := w^:
lewy
f
szukanie minimalnego elementu w prawym poddrzewie
g
end while
Wstaw
w^:
klucz
do
v^:
klucz
i usu wierzchoek
w^ z drzewa
end if
end if
end
usu
Analiza wyszukiwania w drzewach binarnych
Wyznaczymy redni liczb por wna wymaganych dla wyszukania klucza w drze-
wie wyszukiwa binarnych. Zakadamy, e:
1. Dane jest
n r nych kluczy o warto ciach 12:::n.
2. Klucze pojawiaj si w losowej kolejno ci.
3. Pierwszy klucz (a wic korze tworzonego drzewa) ma warto !
i z prawdopodo-
biestwem 1
=n. W wczas lewe poddrzewo bdzie zawiera! i
;
1 wierzchok w,
a prawe poddrzewo
n
;
i wierzchok w.
Oznaczmy:
P
i
;1
| rednia liczba por wna konieczna do wyszukania dowolnego klucza w
lewym poddrzewie.
P
n
;
i
| ta sama wielko ! dla prawego poddrzewa.
P
(
i
)
n
| rednia liczba por wna wymagana dla wyszukania klucza w drzewie o
n wierzchokach i o korzeniu i.
Wobec tego
P
(
i
)
n
= (
P
i
;1
+ 1)
p
i
;1
+ 1
p
i
+ (
P
n
;
i
+ 1)
p
n
;
i
20
gdzie
p
i
;1
,
p
i
i
p
n
;
i
to prawdopodobiestwa, e bdziemy szuka! odpowiednio klucza
w lewym poddrzewie, klucza
i-tego, oraz klucza w prawym poddrzewie. Zakadajc,
e prawdopodobiestwa szukania poszczeg lnych kluczy s r wne, otrzymujemy:
p
i
;1
= i
;
1
n p
i
= 1n p
n
;
i
= n
;
i
n :
Wobec tego
P
(
i
)
n
= (
P
i
;1
+ 1)i
;
1
n + 1
1
n + (P
n
;
i
+ 1)n
;
i
n =
= 1n "(P
i
;1
+ 1)(
i
;
1) + 1 + (
P
n
;
i
+ 1)(
n
;
i)]:
Wielko !
P
(
i
)
n
jest wana tylko dla drzewa o korzeniu
i. Naley j u redni!, tj.
uwzgldni! przypadek, e dowolny klucz moe wystpi! w korzeniu. Oznaczmy t
u rednion warto ! przez
P
n
. W wczas
P
n
= 1n
n
X
i
=1
P
(
i
)
n
= 1n
n
X
i
=1
1
n "(P
i
;1
+ 1)(
i
;
1) + 1 + (
P
n
;
i
+ 1)(
n
;
i)]
= 1n
2
n
X
i
=1
"
P
i
;1
(
i
;
1) +
i
;
1 + 1 +
P
n
;
i
(
n
;
i) + n
;
i]
= 1 + 1n
2
n
X
i
=1
"
P
i
;1
(
i
;
1) +
P
n
;
i
(
n
;
i)]:
Mamy
X
1
i
n
P
i
;1
(
i
;
1) =
X
0
i
+1
n
P
i
+1;1
(
i + 1
;
1) =
X
0
i
n
;1
P
i
i
X
1
i
n
P
n
;
i
(
n
;
i) =
X
1
n
;
i
n
P
n
;
n
+
i
(
n
;
n + i) =
X
0
i
n
;1
P
i
i
a wic
P
n
= 1 + 2n
2
n
;1
X
i
=0
i
P
i
:
Mnoc obie strony r wnania przez
n
2
otrzymujemy
n
2
P
n
=
n
2
+ 2
n
;1
X
i
=0
i
P
i
:
(1)
To samo r wnanie dla
n
;
1
(
n
;
1)
2
P
n
;1
= (
n
;
1)
2
+ 2
n
;2
X
i
=0
i
P
i
:
(2)
21
Odejmujc stronami (1) i (2) otrzymujemy
n
2
P
n
;
(
n
;
1)
2
P
n
;1
=
n
2
;
(
n
;
1)
2
+ 2(
n
;
1)
P
n
;1
n
2
P
n
=
P
n
;1
((
n
;
1)
2
+ 2(
n
;
1)) + (
n
2
;
n
2
+ 2
n
;
1)
n
2
P
n
=
P
n
;1
(
n
;
1)(
n + 1) + (2n
;
1)
(3)
Zastosujemy
metod czynnika sumacyjnego
"11, str. 41] (ang. summation factor me-
thod), kt ra m wi, e rozwizaniem r wnania rekurencyjnego o postaci
a
n
T
n
=
b
n
T
n
;1
+
c
n
gdzie
a
i
b
i
6
= 0 dla
i = 1...n, jest
T
n
= 1
a
n
s
n
(
s
1
b
1
T
0
+
n
X
k
=1
s
k
c
k
)
gdzie
s
n
to wa nie
czynnik sumacyjny
o warto ci
s
n
= a
n
;1
a
n
;2
...
a
1
b
n
b
n
;1
...
b
2
:
R wnanie (3) ma posta!
n
2
P
n
= (
n + 1)(n
;
1)
P
n
;1
+ (2
n
;
1)
a wic
a
n
=
n
2
b
n
= (
n + 1)(n
;
1)
c
n
= 2
n
;
1. Wyliczmy warto !
s
n
:
s
n
= a
n
;1
a
n
;2
...
a
1
b
n
b
n
;1
...
b
2
=
(
n
;
1)
2
(
n
;
2)
2
(
n
;
3)
2
...
3
2
2
2
1
2
(
n + 1)(n
;
1)
n(n
;
2)
(
n
;
1)(
n
;
3)
...
4
2
3
1
a
n
;1
a
n
;2
...
a
1
= (
n
;
1)
2
(
n
;
2)
2
...
3
2
2
2
1
2
= (
n
;
1)!
(
n
;
1)!
b
n
...
b
2
= (
n+1)(n
;
1)
n(n
;
2)
(
n
;
1)(
n
;
3)
(
n
;
2)(
n
;
4)
...
5
3
4
2
3
1
Warto ! iloczynu
b
n
b
n
;2
...
b
2
jest (
n+1)!=2, a warto ! iloczynu b
n
;1
b
n
;3
...
b
1
jest (
n
;
1)!. Wobec tego otrzymujemy
s
n
= (n
;
1)!
(
n
;
1)!
(
n
+1)!
2
(
n
;
1)! =
2
n(n + 1):
Poniewa
P
0
= 0, to
P
n
= 1
s
n
a
n
n
X
k
=1
s
k
c
k
=
1
2
n
(
n
+1)
n
2
n
X
k
=1
2
k(k + 1)(2k
;
1) = n + 1
n
n
X
k
=1
2
k
;
1
k(k + 1):
Rozkadajc wyraenie
2
k
;1
k
(
k
+1)
na uamki proste otrzymujemy
2
k
;
1
k(k + 1) =
3
k + 1
;
1
k:
22
Wobec tego
P
n
= n + 1
n
3
n
X
k
=1
1
k + 1
;
n
X
k
=1
1
k
!
= n + 1
n
3 1
n + 1
;
3 + 3
n
X
k
=1
1
k
;
n
X
k
=1
1
k
!
=
= n + 1
n
3(1
;
n
;
1)
n + 1 + 2
n
X
k
=1
1
k
!
= 2n + 1
n H
n
;
3
:
4.6 Wyszukiwanie mieszajce
4.6.1 Mieszanie otwarte
const
a =
f
Odpowiednia staa.
g
type
sowo
=
array
"1
:: 10]
of
char
element listy =
record
r:
sowo
nast: ^element listy
end
typ listowy = ^element listy
sownik
=
array
"0
:: a
;
1]
of
typ listowy
Funkcja mieszaj
ca
function
h(x:
sowo
): 0
:: a
;
1
var
i suma:
integer
begin
suma := 0
for
i := 1
to
10
do
suma := suma +
ord
(
x"i])
end for
return
(
suma
mod
a)
end
Procedury operuj
ce na sowniku
procedure
ZERUJ
(
var
A:
sownik
)
var
i:
integer
begin
for
i := 0
to
a
;
1
do
A"i] :=
nil
end for
end
function
JEST
(
x:
sowo
var
A:
sownik
):
Boolean
var
bie cy
:
typ listowy
begin
23
bie cy
:=
A"h(x)]
while
bie cy
<>
nil do
if
bie cy
^
:r = x
then
return
(
true
)
f
Sowo znaleziono.
g
else
bie cy
:=
bie cy
^
:nast
end
end while
return
(
false
)
f
Sowa nie znaleziono.
g
end
procedure
WSTAW
(
x:
sowo
var
A:
sownik
)
var
kubeek
: 0
:: a
;
1
stara gow
a:
typ listowy
begin
if not
JEST
(
x A)
then
kubeek
:=
h(x)
stara gowa
:=
A"
kubeek
]
new
(
A"
kubeek
])
A"
kubeek
]^
:r := x
A"
kubeek
]^
:nast :=
stara gowa
end if
end
procedure
USU
(
x:
sowo
var
A:
sownik
)
var
bie cy
:
typ listowy
kubeek
: 0
:: a
;
1
begin
kubeek
:=
h(x)
if
A"
kubeek
]
<>
nil then
if
A"
kubeek
]^
:r = x
then
f
Sowo
x jest w pierwszym elemencie.
g
A"
kubeek
] :=
A"
kubeek
]^
:nast
f
Usunicie sowa
z listy.
g
else
f
Sowo
x, je li wystpuje, nie jest zawarte
w pierwszym elemencie.
g
bie cy
:=
A"
kubeek
]
f
Zmienna
bie cy
wskazuje
na poprzedni element.
g
while
bie cy
^
:nast <>
nil do
if
bie cy
^
:nast^:r = x
then
f
Usunicie sowa z listy.
g
bie cy
^
:nast :=
bie cy
^
:nast^:nast
return
f
Wyj cie z procedury.
g
else
24
f
Sowa
x jeszcze nie znaleziono.
g
bie cy := bie cy
^
:nast
end if
end while
end if
end if
end
Rozkad kluczy w tablicy
i
A0
i + 1 A1
i + 2 A2
i + 3 A3
i + 4 A4
i + 5 A5
i + 6 A6
i + 7 A7
i + 8 A8
i + 9 A9
...
...
j
A10
j + 1 A11 A20
j + 2 A12 A21 A30
j + 3 A13 A22 A31 A40
j + 4 A14 A23 A32 A41 A50
j + 5 A15 A24 A33 A42 A51 A60
j + 6 A16 A25 A34 A43 A52 A61 A70
j + 7 A17 A26 A35 A44 A53 A62 A71 A80
j + 8 A18 A27 A36 A45 A54 A63 A72 A81 A90
j + 9 A19 A28 A37 A46 A55 A64 A73 A82 A91
j + 10
A29 A38 A47 A56 A65 A74 A83 A92
j + 11
A39 A48 A57 A66 A75 A84 A93
j + 12
A49 A58 A67 A76 A85 A94
j + 13
A59 A68 A77 A86 A95
j + 14
A69 A78 A87 A96
j + 15
A79 A88 A97
j + 16
A89 A98
j + 17
A99
4.6.2 Mieszanie zamknite
const
puste =
0
0
f
10 odstp w
g
25
usunite
= '
'
f
10 gwiazdek
g
type
sowo
=
packed array
"1
:: 10]
of
char
sownik
=
array
"0
:: a
;
1]
of
sowo
procedure
ZERUJ
(
var
A:
sownik
)
var
i:
integer
begin
for
i := 0
to
a
;
1
do
A"i] := puste
end for
end
function
szukaj
(
x:
sowo
var
A:
sownik
):
integer
f
Przeszukiwana jest tablica
A poczynajc od kubeka
h0(x) do momentu, gdy x zostaje znalezione albo
zostaje znaleziony kubeek pusty albo te caa tablica
zostanie przeszukana. Warto ci funkcji jest numer
kubeka, na kt rym szukanie zostaje zakoczone,
wskutek jednego z wymienionych wyej powod w.
g
var
pocz i:
integer
f
Zmienna
pocz przechowuje warto ! h0(x)
zmienna
i zawiera liczb dotychczas przeszukanych
kubek w.
g
begin
pocz := h0(x)
i := 0
while
(
i < a)
and
(
A"(pocz + i)
mod
a] <> x)
and
(
A"(pocz + i)
mod
a] <> puste)
do
i := i + 1
end while
return
((
pocz + i)
mod
a)
end
function
szukaj 1
(
x:
sowo
var
A:
sownik
):
integer
f
Dziaanie podobne do funkcji
szukaj, z t r nic,
e przeszukiwanie tablicy
A zostaje take zakoczone
po napotkaniu kubeka z warto ci
usunite
.
g
function
JEST
(
x:
sowo
var
A:
sownik
):
Boolean
begin
if
A"szukaj(x A)] = x
then
return
(
true
)
else
return
(
false
)
end if
26
end
procedure
WSTAW
(
x:
sowo
var
A:
sownik
)
var
kubeek
: 0
:: a
;
1
begin
if
A"szukaj(x A)] = x
then
return
f
x jest w tablicy.
g
end if
kubeek
:=
szukaj 1(x A)
if
(
A"
kubeek
] = puste)
or
(
A"
kubeek
] =
usunite
)
then
A"
kubeek
] :=
x
else
bd
('bd w procedurze
WSTAW
: tablica jest pena')
end if
end
procedure
USU
(
x:
sowo
var
A:
sownik
)
var
kubeek
: 0 ..
a
;
1
begin
kubeek
:=
szukaj
(
x A)
if
A"
kubeek
] =
x
then
A"
kubeek
] :=
usunite
end if
end
4.7 Minimalne, doskonae funkcje mieszajce
1.
Niech dany bdzie zbi r skr t w angielskich nazw miesicy
W
=
f
JUN, SEP, DEC,
AUG, JAN, FEB, JUL, APR, OCT, MAY, MAR, NOV
g
Warto ci liczbowe przyporzdkowane poszczeg lnym literom:
A B C D E F G H I J K L M N O P Q R
4 5 2 0 0 0 3 0 0 0 0 6 0 0 5 1 0 6
S T U V W X Y Z
0 6 0 6 0 0 5 0
Jeeli nazw kadego miesica uwaa! za cig trzech liter
x
1
x
2
x
3
, to minimalna, do-
skonaa funkcja mieszajca ma posta!:
h
d
(
x
1
x
2
x
3
) = liczba przyporzdkowana literze
x
2
+
liczba przyporzdkowana literze
x
3
27
h
d
(
JUN) = 0
h
d
(
SEP) = 1
h
d
(
DEC) = 2
:::
h
d
(
NOV ) = 11
2.
Niech dany bdzie zbi r s w zastrzeonych jzyka Pascal
W
=
f
DO, END, ELSE,
CASE, DOWNTO, GOTO, TO, OTHERWISE,TYPE, WHILE, CONST, DIV, AND,
SET, OR, OF, MOD, FILE, RECORD, PACKED, NOT, THEN, PROCEDURE,
WITH, REPEAT, VAR, IN, ARRAY, IF, NIL, FOR, BEGIN, UNTIL, LABEL,
FUNCTION, PROGRAM
g
,
card(W) = 36.
Warto ci liczbowe przyporzdkowane poszczeg lnym literom:
A B C D E F G H I J K L M N O P Q R
11 15 1 0 0 15 3 15 13 0 0 15 15 13 0 15 0 14
S T U V W X Y Z
6 6 14 10 6 0 13 0
h
d
(
x
1
x
2
::: x
n
) = dugo ! sowa
n +
liczba przyporzdkowana literze
x
1
+
liczba przyporzdkowana literze
x
n
Np.:
h
d
(DO) = 2 + 0 + 0 = 2
h
d
(PROGRAM) = 7 + 15 + 15 = 37
Warto ci
h
d
dla s w DO..PROGRAM s z zakresu 2..37. Funkcja jest wic doskonaa
ale nie minimalna.
3.
Minimalna, doskonaa funkcja mieszajca dla s w zastrzeonych jzyka Pascal
6000
sowa:
var
w :
array
"1
:: N]
of char
f
W =
f
w
1
w
2
...w
N
gg
h
d
(
w) = (h
0
(
w) + g
h
1
(
w) + g
h
2
(
w))
mod
N
N = card(W)
h
0
(
w) = dugo !(w) + (* ord (w"i]), i := 1 do dugo !(w)
z krokiem 3)
h
1
(
w) = (* ord (w"i]), i := 1 do dugo !(w) z krokiem 2)
mod
16
h
2
(
w) = ((* ord (w"i]), i := 2 do dugo !(w) z krokiem 2)
mod
16) + 16
g | funkcja zadana przy pomocy tablicy
28
Przyjto kod EBCDIC:
ord
('A') = 193,
ord
('B') = 194, ... ,
ord
('I') = 201
ord
('J') = 209,
ord
('K') = 210, ... ,
ord
('R') = 217
ord
('S') = 226,
ord
('T') = 227, ... ,
ord
('Z') = 233
Zbi r s w zastrzeonych jzyka Pascal 6000 (
card
(
W
) = 36):
W =
f
AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO, ELSE, END,
FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NIL, NOT, OF,
OR, PACKED, PROCEDURE, PROGRAM, RECORD, REPEAT, SEGMENTED,
SET, THEN, TO, TYPE, UNTIL, VAR, WHILE, WITH
g
i g(i) i g(i) i g(i) i g(i)
0 0 9 12 18 0 27 28
1 0 10 16 19 30 28 28
2 0 11 22 20 0 29 3
3 31 12 0 21 24 30 26
4 12 13 16 22 25 31 30
5 12 14 16 23 35
6 15 15 11 24 15
7 33 16 0 25 27
8 11 17 29 26 3
h
d
(NOT) = 0
h
d
(MOD) = 35
5 Operacje na tekstach
tekst:
array
"1
:: n]
of
char
wzorzec:
array
"1
:: m]
of
char
f
Zwykle zachodzi 1
m
n.
g
5.1 Wyszukiwanie naiwne"
function
wyszukiwanie naiwne:
integer
var
i j:
integer
begin
i := 1
j := 1
repeat
if
tekst"i] = wzorzec"j]
then
29
i := i + 1
j := j + 1
else
i := i
;
j + 2
j := 1
end if
until
(
j > m)
or
(
i > n)
if
j > m
then
return
(
i
;
m)
else
return
(
i)
f
Wzorca nie znaleziono (
i = n + 1).
g
end if
end
5.2 Algorytm Knutha, Morrisa i Pratta (KMP)
function
wyszukiwanie KMP
:
integer
var
i j:
integer
begin
i := 1
j := 1
repeat
if
(
j = 0)
cor
(
tekst"i] = wzorzec"j])
then
i := i + 1
j := j + 1
else
j := nast"j]
end if
until
(
j > m)
or
(
i > n)
if
j > m
then
return
(
i
;
m)
else
return
(
i)
end if
end
procedure
inicjacja nast
var
i j:
integer
begin
i := 1
j := 0
nast"1] := 0
repeat
if
(
j = 0)
or
(
wzorzec"i] = wzorzec"j])
then
i := i + 1
30
j := j + 1
nast"i] := j
else
j := nast"j]
end if
until
i > m
end
Algorytm wyszukiwania KMP z
wbudowanym
wzorcem 10100111
i := 0
0:
i := i + 1
1:
if
tekst"i] <> '1'
then goto
0
i := i + 1
2:
if
tekst"i] <> '0'
then goto
1
i := i + 1
3:
if
tekst"i] <> '1'
then goto
1
i := i + 1
4:
if
tekst"i] <> '0'
then goto
2
i := i + 1
5:
if
tekst"i] <> '0'
then goto
3
i := i + 1
6:
if
tekst"i] <> '1'
then goto
1
i := i + 1
7:
if
tekst"i] <> '1'
then goto
2
i := i + 1
8:
if
tekst"i] <> '1'
then goto
2
i := i + 1
if
i > n + 1
then
return
(
n + 1)
else
return
(
i
;
8)
end if
5.3 Wyszukiwanie niezgodno ciowe
type
znak = (' ', 'A', 'B', ... , 'Z')
var
skok1:
array
"
znak]
of
integer
function
wyszukiwanie niezgodnociowe
:
integer
var
i, j:
integer
begin
i := m
j := m
repeat
if
tekst"i] = wzorzec"j]
then
i := i
;
1
j := j
;
1
else
i := i + skok1"tekst"i]]
j := m
end if
until
(
j < 1)
or
(
i > n)
31
if
j < 1
then
return
(
i + 1)
else
return
(
n + 1)
end if
end
procedure
inicjacja skok1
var
j: znak
k:
integer
begin
for
j := ' '
to
'Z'
do
skok1"j] := m
end for
for
k := 1
to
m
do
skok1"wzorzec"k]] := m
;
k
end for
end
Mody kacja ptli
repeat
w algorytmie wyszukiwania niezgodnociowego
repeat
if
tekst"i] = wzorzec"j]
then
i := i
;
1
j := j
;
1
else
i := i + max(skok1"tekst"i]] skok2"j])
j := m
end if
until
(
j < 1)
or
(
i > n)
5.4 Algorytm Boyera i Moora (BM)
procedure
wyszukiwanie BM
var
du y
:
integer
:=
n + m
f
Og lnie winno zachodzi!:
duy
n + m.
g
i, j, k:
integer
begin
f
m
n
g
i := m
loop
repeat
i := i + skok1"tekst"i]]
until
i > n
if
i
du y
then
32
return
(
n + 1)
f
Wzorca nie znaleziono.
g
end if
f
Zachodzi:
tekst"i
;
du y
] =
wzorzec"m].
g
i := (i
;
du y
)
;
1
j := m
;
1
loop
if
j = 0
then
return
(
i + 1)
f
Wzorzec znaleziono.
g
end if
if
tekst"i] = wzorzec"j]
then
i := i
;
1
j := j
;
1
else
break
end if
end loop
k := skok1"tekst"i]]
if
k =
du y
then
i := i + skok2"j]
else
i := i + max(k skok2"j])
end if
end loop
end
6 Sortowanie
type
typ rekordu
=
record
klucz
:
typ klucza
f
W zbiorze warto ci typu
typ klucza
musi by!
zde+niowana relacja liniowego porzdku.
g
end
indeks
= 0 ..
n
var
A
:
array
"1 ..
n
]
of
typ rekordu
f
Tablica podlegajca sortowaniu.
g
6.1 Sortowanie przez proste wstawianie
33
klucze pocztkowe 44 55 12 42 94 18 06 67
i = 2
44 55 12 42 94 18 06 67
i = 3
12 44 55 42 94 18 06 67
i = 4
12 42 44 55 94 18 06 67
i = 5
12 42 44 55 94 18 06 67
i = 6
12 18 42 44 55 94 06 67
i = 7
06 12 18 42 44 55 94 67
i = 8
06 12 18 42 44 55 67 94
?
?
?
?
?
?
?
Abstrakcyjny zapis algorytmu
for
i
:= 2
to
n
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
x
:=
A
"
i
]
Wstaw
x
w odpowiednim miejscu w
A
"1 ..
i
;
1]
end for
procedure
proste wstawianie 1
var
i
,
j
:
indeks
x
:
typ rekordu
begin
for
i
:= 2
to
n
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
x
:=
A
"
i
]
j
:=
i
;
1
while
(
j
> 0)
cand
(
x
:
klucz
<
A
"
j
]
:
klucz
)
do
A
"
j + 1] :=
A
"
j
]
j
:=
j
;
1
end while
A
"
j + 1] :=
x
end for
end
procedure
proste wstawianie 2
var
34
i
,
j
:
indeks
x
:
typ rekordu
begin
for
i
:= 2
to
n
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
x
:=
A
"
i
]
A
"0] :=
x
f
Ustawienie wartownika.
g
j
:=
i
;
1
while
x:klucz < A"j]:klucz
do
A
"
j + 1] :=
A
"
j
]
j
:=
j
;
1
end while
A
"
j + 1] :=
x
end for
end
Nieco lepsze ustawienie wartownika
...
begin
f
A"0]:klucz :=
;1
g
for
i
:= 2
to
n
do
f
Niezmiennik: ...
g
x
:=
A
"
i
]
j
:=
i
;
1
while
...
...
procedure
powkowe wstawianie
var
i
,
j
,
l
,
m
,
p
:
indeks
x
:
typ rekordu
begin
for
i
:= 2
to
n
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
x
:=
A
"
i
]
l
:= 1
p
:=
i
;
1
while
l
p
do
m := (l + p)
div
2
if
x:klucz < A"m]:klucz
then
p
:=
m
;
1
else
l
:=
m + 1
end if
35
end while
for
j
:=
i
;
1
downto
l
do
A
"
j + 1] :=
A
"
j
]
end for
A
"
l
] :=
x
end for
end
6.2 Algorytm Shella, czyli sortowanie za pomoc malej-
cych przyrostw
type
indeks
:
;
h
"1] ..
n
var
A
:
array
"
;
h
"1] + 1 ..
n
]
of
typ rekordu
procedure
sortowanie Shella
const
t
= 4
var
m
: 1 ..
t
i
,
j
,
k
,
w
:
indeks
h
:
array
"1 ..
t
]
of
integer
f
Tablica przyrost w.
g
x
:
typ rekordu
begin
h
"1] := 40
h
"2] := 13
h
"3] := 4
h
"4] := 1
for
m
:= 1
to
4
do
k
:=
h
"
m
]
w
:=
;
k
f
Miejsce wartownika.
g
for
i
:=
k + 1
to
n
do
x
:=
A
"
i
]
if
w
= 0
then
w
:=
;
k
end if
w
:=
w + 1
A
"
w
] :=
x
f
Ustawienie wartownika.
g
j
:=
i
;
k
while
x:klucz < A"j]:klucz
do
A
"
j + k] :=
A
"
j
]
j
:=
j
;
k
end while
A
"
j + k] :=
x
end for
end for
end
36
Prosta wersja sortowania Shella
procedure
sortowanie Shella 1
var
i
,
j
,
przyr
:
integer
x
:
typ rekordu
begin
przyr
:=
n
div
2
while
przyr
> 0
do
for
i
:=
przyr + 1
to
n
do
j
:=
i
;
przyr
while
j > 0
do
if
A
"
j
]
:
klucz
>
A
"
j + przyr].
klucz
then
zamiana
(
A
"
j
],
A
"
j + przyr])
j
:=
j
;
przyr
else
j
:= 0
f
Wyj cie z ptli.
g
end if
end while
end for
przyr
:=
przyr
div
2
end while
end
6.3 Sortowanie przez proste wybieranie
44 55 12 42 94 18 06 67
06 55 12 42 94 18 44 67
06 12 55 42 94 18 44 67
06 12 18 42 94 55 44 67
06 12 18 42 94 55 44 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
6
6
6
6
6
6
6
6
6
6
for
i
:= 1
to
n
;
1
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
37
Przypisz zmiennej
k
indeks rekordu o najmniejszym kluczu
spo r d rekord w
A
"
i
..
n
]
Wymie
A
"
i
] z
A
"
k
]
end for
procedure
proste wybieranie
var
i
,
j
,
k
:
indeks
x
:
typ rekordu
begin
for
i
:= 1
to
n
;
1
do
f
Niezmiennik:
A
"1 ..
i
;
1] jest posortowane.
g
k
:=
i
x
:=
A
"
i
]
for
j
:=
i + 1
to
n
do
if
A
"
j
]
:
klucz
<
x
:
klucz
then
k
:=
j
x
:=
A
"
j
]
end if
end for
A
"
k
] :=
A
"
i
]
A
"
i
] :=
x
end for
end
procedure
sortowanie przez wybieranie 2
var
i
,
j
,
k
,
m
,
M
,
p
,
q
: 1 ..
n
min
,
Max
:
typ rekordu
begin
i
:= 1
j
:=
n
while
i < j
do
min
:=
Max
:=
A
"
j
]
f
m
i M s wska$nikami,
g
m
:=
M
:=
j
f
odpowiednio, elementu
g
k
:=
i
f
minimalnego i maksymalnego.
g
repeat
if
A
"
k
].
klucz
A
"
k + 1].
klucz
then
p
:=
k
q
:=
k + 1
else
p
:=
k + 1
q
:=
k
38
end if
if
A
"
p
]
:
klucz
<
min
.
klucz
then
min
:=
A
"
p
]
m
:=
p
end if
if
A"q]:
klucz
>
Max
:
klucz
then
Max
:=
A
"
q
]
M
:=
q
end if
k
:=
k + 2
until
k
j
if
M
=
i
then
A
"
m
] :=
A
"
j
]
else
A
"
m
] :=
A
"
i
]
A
"
M
] :=
A
"
j
]
end if
A
"
i
] :=
min
A
"
j
] :=
Max
i
:=
i + 1
j
:=
j
;
1
end while
end
for
i
:=
n
downto
2
do
f
Niezmiennik:
A
"
i + 1 ..
n
] jest posortowane.
g
Przypisz zmiennej
k
indeks rekordu o najwikszym kluczu
spo r d rekord w
A
"1 ..
i
]
Wymie
A
"
i
] z
A
"
k
]
end for
6.4 Sortowanie przez prosta zamian
39
numer przej cia
klucze
pocztkowe k=1 k=2 k=3 k=4 k=5 k=6 k=7
44
06 06 06 06 06 06 06
55
44 12 12 12 12 12 12
12
55 44 18 18 18 18 18
42
12 55 44 42 42 42 42
94
42 18 55 44 44 44 44
18
94 42 42 55 55 55 55
06
18 94 67 67 67 67 67
67
67 67 94 94 94 94 94
-
-
-
-
-
-
procedure
sortowanie bbelkowe
var
i
,
j
:
indeks
t
:
typ rekordu
begin
for
i
:= 2
to
n
do
for
j
:=
n
downto
i
do
if
A
"
j
]
:
klucz
<
A
"
j
;
1]
:
klucz
then
t
:=
A
"
j
]
A
"
j
] :=
A
"
j
;
1]
A
"
j
;
1] :=
t
end if
end for
end for
end
procedure
sortowanie mieszane
var
j
,
k
,
l
,
p
:
indeks
t
:
typ rekordu
begin
l
:= 2
p
:=
n
k
:=
n
f
Pozycja ostatniej zamiany.
g
repeat
40
for
j
:=
p
downto
l
do
if
A
"
j
]
:
klucz
<
A
"
j
;
1]
:
klucz
then
t
:=
A
"
j
]
A
"
j
] :=
A
"
j
;
1]
A
"
j
;
1] :=
t
k
:=
j
end if
end for
l
:=
k + 1
for
j
:=
l
to
p
do
if
A
"
j
]
:
klucz
<
A
"
j
;
1]
:
klucz
then
t
:=
A
"
j
]
A
"
j
] :=
A
"
j
;
1]
A
"
j
;
1] :=
t
k
:=
j
end if
end for
p
:=
k
;
1
until
l
>
p
end
6.5 Sortowanie szybkie { algorytm Quicksort
procedure
Quicksort
(
i
,
j
:
integer
)
1.
if
A
"
i
] do
A
"
j
] zawieraj co najmniej dwa r ne klucze
then
2.
Niech
v
bdzie wikszym z dw ch r nych kluczy najbardziej
na lewo pooonych w cigu
3.
Dokona! permutacji
A
"
i
], ...,
A
"
j
] tak, e dla pewnego
k
2
"
i + 1,
j
]
podcig
A
"
i
], ...,
A
"
k
;
1] skada si z kluczy mniejszych od
v
,
a podcig
A
"
k
], ...,
A
"
j
] | z kluczy wikszych lub r wnych
v
4.
Quicksort
(
i
,
k
;
1)
5.
Quicksort
(
k
,
j
)
6.
end if
function
znajd klucz osiowy
(
i
,
j
:
integer
):
integer
f
Warto ci funkcji jest indeks wikszego z dw ch najbardziej na lewo pooonych,
r nych kluczy cigu
A
"
i
], ...,
A
"
j
],
bd$ 0, gdy cig skada si z identycznych kluczy.
g
var
pierwszy
:
typ klucza
k
:
integer
begin
pierwszy
:=
A
"
i
].
klucz
41
for
k
:=
i + 1
to
j
do
if
A
"
k
]
:
klucz
>
pierwszy
then
return
(
k
)
else
if
A
"
k
]
:
klucz
<
pierwszy
then
return
(
i
)
end if
end if
end for
return
(0)
f
Nie znaleziono r nych kluczy.
g
end
function
podzia
(
i
,
j
:
integer
klucz osiowy
:
typ klucza
):
integer
f
Dokonuje si podziau cigu
A
"
i
], ...,
A
"
j
] tak, e klucze
<
klucz osiowy
znajd si po lewej stronie, a klucze
klucz osiowy
po prawej stronie cigu.
Warto ci funkcji jest pocztek prawej grupy kluczy.
g
var
l
,
p
:
integer
begin
l
:=
i
p
:=
j
repeat
zamiana
(
A
"
l
],
A
"
p
])
while
A
"
l
].
klucz
<
klucz osiowy
do
l
:=
l + 1
end while
while
A
"
p
].
klucz
klucz osiowy
do
p
:=
p
;
1
end while
until
l
>
p
return
(
l
)
end
procedure
Quicksort
(
i
,
j
:
integer
)
f
Sortowana jest tablica
A
"
i
], ...,
A
"
j
].
g
var
klucz osiowy
:
typ klucza
indeks klucza osiowego
:
integer
k
:
integer
f
Pocztek grupy kluczy
klucz osiowy
.
g
begin
indeks klucza osiowego
:=
znajd klucz osiowy
(
i
,
j
)
if
indeks klucza osiowego
6
= 0
then
42
klucz osiowy
:=
A
"
indeks klucza osiowego
].
klucz
k
:=
podzia
(
i
,
j
,
klucz osiowy
)
Quicksort
(
i
,
k
;
1)
Quicksort
(
k
,
j
)
end if
end
procedure
quicksort
procedure
sort
(
l
,
p
:
indeks
)
var
i
,
j
:
indeks
x
,
t
:
typ rekordu
begin
i
:=
l
j
:=
p
Wybierz losowo rekord
x
f
np.
x
:=
A
"(
l + p)
div
2]
g
repeat
while
A
"
i
]
:
klucz
< x:
klucz
do
i
:=
i
+ 1
end while
while
x
:
klucz
<
A
"
j
]
:
klucz
do
j
:=
j
;
1
end while
if
i
j
then
t
:=
A
"
i
]
A
"
i
] :=
A
"
j
]
A
"
j
] :=
t
i
:=
i
+ 1
j
:=
j
;
1
end if
until
i
>
j
if
l < j
then
sort
(
l
,
j
)
end if
if
i
<
p
then
sort
(
i
,
p
)
end if
end
begin
sort
(1,
n
)
end
43
procedure
Quicksort 1
(
i
,
j
:
integer
)
f
Sortowana jest tablica
A
"
i
..
j
].
g
var
klucz osiowy
:
typ klucza
indeks klucza osiowego
:
integer
k
:
integer
f
Pocztek grupy kluczy
klucz osiowy
.
g
x
:
typ rekordu
l
,
m
:
integer
begin
if
j
;
i + 1
9
then
for
l
:=
i
+ 1
to
j
do
f
Niezmiennik:
A
"
i
..
l
;
1] jest posortowane.
g
x
:=
A
"
l
]
m
:=
l
;
1
while
(
m > i
;
1)
cand
(
x:klucz <
A
"
m]:
klucz
)
do
A
"
m + 1] :=
A
"
m
]
m
:=
m
;
1
end while
A
"
m + 1] :=
x
end for
else
indeks klucza osiowego
:=
znajd klucz osiowy
(
i
,
j
)
if
indeks klucza osiowego
6
= 0
then
klucz osiowy
:=
A
"
indeks klucza osiowego
].
klucz
k
:=
podzia
(
i
,
j
,
klucz osiowy
)
Quicksort 1
(
i
,
k
;
1)
Quicksort 1
(
k
,
j
)
end if
end if
end
6.6 Inna wersja algorytmu Quicksort
Dana jest nastpujca wersja algorytmu sortowania szybkiego
procedure
qsort
(
g, d
:
indeks
)
var
i, s
:
indeks
t
:
typ rekordu
begin
if
d < g
then
t
:=
A"d]
f
t.klucz
jest kluczem osiowym
g
s
:=
d
for
i
:=
d + 1
to
g
do
f
Niezmiennik:
A"d + 1 :: s] < t
A"s + 1 :: i
;
1]
g
44
if
A"i]:klucz < t:klucz
then
s
:=
s + 1
Zamie
(
A"s] A"i])
end if
end for
Zamie
(
A"d] A"s])
f
Niezmiennik:
A"d :: s
;
1]
< A"s]
A"s + 1 :: g]
g
qsort
(
d s
;
1)
qsort
(
s + 1 g)
end if
end
Wyznaczymy zoono ! redni tego algorytmu. W tym celu zaoymy, e:
1. Cig kluczy rekord w w tablicy
A jest losow permutacj liczb cakowitych 1
...
n.
2. Wystpienie kadej permutacji jest jednakowo prawdopodobne.
3. Pierwsze wywoanie procedury ma posta!
qsort
(1
n).
4. Operacj dominujc jest por wnanie kluczy rekord w.
Zauwamy, e dla
d
g wykonuje si 0 por wna. Wobec tego
T
sr
(0) =
T
sr
(1) = 0
:
Por wnania kluczy rekord w wykonywane s
g
;
d razy, wobec tego przy wywoaniu
qsort
(1
n) por wna wykonanych bdzie n
;
1. Za my, e kluczemosiowym zostaje
warto !
i. W wczas na lewo od klucza osiowego tra+ i
;
1 rekord w, a na prawo od
klucza osiowego
n
;
i rekord w. Wobec tego wykonamy w wczas
n
;
1 +
T(i
;
1) +
T(n
;
i)
por wna. Warto ! t musimy u redni! po wszystkich warto ciach
i z przedziau 1::n.
Poniewa kada permutacja jest jednakowo prawdopodobna, to prawdopodobiestwo,
e kluczem osiowym bdzie warto !
i wynosi
1
n
. Wobec tego
T
sr
(
n) =
n
X
i
=1
1
n(n
;
1 +
T
sr
(
i
;
1) +
T
sr
(
n
;
i)) =
=
n
;
1 + 1n
X
1
i
n
T
sr
(
i
;
1) + 1n
X
1
i
n
T
sr
(
n
;
i)
Poniewa
X
1
i
n
T
sr
(
i
;
1) =
X
1
i
+1
n
T
sr
(
i + 1
;
1) =
X
0
i
n
;1
T
sr
(
i)
X
1
i
n
T
sr
(
n
;
i) =
X
1
n
;
i
n
T
sr
(
n
;
(
n
;
i)) =
X
0
i
n
;1
T
sr
(
i)
45
otrzymujemy
T
sr
(
n) = n
;
1 + 2n
n
;1
X
i
=0
T
sr
(
i):
(4)
Mnoc obie strony r wnania (4) przez
n otrzymujemy
nT
sr
(
n) = n
2
;
n + 2
n
;1
X
i
=0
T
sr
(
i):
(5)
R wnanie (5) dla
n
;
1 ma posta!
(
n
;
1)
T
sr
(
n
;
1) = (
n
;
1)
2
;
(
n
;
1) + 2
n
;2
X
i
=0
T
sr
(
i):
(6)
Odejmujc stronami (5) i (6) otrzymujemy
nT
sr
(
n)
;
(
n
;
1)
T
sr
(
n
;
1) =
n
2
;
n
;
(
n
;
1)
2
+
n
;
1 + 2
n
;1
X
i
=0
T
sr
(
i)
;
2
n
;2
X
i
=0
T
sr
(
n)
nT
sr
(
n) = (n + 1)T
sr
(
n
;
1) + 2(
n
;
1)
:
(7)
Do znalezienia rozwizania (6) zastosujemy
metod czynnika sumacyjnego
"11, str.
41]. Z (7) wynika, i
a
n
=
n b
n
=
n + 1 c
n
= 2(
n
;
1). Wobec tego
s
n
= a
n
;1
a
n
;2
a
1
b
n
b
n
;1
b
2
= (n
;
1)(
n
;
2)
3
2
1
(
n + 1)n(n
;
1)(
n
;
2)
3 =
2
(
n + 1)n
Poniewa
T
sr
(0) = 0, otrzymujemy
T
sr
(
n) = 1
s
n
c
n
n
X
k
=1
s
k
c
k
=
=
1
2
n
(
n
+1)
n
n
X
k
=1
2
k(k + 1)
2(
k
;
1) =
= 2(
n + 1)
n
X
k
=1
k
;
1
k(k + 1) =
= 2(
n + 1)
;
n
X
k
=1
1
k + 2
n
X
k
=1
1
k + 1
!
=
= 2(
n + 1)
;
n
X
k
=1
1
k + 2
n
X
k
=1
1
k +
2
n + 1
;
2
!
=
= 2(
n + 1)
n
X
k
=1
1
k
;
2
n
n + 1
!
=
= 2(
n + 1)H
n
;
4
n:
2
46
6.7 Czasy wykonania programw sortowania
T
ab ela
I
.
Metoda sortowania
Cigi uporzdk.
Cigi
losowe
Cigi odwrot.
uporzdk.
Wstawianie proste
12
23 366 1444 704
2836
Wstawianie po wkowe
56
125 373 1327 662
2490
Wybieranie proste
489
1907 509 1956 695
2675
Sortowanie bbelkowe
540
2165 1026 4054 1492
5931
Sortowanie bbelkowe ze znacznikiem
5
8 1104 4270 1645
6542
Sortowanie mieszane
5
9 961 3642 1619
6520
Sortowanie metod Shella
58
116 127 349 157
492
Sortowanie stogowe
116
253 110 241 104
226
Sortowanie szybkie
31
69
60 146
37
79
Sortowanie przez czenie
99
234 102 242
99
232
T
ab ela
I I
. (klucze wraz ze zwizanymi z nimi danymi)
Metoda sortowania
Cigi uporzdk.
Cigi
losowe
Cigi odwrot.
uporzdk.
Wstawianie proste
12
46 366 1129 704
2150
Wstawianie po wkowe
46
76 373 1105 662
2070
Wybieranie proste
489
547 509 607 695
1430
Sortowanie bbelkowe
540
610 1026 3212 1492
5599
Sortowanie bbelkowe ze znacznikiem
5
5 1104 3237 1645
5762
Sortowanie mieszane
5
5 961 3071 1619
5757
Sortowanie metod Shella
58
186 127 373 157
435
Sortowanie stogowe
116
264 110 246 104
227
Sortowanie szybkie
31
55
60 137
37
75
Sortowanie przez czenie
99
196 102 195
99
187
7 Selekcja
A
:
array
"1 ..
n
]
of
typ klucza
function
selekcja
(
i, j, k
:
integer
):
typ klucza
f
Znajdowany jest
k
-ty najmniejszy klucz w tablicy
A
"
i
..
j
].
g
var
klucz osiowy
:
typ klucza
47
indeks klucza osiowego
:
integer
m
:
integer
f
Pocztek grupy kluczy
klucz osiowy
.
g
begin
indeks klucza osiowego
:=
znajd klucz osiowy
(
i
,
j
)
if
indeks klucza osiowego
6
= 0
then
klucz osiowy
:=
A
"
indeks klucza osiowego
]
m
:=
podzia
(
i
,
j
,
klucz osiowy
)
if
k
m
;
i
then
return
(
selekcja
(
i
,
m
;
1,
k
))
else
return
(
selekcja
(
m
,
j
,
k
;
m + i))
end if
else
return
(
A
"
i
])
end if
end
8 Algorytmy sortowania, w ktrych korzysta si
ze szczeglnych wasnoci kluczy
type
typ rekordu
=
record
klucz
: 1 ..
n
...
end
var
A
,
B
:
array
"1 ..
n
]
of
typ rekordu
Algorytm 1
for
i
:= 1
to
n
do
B
"
A
"
i
].
klucz
] :=
A
"
i
]
end for
Algorytm 2
for
i
:= 1
to
n
do
while
A"i]:klucz
6
=
i
do
zamiana
(
A
"
i
],
A
"
A
"
i
].
klucz
])
end while
end for
48
8.1 Sortowanie kubekowe
type
typ klucza
= 1 ..
m
f
lub znakowy og lnie typ dyskretny,
w zbiorze warto ci kt rego istnieje
relacja porzdku
g
typ rekordu
=
record
klucz
:
typ klucza
...
end
element listy
=
record
r
:
typ rekordu
nast
: ^
element listy
end
typ listowy
= ^
element listy
var
A
:
array
"1 ..
n
]
of
typ rekordu
f
Tablica rekord w do sortowania.
g
B
:
array
"
typ klucza
]
of
typ listowy
f
Tablica kubek w.
W kubeku rekordy sa poczone w list.
g
C
:
array
"
typ klucza
]
of
typ listowy
f
Tablica odsyaczy
do koc w list w kubekach.
g
procedure
sortowanie kubekowe
var
i
:
integer
p
,
v
:
typ klucza
begin
for
v
:=
niski klucz
to
wysoki klucz
do
B
"
v
] :=
nil
C
"
v
] :=
nil
end for
for
i
:= 1
to
n
do
WSTAW
(
A
"
i
],
B
"
A
"
i
].
klucz
],
C
"
A
"
i
].
klucz
])
end for
p
:=
niski klucz
while
B
"
p
] =
nil do
p
:=
succ
(
p
)
end while
if
p
6
=
wysoki klucz
then
for
v
:=
succ
(
p
)
to
wysoki klucz
do
if
B"v]
6
=
nil then
POCZ
(
C
"
p
],
B
"
v
],
C
"
v
])
end if
49
end for
end if
end
procedure
WSTAW
(
x
:
typ rekordu
var
l
,
m
:
typ listowy
)
var
temp
:
typ listowy
begin
temp
:=
l
new
(
l
)
l
^.
r
:=
x
l
^.
nast
:=
temp
if
temp
=
nil then
m
:=
l
end if
end
f
WSTAW
g
procedure
POCZ
(
var
lC1
:
typ listowy
lB2
,
lC2
:
typ listowy
)
f
Parametry s odsyaczami do pocztk w i koc w czonych list.
g
begin
lC1
^.
nast
:=
lB2
lC1
:=
lC2
end
f
POCZ
g
8.2 Sortowanie pozycyjne
procedure
sortowanie pozycyjne
f
Sortowana jest lista
A
o
n
rekordach, kt,orych klucze
skadaj si z p,ol
f
1
,
f
2
, ...,
f
k
o typach odpowiednio
t
1
,
t
2
, ...,
t
k
.
g
begin
for
i
:=
k
downto
1
do
for
kadej warto,sci
v
typu
t
i
do
B
i
"
v] :=
nil
f
Opr,onianie kubek,ow.
g
end for
for
kadego rekordu
r
na li,scie
A
do
przesu,n
r
z
A
na koniec listy kubeka
B
i
"
v],
gdzie
v
jest warto,sci pola
f
i
klucza rekordu
r
end for
for
kadej warto,sci
v
typu
t
i
, od najmniejszej do
najwikszej
do
docz
B
i
"
v] na koniec listy
A
50
end for
end for
end
Praktyczna implementacja algorytmu sortowania pozycyjnego
Sortowanie listy rekordw
A
wedug dat:
type
typ rekordu
=
record
dzie
: 1 .. 31
mies
: (
sty
, ...,
gru
)
rok
: 1900 .. 1999
f
Inne pola rekordu.
g
end
element listy
=
record
r
:
typ rekordu
nast
: ^
element listy
end
typ listowy
= ^
element listy
var
A
:
typ listowy
procedure
sortowanie wg dat
f
Sortowana jest lista
A
o
n
rekordach, kt rych klucze s datami.
g
var
p3
,
v3
: 1900 .. 1999
p2
,
v2
: (
sty
, ...,
gru
)
p1
,
v1
: 1 .. 31
B3
,
C3
:
array
"1900 .. 1999]
of
typ listowy
B2
,
C2
:
array
"(
sty
, ...,
gru
)]
of
typ listowy
B1
,
C1
:
array
"1 .. 31]
of
typ listowy
begin
f
Sortowanie rekord w wedug dni.
g
for
v1
:= 1
to
31
do
B1
"
v1
] :=
nil
C1
"
v1
] :=
nil
end for
while
A
6
=
nil do
f
Wstawienie rekordu
A
^.
r
na koniec listy kubeka
okre lonego przez klucz rekordu.
g
DOCZ
(
A
^.
r
,
B1
"
A
^.
r
.
dzie
],
C1
"
A
^.
r
.
dzie
])
A
:=
A
^.
nast
end while
51
p1
:= 1
while
B1
"
p1
] =
nil do
p1
:=
succ
(
p1
)
end while
if
p1
6
= 31
then
for
v1
:=
succ
(
p1
)
to
31
do
f
Przyczenie list wszystkich kubek w do koca listy
wskazanej przez
B1
"
p1
].
g
if
B1"
v1
]
6
=
nil then
POCZ
(
C1
"
p1
],
B1
"
v1
],
C1
"
v1
])
end if
end for
end if
A
:=
B1
"
p1
]
f
Dokona! podobnie sortowania kubekowego listy
A
wedug p l
A
^.
r
.
mies
oraz
A
^.
r.rok
.
g
end
procedure
DOCZ
(
x
:
typ rekordu
var
lB
,
lC
:
typ listowy
)
var
temp
:
typ listowy
begin
if
lB
=
nil then
new
(
lC
)
lC
^.
r
:=
x
lC
^.
nast
:=
nil
lB
:=
lC
else
temp
:=
lC
new
(
lC
)
lC
^.
r
:=
x
lC
^.
nast
:=
nil
temp
^.
nast
:=
lC
end if
end
f
DOCZ
g
9 Sortowanie plikw sekwencyjnych
9.1 czenie proste
procedure
sortowanie przez czenie proste
var
i j k l: indeks
52
gra
:
Boolean
p
:
integer
f
dugo ! czonych podcig w
g
begin
gra
:=
true
p
:= 1
repeat
if
gra
then
f
Inicjowanie indeks w.
g
i := 1 j := n k := n + 1 l := 2
n
else
i := n + 1 j := 2
n k := 1 l := n
end if
\cz
p{tki z i{cigu oraz j{cigu do
k{cigu oraz l{cigu."
gra
:=
not
gra
p := 2
p
until
p = n
end
L czenie
p
-tek mona zapisa nastpuj co:
h := 1
m := n
f
m okre la liczb rekord w do poczenia.
g
repeat
q := p
r := p
m := m
;
2
p
Pocz
q rekord w z i{cigu oraz r rekord w z j{cigu
k jest indeksem cigu wynikowego z przyrostem h
h :=
;
h
Zamie
k z l
until
m = 0
while
(
q <> 0)
and
(
r <> 0)
do
f
Wybieranie rekordu z
i{cigu lub j{cigu.
g
if
A"i]:klucz < A"j]:klucz
then
Przemie ! rekord z
i do k, zwiksz i oraz
uaktualnij
k
q := q
;
1
else
Przemie ! rekord z
j do k, zmniejsz j oraz
uaktualnij
k
r := r
;
1
end if
end while
53
Skopiuj koniec
i{cigu
Skopiuj koniec
j{cigu
Ci g instrukcji:
q := p
r := p
m := m
;
2
p
przyjmuje posta:
f
q wyznacza dugo ! i{cigu, za r | j{cigu.
g
if
m
p
then
q := p
else
q := m
end if
m := m
;
q
if
m
p
then
r := p
else
r := m
end if
m := m
;
r
Peny algorytm sortowania
procedure
sortowanie przez czenie proste
var
i j k l t: indeks
h m p q r:
integer
gra
:
Boolean
begin
gra
:=
true
p := 1
repeat
if
gra
then
f
Inicjowanie indeks w.
g
i := 1 j := n k := n + 1 l := 2
n
else
i := n + 1 j := 2
n k := 1 l := n
end if
h := 1
m := n
repeat
f
czenie
p-tki z i{cigu oraz j{cigu do k{cigu.
g
54
if
m
p
then
q := p
else
q := m
end if
m := m
;
q
if
m
p
then
r := p
else
r := m
end if
m := m
;
r
while
(
q <> 0)
and
(
r <> 0)
do
f
czenie cig w.
g
if
A"i]:klucz < A"j]:klucz
then
A"k] := A"i]
i := i + 1
k := k + h
q := q
;
1
else
A"k] := A"j]
j := j
;
1
k := k + h
r := r
;
1
end if
end while
f
Kopiowanie koca
i{cigu.
g
while
q <> 0
do
A"k] := A"i]
i := i + 1
k := k + h
q := q
;
1
end while
f
Kopiowanie koca
j{cigu.
g
while
r <> 0
do
A"k] := A"j]
j := j
;
1
k := k + h
r := r
;
1
end while
h :=
;
h
f
Zamiana
k z l.
g
t := k
k := l
l := t
until
m = 0
f
Koniec fazy (przebiegu).
g
55
gra
:=
not
gra
p := 2
p
until
p
n
f
Koniec sortowania.
g
if not
gra
then
for
i := 1
to
n
do
A"i] := A"i + n]
end for
end if
end
9.2 czenie naturalne
c: 22 36 06 79 26 45 75 13 31 62 27 76 33 16 62 47
Przebieg 1. a: 22 36 ' 26 45 75 ' 27 76 ' 16 62 '
b: 06 79 ' 13 31 62 ' 33 ' 47
= c: 06 22 36 79 ' 13 26 31 45 62 75 ' 27 33 76 ' 16 47 62
Przebieg 2. a: 06 22 36 79 ' 27 33 76 '
b: 13 26 31 45 62 75 ' 16 47 62
= c: 06 13 22 26 31 36 45 62 75 79 ' 16 27 33 47 62 76
Przebieg 3. a: 06 13 22 26 31 36 45 62 75 79 '
b: 16 27 33 47 62 76
= c: 06 13 16 22 26 27 31 33 36 45 47 62 62 75 76 79
type
tama
=
le of
typ rekordu
var
c:
tama
f
Plik do sortowania.
g
procedure
sortowanie przez czenie naturalne
var
l:
integer
f
Oznacza liczb serii w pliku
c.
g
a b:
tama
begin
repeat
rewrite
(
a)
f
Uczynienie plik w
g
rewrite
(
b)
f
a i b pustymi.
g
reset
(
c)
f
Przygotowanie pliku
c do czytania.
g
rozdzielanie
reset
(
a)
reset
(
b)
rewrite
(
c)
l := 0
czenie
until
l = 1
end
procedure
rozdzielanie
f
Z
c na a i b.
g
begin
repeat
56
kopiuj seri
(
c a)
if not
eof
(
c)
then
kopiuj seri
(
c b)
end if
until
eof
(
c)
end
procedure
czenie
f
Z
a i b na c.
g
begin
repeat
cz serie
l := l + 1
until
eof
(
b)
if not
eof
(
a)
then
kopiuj seri
(
a c)
l := l + 1
end if
end
procedure
kopiuj seri
(
var
x y:
tama
)
f
Kopiowanie jednej serii z pliku
x do y.
ks jest globaln zmienn boolowsk okre lajc,
czy osignito koniec serii.
g
begin
repeat
kopiuj
(
x y)
until
ks
end
procedure
kopiuj
(
var
x y:
tama
)
f
Kopiowanie jednego elementu z pliku
x do y.
g
var
buf
:
typ rekordu
begin
read
(
x
buf
)
write
(
y
buf
)
if
eof
(
x)
then
ks :=
true
else
ks :=
buf.klucz
> x^:
klucz
end if
end
procedure
cz serie
f
czenie po jednej serii z
a i b oraz
przesanie serii wynikowej do
c.
g
57
begin
repeat
if
a^:klucz < b^:klucz
then
kopiuj
(
a c)
if
ks
then
kopiuj seri
(
b c)
end if
else
kopiuj
(
b c)
if
ks
then
kopiuj seri
(
a c)
end if
end if
until
ks
end
Przykad 1
c: 03 02 05
11 07 13 19 17 23 31 29 37 43
a: 03 ' 07 13 19 ' 29 37 43 '
b: 02 05 11 ' 17 23 31
c: 02 03 05
07 11 13 17 19 23 29 31 37 43
Przykad 2
c: 13 57 17 19 11 59 23 29 07 61
a: 13 57 ' 11 59 ' 07 61 '
b: 17 19 ' 23 29 '
c: 13 17 19 23 29
57 11 59
Poprawiona procedura
czenia
procedure
czenie
f
Z
a i b na c.
g
begin
repeat
cz serie
l := l + 1
until
eof
(
a)
or
eof
(
b)
while not
eof
(
a)
do
kopiuj seri
(
a c)
l := l + 1
end while
while not
eof
(
b)
do
58
kopiuj seri
(
b c)
l := l + 1
end while
end
10 Algorytmy zachanne (aroczne)
10.1 Kolorowanie zachanne
procedure
kolorowanie zachanne
(
G
:
graf
var
nowy kolor
:
zbir
)
f
Procedura docza do zbioru
nowy kolor
te
wierzchoki grafu, kt rym mona przyporzdkowa!
ten sam kolor.
g
var
jest
:
Boolean
v w:
integer
begin
nowy kolor
:=
v := pierwszy niepokolorowany wierzchoek w G
while
v <>
null do
jest
:=
false
w := pierwszy wierzchoek w zbiorze
nowy kolor
while
w <>
null cand not
jest
do
if
istnieje krawd$ pomidzy
v i w w G
then
jest
:=
true
end if
w := nastpny wierzchoek w zbiorze
nowy kolor
end while
if
jest
=
false
then
Oznacz
v jako pokolorowany
Docz
v do zbioru
nowy kolor
end if
v := nastpny niepokolorowany wierzchoek w G
end while
end
10.2 Problem komiwoja era
procedure
komiwoja er
(
G
:
graf
var
droga
:
cig krawdzi
)
f
Wyznacza si drog o minimalnym koszcie w gra+e
G.
g
var
i:
integer
min
:
real
59
begin
min
:=
1
for
i := 1
to
(
n
;
1)!
do
p := i{ta permutacja wierzchok w v
1
v
2
::: v
n
;1
f
Niech
d(p) jest drog w gra+e G odpowiadajc
permutacji
p jego wierzchok w.
g
if
koszt(d(p)) < min
then
droga := d(p)
min := koszt(d(p))
end if
end for
end
10.3 Znajdowanie najtaszych drg | Algorytm Dijkstry
procedure
Dijkstra
f
Obliczane s koszty najtaszych dr g z wierzchoka 1
do kadego innego wierzchoka w gra+e zorientowanym.
g
begin
S :=
f
1
g
for
i := 2
to
n
do
D"i] := C"1 i]
f
Inicjalizacja tablicy
D.
g
end for
for
i := 1
to
n
;
1
do
Wybra! wierzchoek
w ze zbioru V
;
S taki,
e
D"w] jest minimalne
Doczy!
w do S
for
kadego wierzchoka
v w zbiorze V
;
S
do
D"v] := min(D"v] D"w] + C"w v])
end for
end for
end
11 Algorytmy grafowe
11.1 Przeszukiwanie grafu w gb
procedure
wg(v)
f
Przeszukiwanie w gb z wierzcholka
v.
g
begin
znacznik"v] := odwiedzony
for
u
2
listy incydencji"v]
do
60
if
znacznik"u] = nieodwiedzony
then
f
Krawd$ (
v w) wstawiana jest do drzewa
rozpinajcego.
g
wg(u)
end if
end for
end
begin
f
Przeszukiwanie grafu
G = (V E) w gb.
g
for
v
2
V
do
znacznik"v] := nieodwiedzony
end for
for
v
2
V
do
if
znacznik"v] = nieodwiedzony
then
wg(v)
end if
end for
end
Zastosowanie metody przeszukiwania w g b | wyszukiwanie skadowych
spjnoci
var
compnum
:
array
"1
::
j
V
j
]
of
integer
f
compnum"v] jest
numerem skadowej sp jno ci, do kt rej naley wierzchoek
v
g
for
v
2
V
do
compnum"v] := 0
end for
c := 0
for
v
2
V
do
if
compnum"v] = 0
then
c := c + 1
COMP(v)
end if
end for
procedure
COMP(x:
wierzchoek
)
begin
compnum(x) := c
for
w
2
adj"x]
do
if
compnum"w] = 0
then
COMP(w)
61
end if
end for
end
Nierekursywna wersja procedury przeszukiwania w g
b
procedure
wg1
(
v)
f
Na pocztku procesu przeszukiwania
P"t] = wska$nik
do pierwszego rekordu listy
adj"t] dla kadego u.
g
begin
stos
(
stos
(
v odwied$ v nowy"v] :=
false
while
stos <>
do
t := top(stos)
f
odczytaj szczytowy
element stosu
g
while
(
P"t] <>
nil
)
cand
(
not
nowy"P"t]^:wierzch])
do
P"t] := P"t]^:nast
f
znajd$ \nowy" wierzchoek
na li cie
adj"t]
g
end while
if
P"t] <>
nil then
f
nowy wierzchoek znaleziony
g
t := P"t]^:wierzch stos
(
t
odwied$
t nowy"t] :=
false
else
f
wierzchoek
t zosta wykorzystany
g
t
(
stos
f
zdejmij szczytowy wierzchoek ze stosu
g
end if
end while
end
11.2 Przeszukiwanie grafu wszerz
procedure
wsz(v)
f
Przeszukiwanie wszerz z wierzchoka
v.
g
var
K
:
kolejka wierzchokw
(typu FIFO)
begin
znacznik
"
v] :=
odwiedzony
wstaw do kolejki
(
v K)
while not
pusta kolejka
(
K)
do
x :=
pierwszy
(
K)
usu pierwszy z kolejki
(
K)
for
y
2
listy incydencji"x]
do
if
znacznik
"
y] =
nieodwiedzony
then
znacznik
"
y] :=
odwiedzony
wstaw do kolejki
(
y K)
f
Krawed$ (
x y) wstawiana jest do drzewa
62
rozpinajcego.
g
end if
end for
end while
end
begin
f
Przeszukiwanie grafu
G = (V E) wszerz.
g
for
v
2
V
do
znacznik"v] := nieodwiedzony
end for
for
v
2
V
do
if
znacznik"v] = nieodwiedzony
then
wsz(v)
end if
end for
end
Alternatywna wersja BFS
kolejka
(
kolejka
(
v nowy"v] :=
false
while
kolejka <>
do
p
(
kolejka
f
pobierz
p z kolejki (tj. z usuniciem)
g
for
n
2
adj"p]
do
if
nowy"n]
then
kolejka
(
u
nowy"u] :=
false
end if
end for
end while
Zastosowanie przeszukiwania grafu wszerz | znajdowanie najkrtszej dro-
gi pomidzy wierzchokami
v
i
x
w gra e
var
pred
:
array
"1
::
j
V
j
]
of
1
::
j
V
j
f
wierzchoki poprzedzajce
na najkr tszej drodze
g
odl:
array
"1
::
j
V
j
]
of
integer
f
dugo ! najkr tszej drogi
g
begin
for
v
2
V
do
nowy"v] :=
true
end for
kolejka := pusta kolejka kolejka
(
v
0
nowy"v
0
] :=
false
pred
"
v
0
] :=
;
1
odl"v
0
] := 0
63
while
nowy"x]
do
p
(
kolejka
for
u
2
adj"p]
do
if
nowy"u]
then
kolejka
(
u nowy"u] :=
false
pred
"
u] := p odl"u] := odl"p] + 1
end if
end for
end while
end
11.3 Wyznaczanie cykli podstawowych (fundamentalnych)
begin
for
x
2
V
do
num"x] := 0
f
inicjacja numeracji wierzchok w
g
end for
i := 0
f
licznik do numeracji kolejnych wierzchok w
odwiedzanych w gb
g
j := 0
f
licznik cykli fundamentalnych
g
k := 0
f
wska$nik stosu
g
for
x
2
V
do
if
num"x] = 0
then
k := k + 1
stos"k] := x
ZNAJD CYKLE
(
x 0)
k := k
;
1
end if
end for
end
procedure
ZNAJD CYKLE
(
v u)
f
v | wierzchoek aktualny,
u | wierzchoek poprzedni
g
begin
i := i + 1
f
Odwiedzone wierzchoki zostaj ponumerowane
g
num"v] := i
f
rosnco zgodnie z licznikiem
i.
g
for
w
2
adj"v]
do
if
num"w] = 0
then
k := k + 1
stos"k] := w
ZNAJD CYKLE
(
w v)
k := k
;
1
else
64
if
num"w] < num"v]
cand
w <> u
then
j := j + 1
f
licznik cykli
g
\
s
j
jest cyklem (
w stos"k] stos"k
;
1]
::: stos"t])
gdzie
stos"t] = w stos"k] = v"
end if
end if
end for
end
11.4 Minimalne drzewa rozpinajce
Algorytm Kruskala
T { zbi r krawdzi minimalnego drzewa rozpinajcego
VS
{ rodzina (zbi r) rozcz-
nych zbior w wierzchok w
begin
T :=
VS
:=
Skonstruuj kolejk priorytetow
Q zawierajc
wszystkie krawdzie ze zbioru
E
for
v
2
V
do
Dodaj
f
v
g
do
VS
end for
while
j
VS
j
> 1
do
Wybierz z kolejki
Q krawd$ (v w) o najmniejszym koszcie
Usu (
v w) z Q
if
v i w nale do r nych zbior w W1 i W2
nalecych do
VS
then
Zastp
W1 i W2 w
VS
przez
W1
W2
Dodaj (
v w) do T
end if
end while
end
Algorytm najbliszego s siedztwa (Prima i Dijkstry)
(
n =
j
V
j
)
var
near:
array
"1
:: n]
of
1
:: n
f
dla kadego wierzchoka
v,
kt ry nie znalaz si jeszcze w drzewie, element
near"v] zapamituje najbliszy mu wierzchoek drzewa
g
dist:
array
"1
:: n]
of
1
:: n
f
dist"v] zapamituje
odlego !
v od najbliszego mu wierzchoka drzewa
g
65
W = "w
ij
]
f
macierz koszt w
g
begin
Wybierz arbitralnie
v
0
for
v
2
V
do
dist"v] := W"v v
0
]
f
koszt krawdzi (
v
0
v)
g
near"v] := v
0
end for
V
t
:=
f
v
0
g
f
wierzchoki drzewa
g
E
t
:=
f
krawdzie drzewa
g
W
t
:= 0
f
sumaryczny koszt drzewa
g
while
V
t
<> V
do
v := wierzchoek z V
;
V
t
o najmniejszej
warto ci
dist"v]
V
t
:=
V
t
f
v
g
E
t
:=
E
t
f
(
v near(v))
g
W
t
:=
W
t
+
dist"v]
for
x
2
V
;
V
t
do
if
dist"x] > W"v x]
then
dist"x] := W"v x]
near"x] := v
end if
end for
end while
end
11.5 Wyznaczanie cykli Eulera
begin
STOS
(
f
opr nianie
g
CE
(
f
stos w
g
v := dowolny wierzchoek grafu
STOS
(
v
while
STOS
6
=
do
v := szczyt(
STOS
)
f
v jest szczytowym elementem stosu
g
if
inc
"
v]
6
=
then
f
lista incydencji
v jest niepusta
g
u := pierwszy wierzchoek listy
inc
"
v]
STOS
(
u
f
usuwanie krawdzi (
u v) z grafu
g
inc
"
v] :=
inc
"
v]
;
f
u
g
inc
"
u] :=
inc
"
u]
;
f
v
g
else
f
lista incydencji
v jest pusta
g
v
(
STOS
f
przeniesienie szczytowego wierzchoka stosu
STOS
g
CE
(
v
f
do stosu
CE
g
66
end if
end while
end
12 Wyszukiwanie wyczerpujace. Algorytm z po-
wrotami
procedure
wyszukiwanie z powrotami
begin
Wyznacz
S
1
f
na podstawie
A
1
i ogranicze
g
k := 1
while
k > 0
do
while
S
k
<>
do
a
k
:= element z
S
k
S
k
:=
S
k
{
f
a
k
g
if
(
a
1
,
a
2
, ... ,
a
k
) jest rozwizaniem
then
write((
a
1
,
a
2
, ... ,
a
k
))
end if
k := k + 1
Wyznacz
S
k
f
na podstawie
A
k
i ogranicze,n
g
end while
k := k
;
1
f
powr t
g
end while
end
13 Przeszukiwanie heurystyczne
13.1 Przeszukiwanie wszerz
procedure
BFS
begin
Q
(
f
zerowanie kolejki
g
Q
(
s
0
f
stan pocztkowy do kolejki
g
loop
if
kolejka
Q pusta
then
return
(poraka)
end if
s
(
Q
f
pobranie stanu z kolejki
g
Wygenerowanie nastpnik w
s
j
stanu
s na podstawie
operatora dla stanu
s
Wstawienie stan w
s
j
do kolejki
67
if
dowolny stan
s
j
jest stanem kocowym
then
return
(sukces)
end if
end loop
end
BFS
13.2 Przeszukiwanie w gb z iteracyjnym pogbianiem
procedure
DFS
(
s,
gboko
,
odcicie
)
f
Przeszukiwanie w gb z odciciem.
s | biecy stan,
gboko
| bieca gboko !.
g
begin
for
s
j
2
nastpniki
(
s)
do
if
s
j
jest stanem kocowym
then
return
(sukces)
f
znaleziono rozwizanie
g
end if
if
gboko
+ 1
<
odcicie
then
DFS
(
s
j
,
gboko
+ 1,
odcicie
)
end if
end for
end
DFS
for
odcicie
:= 1
to
odcicie max
do
DFS
(
s
0
, 0,
odcicie
)
end for
return
(poraka)
13.3 Przeszukiwanie wedug strategii najlepszy wierzcho-
ek jako pierwszy"
OTWARTE
(
(
s ^f(s))
f
wierzchoek pocztkowy na list
g
while
lista
OTWARTE
nie pusta
do
(*)
Pobranie z listy
OTWARTE
wierzchoka
i o minimalnej warto ci ^f(i)
ZAMKNITE
(
(
i ^f(i))
if
i jest wierzchokiem kocowym
then
return
(sukces)
end if
Rozszerzenie wierzchoka
i przez wyznaczenie wszystkich jego
nastpnik w
j i obliczenie ^f(j)
if
j nie wystpuje na listach
OTWARTE
i
ZAMKNITE
then
OPEN
(
(
j ^f(j))
68
Ustanowienie wska$nika od wierzchoka
j do jego poprzednika i
(aby umoliwi! odtworzenie rozwizania kocowego)
else
(**)
if
j wystpuje na li cie
OTWARTE
lub
ZAMKNITE
then
if
nowe ^
f(j) < stare ^f(j)
then
stare ^
f(j) := nowe ^f(j)
Ustanowienie wska$nika od
j do nowego poprzednika i
end if
if
wierzchoek
j jest na li cie
ZAMKNITE
then
Przesunicie (
j ^f(j)) na list
OTWARTE
end if
end if
end if
end while
return
(poraka)
14 Generowanie permutacji
procedure
PERMUTACJE
(
n, m)
begin
(
p
1
p
2
...
p
m
) := (12 ...
m)
Wyprowad$ (
p
1
p
2
...
p
m
) na wyj cie
u
1
,
u
2
, ...,
u
n
:= (1
1 ... 1)
for
i := 1
to
n
P
m
;
1
do
NAST.PNA PERMUTACJA(
n, m, p
1
,
p
2
, ...,
p
m
)
end for
end
procedure
NASTPNA PERMUTACJA
(
n, m, p
1
,
p
2
, ...,
p
m
)
begin
for
i := 1
to
m
do
u"p
i
] := 0
f
zaznaczenie, kt re elementy s w permutacji
g
end for
f
Znalezienie najwikszego, nieuywanego elementu w zbiorze
f
1,2,...,n
g
.
g
f := n
while
u"f] <> 1
do
f := f
;
1
end while
f
Znalezienie najbardziej na prawo pooonego,
mody+kowalnego elementu permutacji.
g
k := m + 1
i := 0
f
Indeks elementu permutacji, kt ry zostanie zmody+kowany.
g
69
while
i = 0
do
k := k
;
1
u"p
k
] := 1
if
p
k
< f
then
f
uaktualnij
p
k
g
Znajd$ najmniejsze
j takie, e p
k
< j
n oraz u"j] = 1
i := k
p
i
:=
j
f
zmody+kowanie permutacji
g
u"p
i
] := 0
else
f := p
k
f
najwikszy, nieuywany element jest ustawiany na warto !
p
k
g
end if
end while
f
Uaktualnienie element w lecych na prawo od
p
i
g
for
k := 1
to
m
;
i
do
if
u"s] jest k-t pozycj w tablicy u r wn 1
then
p
i
+
k
:=
s
end if
end for
f
Przywr ! 1-ki w tablicy
u.
g
for
k := 1
to
i
do
u"p
k
] := 1
end for
Wyprowad$ (
p
1
p
2
...
p
m
) na wyj cie
end
procedure
RZD
(
n, m, p
1
,
p
2
, ...,
p
m
,
d)
begin
for
i := 1
to
m
do
d := 0
for
j := 1
to
i
;
1
do
if
p
i
< p
j
then
d := d + 1
end if
end for
r
i
:=
p
i
;
i + d
end for
d := r
m
+ 1
waga
:= 1
for
k := m
;
1
downto
1
do
waga
:= (
n
;
k)
waga
d := d + r
k
waga
end for
end
RZD
70
procedure
RZD ODWR
(
n, m, d, p
1
,
p
2
, ...,
p
m
)
begin
d := d
;
1
for
i := 1
to
n
do
s
i
:= 0
end for
a := 1
f
obliczenie (
n
;
m + 1)(n
;
m + 2)...(n
;
1)
g
for
i := m
;
1
downto
1
do
a := a
(
n
;
m + i)
end for
f
wyznaczanie
p
i
,
i = 1, 2, ..., m
g
for
i := 1
to
m
do
r :=
b
d=a
c
d := d
;
r
a
if
n > i
then
a := a=(n
;
i)
end if
k := 0 j := 0
f
szukanie (
r + 1)-ego elementu tablicy s r wnego 0
g
while
k < r + 1
do
j := j + 1
if
s
j
= 0
then
f
element =
j nie wystpi jeszcze w permutacji
g
k := k + 1
end if
end while
p
i
:=
j
f
element permutacji =
j
g
s
j
:= 1
f
w permutacji wystpi element =
j
g
end for
end
RZD ODWR
15 Literatura
"1] Wirth, N.,
Algorytmy + Struktury Danych = Programy,
WNT, Warszawa, 1980.
"2] Banachowski, L., Kreczmar, A.,
Elementy Analizy Algorytmw,
WNT, Warszawa,
1982.
"3] Alagi!, S., Arbib, M.A.,
Projektowanie Programw Poprawnych i Dobrze Zbudo-
wanych,
WNT, Warszawa, 1982.
"4] Aho, A.V., Ullman, J.D.,
Projektowanie i Analiza Algorytmw Komputerowych,
PWN, Warszawa, 1983.
"5] Reingold, E.M., Nievergelt, J., Deo, N.,
Algorytmy Kombinatoryczne,
PWN, War-
szawa, 1985.
71
"6] Bentley, J.,
Pereki Oprogramowania,
WNT, Warszawa, 1986.
"7] Lipski, W.,
Kombinatoryka dla Programistw,
WNT, Warszawa, 1987.
"8] Banachowski, L., Kreczmar, A., Rytter, W.,
Analiza Algorytmw i Struktur Da-
nych,
WNT, Warszawa, 1987.
"9] Harel, D.,
Rzecz o Istocie Informatyki. Algorytmika,
WNT, Warszawa, 1992.
"10] Banachowski, L., Diks, K., Rytter, W.,
Algorytmy i Struktury Danych,
WNT,
Warszawa, 1996.
"11] Graham, R.L., Knuth, D.E., Patashnik, O.,
Matematyka Konkretna,
PWN, War-
szawa, 1996.
"12] Cormen, T.H., Leiserson, C.E., Rivest, R.L.,
Wprowadzenie do Algorytmw,
WNT, Warszawa, 1997.
16 Pytania
1. Metody empirycznego testowania program w. Dlaczego testowanie empiryczne
jest niedoskonae? Co sdzi Dijkstra o testowaniu empirycznym?
2. Co to s: aksjomat, asercja, regua dowodzenia? Poda! aksjomaty liczb ca-
kowitych i rzeczywistych. Co to s: zdanie, predykat. Poda! kilka aksjomat w
rachunku zda.
3. Poda! i om wi! na wybranych przykadach reguy dowodzenia dla instrukcji
przypisania oraz instrukcji zoonej.
4. Poda! i om wi! na wybranych przykadach reguy dowodzenia dla instrukcji
alternatywy oraz instrukcji warunkowej.
5. Poda! i om wi! na wybranym przykadzie regu dowodzenia dla instrukcji
iteracji \dop ki". Co to jest niezmiennik ptli?
6. Poda! i om wi! na wybranym przykadzie regu dowodzenia dla instrukcji
itracji \powtarzaj". Co to jest niezmiennik ptli?
7. Poda! i om wi! na wybranym przykadzie reguy dowodzenia dla instrukcji
iteracji \dla". Co to jest niezmiennik ptli?
8. Cz ciowa oraz pena poprawno ! algorytmu. Jak dowodzi si dochodzenie ob-
licze algorytmu do punktu kocowego (wasno ! stopu)?
9. Poda! de+nicje poj!: rozmiar danych, dziaanie dominujce, zoono ! cza-
sowa algorytmu, zoono ! pamiciowa algorytmu. Wymieni! typowe funkcje
okre lajce zoono ci obliczniowe algorytm w. Po co wyznacza si zoono !
obliczeniow algorytmu?
72
10. Co rozumiesz przez: zoono ! pesymistyczn algorytmu, zoono ! redni al-
gorytmu? Udowodnij, e
W(n) = a
m
n
m
+ ... +
a
1
n + a
0
=
O(n
m
) dla
n > 0.
11. Jak brzmi de+nicja O-notacji? Poda! i udowodni! trzy dowolne wasno ci rzdu
funkcji.
12. Okre li! zoono ! obliczeniow algorytmu wyznaczania warto ci wielomianu
dla przypadk w: (a) korzystajc bezpo rednio ze wzoru, (b) korzystajc ze sche-
matu Hornera.
13. Poda! dwa algorytmy znajdowania maksymalnego elementu w tablicy. Wyzna-
czy! i por wna! ich zoono ci.
14. Poda! algorytmy znajdowania elementu maksymalnego i minimalnego w zada-
nym zbiorze dla przypadk w: (a) kolejne znajdowanie elementumaksymalnegoa
nastpnie minimalngo, (b) dzielenie zadania na podzadania. Okre li! zoono !
obliczniow algorytm w.
15. Poda! algorytm mnoenia dw ch
n
-bitowych liczb dw jkowych z zastosowa-
niem metody dzielenia zadania na podzadania. Okre li! zoono ! obliczeniow
algorytmu.
16. Wyprowadzi! rozwizania r wna rekurencyjnych:
T(n) = b dla n = 1 oraz
T(n) = aT(
n
c
) +
bn dla n > 1. Poda! interpretacj rozwiza.
17. Om wi! zasad r wnowaenia rozmiar w podzada na przykadzie zadania sor-
towania, rozwaajc algorytm sortowania przez wyb r prosty oraz rekursywny
algorytm sortowania przez czenie. Okre li! zoono ci obliczeniowe algoryt-
m w.
18. Sformuowa! zadanie sortowania. Poda! og ln klasy+kacj algorytm w sorto-
wania oraz klasy+kacj algorytm w sortowania wewntrznego. Poda! de+nicje
poj!: drzewo decyzyjne sortowania, gboko ! i wysoko ! wierzchoka w drze-
wie, wysoko ! drzewa. Okre li! kres dolny zoono ci obliczeniowej algorytm w
sortowania wewntrznego z pomoc por wna.
19. Poda! wasno ci kopca oraz om wi!spos b jego implementacji.Poda! i wyja ni!
dziaanie procedur:
przemie w gr
i
przemie w d
.
20. Poda! abstrakcyjny opis kolejki priorytetowej. Poda! i wyja ni! dziaanie pro-
cedur
wstaw
i
usu min
dla kolejki implementowanej z pomoc kopca. Jakie s
inne moliwe implementacje kolejki? Por wna! je ze sob pod ktem zoono ci
obliczeniowej.
21. Poda! algorytm budowania kopca (faza 1. sortowania przez kopcowanie). Wy-
znaczy! jego zoono ! pesymistyczn.
22. Poda! algorytm sortowania przez kopcowanie oraz okre li! jego pesymistyczn
zoono ! obliczeniow.
73
23. Poda! algorytm sortowania liczb naturalnych z zakresu "1
::n] o zoono ci linio-
wej. Czy przy sortowaniu niezbdna jest dodatkowa tablica?
24. Poda! algorytm sortowania kubekowego. Jaka jest jego zoono !? Co to jest
porzdek leksykogra+czny? Poda! algorytm sortowania pozycyjnego. Jaka jest
jego zoono !?
25. Poda! algorytm sortowania przez proste wstawianie (z wartownikiem). Okre li!
jego zoono ! pesymistyczn oraz redni.
26. Poda! algorytm sortowania metod Shella. Jak naley dobiera! przyrosty? Jaka
jest zoono ! algorytmu?
27. Poda! algorytm sortowania przez proste wybieranie. Okre li! jego zoono !
pesymistyczn oraz redni. Jakie s moliwo ci ulepszania algorytmu?
28. Poda! algorytm sortowania bbelkowego. Jaka jest jego zozono !? Jakie s
moliwo ci ulepszania algorytmu?
29. Poda! algorytm sortowania szybkiego (Quicksort). Co warunkuje jego szybkie
dziaanie.
30. Wyznaczy! zoono ! pesymistyczn i redni algorytmu sortowania szybkiego.
31. Om
wi! dwie metody wyznaczania
k-tego co do wielko ci klucza w tablicy: a)
mody+kacja algorytmu sortowania przez kopcowanie b) algorytm rekursywny.
Jakie s zoono ci tych metod?
32. Poda! algorytm sortowania plik w sekwencyjnych przez czenie proste (na
\ rednim" poziomie abstrakcji). Jaka jest zoono ! algorytmu?
33. Poda! algorytm sortowania plik w sekwencyjnych przez czenie naturalne (na
\ rednim" poziomie abstrakcji). Jaka jest zoono ! algorytmu?
34. Om wi! idee sortowania przez wielokierunkowe czenie wywaone oraz sorto-
wania polifazowego. Jakie s zoono ci tych metod?
35. Sformuowa! zadanie wyszukiwania. Poda! algorytmy wyszukiwania liniowego
(bez wartownika i z wartownikiem) oraz okre li! ich zoono ci rednie i pesy-
mistyczne.
36. Poda! algorytm wyszukiwania binarnego. Okre li!jego zoono ! pesymistyczn.
37. Por
wna! algorytmy wyszukiwania liniowego i binarnego pod ktem pesymi-
stycznej zoono ci obliczeniowej oraz narzutu zwizanego z konieczno ci reor-
ganizacji pliku rekord w.
38. Poda! wasno ci drzewa poszukiwa binarnych oraz procedury
szukaj
i
wstaw
operujce na drzewie. Jaki jest koszt wyszukiwania klucza w drzewie?
74
39. Poda! i om
wi! procedur usuwania klucza z drzewa poszukiwa binarnych.
40. Dla metody mieszania otwartego poda! procedury wyszukiwania, wstawiania i
usuwania elementu z tablicy mieszajcej. Jaka jest rednia zoono ! oblicze-
niowa kadej z procedur?
41. Dla metody mieszania zamknitego poda! procedury wyszukiwania, wstawiania
i usuwania elementu z tablicy mieszajcej.
42. Poda! wymagania jakie powinna spenia! podstawowa funkcja mieszajca. Wy-
mieni! i om wi! czsto stosowane podstawowe funkcje mieszajce.
43. Om wi! metody przezwyciania kolzji w metodzie mieszania zamknitego. Ja-
kie s wady i zalety wyszukiwania i wstawiania mieszajcego?
44. Okre li! zoono ! obliczeniow mieszania zamknitego. Jak naley dobra! ob-
jto ! tablicy mieszajcej?
45. Na czym polega restrukturyzacja tablic mieszajcych? Co to jest minimalna
doskonaa funkcja mieszajca? Poda! przykad takiej funkcji.
46. Poda! algorytm naiwny" wyszukiwania wzorca w tek cie. Jaka jest jego zoo-
no !?
47. Poda! algorytm wyszukiwania Knutha, Morrisa i Pratta. Jak wyznacza si war-
to ci element w tablicy
nast
?
48. Dla wybranego przykadu poda! algorytm wyszukiwania Knutha, Morrisa i
Pratta z \wbudowanym" wzorcem. Co to jest kompilator procedur wyszuki-
wania?
49. Poda! algorytm wyszukiwania niezgodno ciowego. Om wi! jego dziaanie na
przykadzie. Jak wyznacza si warto ci element w tablicy
skok 1
.
50. Poda! algorytm wyszukiwania Boyera i Moora. Czy jest on bardziej efektywny
od algorytmu wyszukiwania niezgodno ciowego.
51. Om wi! ide algorytmu zachannego na przykadzie projektowania sekwencji
zmiany wiate dla skrzyowania. Na czym polega problem kolorowania grafu?
52. Sformuowa! problem komiwojaera. Poda!: a) algorytm typu \sprawd$ wszyst-
kie moliwo ci" b) algorytm heurystycznyoparty na postpowaniu zachannym.
Jakie s zoono ci algorytm w?
53. Sformuowa! i por wna! problemy znalezienia marszruty komiwojaera , cyklu
Eulera i cyklu Hamiltona.
54. Poda! algorytm Dijkstry znajdowania najkr tszych dr g z ustalonego wierz-
choka. Obja ni! jego dziaanie na wybranym przykadzie.
75
55. Om wi! przeszukiwanie grafu wgb. Poda! zastosowanie tego przeszukiwania
dla problemu znajdowania skadowych sp jno ci.
56. Om wi! przeszukiwanie grafu wszerz. Poda! zastosowanie tego przeszukiwania
dla problemu znajdowania najkr tszej cieki w gra+e (dugo ! cieki liczona
liczb krawdzi).
57. Poda! i om wi! algorytm znajdowania cykli fundamentalnych w gra+e. Jaka
jest jego zoono !?
58. Poda! i om wi! algorytm Kruskala znajdowania minimalnego drzewa rozpina-
jcego. Jaka jest jego zoono !?
59. Poda! i om wi! algorytm Prima i Dijkstry znajdowania minimalnego drzewa
rozpinajcego. Jaka jest jego zoono !?
60. Poda! i om
wi! algorytm wyznaczania cykli Eulera. Jaka jest jego zoono !?
61. Poda! i om
wi! algorytm wyznaczania
n
P
m
permutacji. Jaka jest jego zoo-
no !?
17 Podzikowania
W przygotowaniu pierwszej wersji niniejszych materia w uczestniczyy Beata Bart-
kowiak i Beata Gawlik, za drug wersj przygotowali Magdalena Biedzka i Zdzisaw
Koch. Kolejn wersj przygotoway Zo+a Imiela oraz Boena Bartoszek. Wersje na-
stpne przygotowali Mohamed Daghestani oraz Ilona Bargie, Wojciech Mikanik i
Joanna Sim0cak. Wszystkim tym osobom skadam serdeczne podzikowania.
76
Wyszukiwarka
Podobne podstrony:
Analiza Algorytmów Ćwiczenia
Analiza algorytmow ukrywania w Nieznany
A V Aho, J E Hopcroft,J D Ullman Algorytmy Projektowanie I Analiza Algorytmow Komputerowych
Projektowanie i analiza algorytmow
Zestawienie tematów objętych zakresem egzaminu z budowy i analizy algorytmów
Analiza Algorytmów Genetycznych jako Ukladow Dynamicznych 08 Kotowski PhD p72
Analiza algorytmow Z Czech PŚ [56]
METODY KONSTRUOWANIA I ANALIZOWANIA ALGORYTMÓ…
Analiza algorytmow
Analiza Algorytmów Ćwiczenia
Analiza algorytmow ukrywania w Nieznany
Projektowanie i analiza algorytmow 2
Projektowanie i analiza algorytmow
Projektowanie i analiza algorytmow proalg
więcej podobnych podstron