I n s t y t u t I n f o r m a t y k i
P o l i t e c h n i k a Zl s k a
A n a l i z a a l g o r y t m w
O p r a c o w a B: Z b i g n i e w C z e c h
M a t e r i a By d y d a k t y c z n e
G l i w i c e , w r z e s i e D 2 0 0 4
S p i s t r e [c i
1 D o w o d z e n i e p o p r a w n o [c i a l g o r y t m w 4
1 . 1 A k s j o m a t y a r y t m e t y k i l i c z b . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 . 2 P r a w a r a c h u n k u z d a D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 . 3 R e g u By d o w o d z e n i a ( w n i o s k o w a n i a ) . . . . . . . . . . . . . . . . . . . . . . . . 6
1 . 4 D o w o d z e n i e s k o Dc z o n o [c i a l g o r y t m w . . . . . . . . . . . . . . . . . . . . . . 8
2 Z Bo |o n o [ o b l i c z e n i o w a a l g o r y t m w 8
2 . 1 O b l i c z a n i e w a r t o [c i w i e l o m i a n u . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 . 2 M n o |e n i e l i c z b c a Bk o w i t y c h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 . 3 Z n a j d o w a n i e m a k s y m a l n e g o ( m i n i m a l n e g o ) e l e m e n t u . . . . . . . . . . . . . . 9
2 . 4 J e d n o c z e s n e z n a j d o w a n i e m a k s y m a l n e g o i m i n i m a l n e g o e l e m e n t u . . . . . . . 1 0
2 . 5 M n o |e n i e d w c h n - b i t o w y c h l i c z b d w j k o w y c h . . . . . . . . . . . . . . . . . 1 0
2 . 6 S o r t o w a n i e p r z e z Bc z e n i e . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1
3 K o p c e i k o l e j k i p r i o r y t e t o w e 1 1
3 . 1 P r o c e d u r y o p e r u j c e n a k o p c u . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1
3 . 2 O p e r a c j e n a k o l e j k a c h p r i o r y t e t o w y c h . . . . . . . . . . . . . . . . . . . . . . 1 2
3 . 3 S o r t o w a n i e p r z e z k o p c o w a n i e . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3
4 W y s z u k i w a n i e 1 4
4 . 1 W y s z u k i w a n i e l i n i o w e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4
4 . 2 W y s z u k i w a n i e l i n i o w e z z a s t o s o w a n i e m w a r t o w n i k a . . . . . . . . . . . . . . . 1 4
4 . 3 W y s z u k i w a n i e l i n i o w e w u p o r z d k o w a n e j t a b l i c y . . . . . . . . . . . . . . . . 1 5
4 . 4 W y s z u k i w a n i e b i n a r n e ( l o g a r y t m i c z n e ) . . . . . . . . . . . . . . . . . . . . . . 1 5
4 . 5 D r z e w a p o s z u k i w a D b i n a r n y c h . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5
4 . 6 H a s z o w a n i e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9
4 . 6 . 1 H a s z o w a n i e o t w a r t e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9
4 . 6 . 2 H a s z o w a n i e z a m k n i t e . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1
4 . 7 M i n i m a l n e , d o s k o n a Be f u n k c j e h a s z u j c e . . . . . . . . . . . . . . . . . . . . . 2 2
5 O p e r a c j e n a t e k s t a c h 2 4
5 . 1 W y s z u k i w a n i e n a i w n e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4
5 . 2 A l g o r y t m K n u t h a , M o r r i s a i P r a t t a ( K M P ) . . . . . . . . . . . . . . . . . . . 2 5
5 . 3 W y s z u k i w a n i e n i e z g o d n o [c i o w e . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6
5 . 4 A l g o r y t m B o y e r a i M o o r a ( B M ) . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6
6 S o r t o w a n i e 2 7
6 . 1 S o r t o w a n i e p r z e z p r o s t e w s t a w i a n i e . . . . . . . . . . . . . . . . . . . . . . . 2 7
6 . 2 A l g o r y t m S h e l l a , c z y l i s o r t o w a n i e z a p o m o c m a l e j c y c h p r z y r o s t w . . . . . 2 9
6 . 3 S o r t o w a n i e p r z e z p r o s t e w y b i e r a n i e . . . . . . . . . . . . . . . . . . . . . . . 3 0
6 . 4 S o r t o w a n i e p r z e z p r o s t a z a m i a n . . . . . . . . . . . . . . . . . . . . . . . . . 3 2
6 . 5 S o r t o w a n i e s z y b k i e a l g o r y t m Q u i c k s o r t . . . . . . . . . . . . . . . . . . . . . 3 4
6 . 6 I n n a w e r s j a a l g o r y t m u Q u i c k s o r t . . . . . . . . . . . . . . . . . . . . . . . . . 3 6
6 . 7 C z a s y w y k o n a n i a p r o g r a m w s o r t o w a n i a . . . . . . . . . . . . . . . . . . . . . 3 8
7 S e l e k c j a 3 9
8 S o r t o w a n i e p r z y u w z g l d n i e n i u s z c z e g l n y c h w Ba s n o [c i k l u c z y 3 9
8 . 1 S o r t o w a n i e k u b e Bk o w e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 0
8 . 2 S o r t o w a n i e p o z y c y j n e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1
9 A l g o r y t m y z a c h Ba n n e 4 3
9 . 1 K o l o r o w a n i e z a c h Ba n n e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3
9 . 2 P r o b l e m k o m i w o j a |e r a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3
9 . 3 Z n a j d o w a n i e n a j t a Ds z y c h d r g a l g o r y t m D i j k s t r y . . . . . . . . . . . . . . 4 4
2
1 0 A l g o r y t m y g r a f o w e 4 4
1 0 . 1 P r z e s z u k i w a n i e g r a f u w g Bb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4
1 0 . 2 P r z e s z u k i w a n i e g r a f u w s z e r z . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 6
1 0 . 3 W y z n a c z a n i e c y k l i p o d s t a w o w y c h ( f u n d a m e n t a l n y c h ) . . . . . . . . . . . . . . 4 7
1 0 . 4 M i n i m a l n e d r z e w a r o z p i n a j c e . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8
1 0 . 5 W y z n a c z a n i e c y k l i E u l e r a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9
1 1 W y s z u k i w a n i e w y c z e r p u j a c e . A l g o r y t m z p o w r o t a m i 4 9
1 2 P r z e s z u k i w a n i e h e u r y s t y c z n e 4 9
1 2 . 1 P r z e s z u k i w a n i e w s z e r z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9
1 2 . 2 P r z e s z u k i w a n i e w g Bb z i t e r a c y j n y m p o g Bb i a n i e m . . . . . . . . . . . . . . . 5 0
1 2 . 3 P r z e s z u k i w a n i e w e d Bu g s t r a t e g i i n a j l e p s z y w i e r z c h o Be k j a k o p i e r w s z y . . . . 5 0
1 3 G e n e r o w a n i e p e r m u t a c j i 5 1
1 4 P y t a n i a 5 3
1 5 P o d z i k o w a n i a 5 6
L i t e r a t u r a 5 6
3
1 D o w o d z e n i e p o p r a w n o [c i a l g o r y t m w
P r z e d d o w o d e m p o p r a w n o [c i
{ ( n > 0 ) a n d ( m > 0 ) } w a r u n e k w s t p n y ( a s e r c j a w e j [c i o w a )
b e g i n
i l o c z y n : = 0 ;
N : = n ;
r e p e a t
i l o c z y n : = i l o c z y n + m ;
N : = N - 1 ;
u n t i l N = 0 ;
e n d ;
{ i l o c z y n = n " m } w a r u n e k o s t a t e c z n y ( a s e r c j a w y j [c i o w a )
P o p r z e p r o w a d z e n i u d o w o d u
{ ( n > 0 ) a n d ( m > 0 ) }
b e g i n
i l o c z y n : = 0 ;
N : = n ;
r e p e a t
{ N i e z m i e n n i k : ( i l o c z y n + N " m = n " m ) a n d ( N > 0 ) }
i l o c z y n : = i l o c z y n + m ;
N : = N - 1 ;
{ ( i l o c z y n + N " m = n " m ) a n d ( N 0 ) }
u n t i l N = 0 ;
{ ( i l o c z y n + N " m = n " m ) a n d ( N = 0 ) }
e n d ;
{ i l o c z y n = n " m }
P r o c e s o b l i c z e n i o w y
I n s t r u k c j e W y n i k i o b l i c z e D N i e z m i e n n i k i t e r a c j i
n = 5 m = 8
i l o c z y n : = 0 ; N : = n ; i l o c z y n = 0 , N = 5 , m = 8 ( 0 + 5 " 8 = 4 0 ) a n d ( N > 0 )
i l o c z y n : = i l o c z y n + m N : = N - 1 i l o c z y n = 8 , N = 4 , m = 8 ( 8 + 4 " 8 = 4 0 ) a n d ( N > 0 )
i l o c z y n : = i l o c z y n + m N : = N - 1 i l o c z y n = 1 6 , N = 3 , m = 8 ( 1 6 + 3 " 8 = 4 0 ) a n d ( N > 0 )
i l o c z y n : = i l o c z y n + m N : = N - 1 i l o c z y n = 2 4 , N = 2 , m = 8 ( 2 4 + 2 " 8 = 4 0 ) a n d ( N > 0 )
i l o c z y n : = i l o c z y n + m N : = N - 1 i l o c z y n = 3 2 , N = 1 , m = 8 ( 3 2 + 1 " 8 = 4 0 ) a n d ( N > 0 )
i l o c z y n : = i l o c z y n + m N : = N - 1 i l o c z y n = 4 0 , N = 0 , m = 8 ( 4 0 + 0 " 8 = 4 0 ) a n d ( N = 0 )
P r o c e d u r a a s s e r t o r a z p r z y k Ba d j e j u |y c i a
p r o c e d u r e a s s e r t ( b : B o o l e a n ; t : s t r i n g ) ;
i f n o t b t h e n w r i t e ( t ) ;
a s s e r t ( ( n > 0 ) a n d ( m > 0 ) , n o t 1 ) ;
b e g i n
i l o c z y n : = 0 ;
N : = n ;
r e p e a t
a s s e r t ( ( i l o c z y n + N " m = n " m ) a n d ( N > 0 ) , n o t 2 ) ;
i l o c z y n : = i l o c z y n + m ;
N : = N - 1 ;
a s s e r t ( ( i l o c z y n + N " m = n " m ) a n d ( N 0 ) , n o t 3 ) ;
u n t i l N = 0 ;
4
a s s e r t ( ( i l o c z y n + N " m = n " m ) a n d ( N = 0 ) , n o t 4 ) ;
e n d ;
a s s e r t ( i l o c z y n = n " m , n o t 5 ) ;
1 . 1 A k s j o m a t y a r y t m e t y k i l i c z b
P r z e m i e n n o [ d o d a w a n i a i m n o |e n i a
x + y = y + x
x " y = y " x
Bc z n o [ d o d a w a n i a i m n o |e n i a
( x + y ) + z = x + ( y + z )
( x " y ) " z = x " ( y " z )
R o z d z i e l n o [ d o d a w a n i a i o d e j m o w a n i a w z g l d e m m n o |e n i a
x " ( y + z ) = x " y + x " z
x " ( y - z ) = x " y - x " z
I n n e
x + 0 = x
x " 0 = 0
x " 1 = x
1 . 2 P r a w a r a c h u n k u z d a D
e 1 , e 2 , e 3 z d a n i a
1 . P r a w a p r z e m i e n n o [c i
( e 1 '" e 2 ) a" ( e 2 '" e 1 )
( e 1 (" e 2 ) a" ( e 2 (" e 1 )
( e 1 a" e 2 ) a" ( e 2 a" e 1 )
2 . P r a w a Ba c z n o [c i
e 1 '" ( e 2 '" e 3 ) a" ( e 1 '" e 2 ) '" e 3
e 1 (" ( e 2 (" e 3 ) a" ( e 1 (" e 2 ) (" e 3
3 . P r a w a r o z d z i e l n o [c i
e 1 (" ( e 2 '" e 3 ) a" ( e 1 (" e 2 ) '" ( e 1 (" e 3 )
e 1 '" ( e 2 (" e 3 ) a" ( e 1 '" e 2 ) (" ( e 1 '" e 3 )
4 . P r a w a D e M o r g a n a
( e 1 '" e 2 ) a" e 1 (" e 2
( e 1 (" e 2 ) a" e 1 '" e 2
5 . P r a w o p o d w j n e g o p r z e c z e n i a
( e 1 ) a" e 1
6 . P r a w o w y Bc z o n e g o [r o d k a
e 1 (" e 1 a" t r u e
7 . P r a w o z a p r z e c z e n i a
e 1 '" e 1 a" f a l s e
8 . P r a w o i m p l i k a c j i
e 1 ! e 2 a" e 1 (" e 2
9 . P r a w o r w n o w a |n o [c i
( e 1 a" e 2 ) a" ( e 1 ! e 2 ) '" ( e 2 ! e 1 )
1 0 . P r a w a u p r a s z c z a n i a a l t e r n a t y w y
5
e 1 (" e 1 a" e 1
e 1 (" t r u e a" t r u e
e 1 (" f a l s e a" e 1
e 1 (" ( e 1 '" e 2 ) a" e 1
1 1 . P r a w a u p r a s z c z a n i a k o n i u n k c j i
e 1 '" e 1 a" e 1
e 1 '" t r u e a" e 1
e 1 '" f a l s e a" f a l s e
e 1 '" ( e 1 (" e 2 ) a" e 1
1 2 . P r a w o i d e n t y c z n o [c i
e 1 a" e 1
1 . 3 R e g u By d o w o d z e n i a ( w n i o s k o w a n i a )
F 1 , . . . , F n
G
F 1 , . . . , F n o r a z G s a p r e d y k a t a m i ( a s e r c j a m i ) .
Z n a c z e n i e : J e [l i F 1 , . . . , F n s p r a w d z i w e ( z a Bo |e n i a ) , t o m o |n a u d o w o d n i , |e G j e s t
p r a w d z i w e ( t e z a ) .
I n s t r u k c j a p r z y p i s a n i a
{ A ( x ! E ) } x : = E { A }
I n s t r u k c j a z l o |o n a
{ A } P 1 { B } , { B } P 2 { C }
{ A } b e g i n P 1 ; P 2 e n d { C }
U o g l n i o n a r e g u Ba d o w o d z e n i a d l a i n s t r u k c j i z Bo |o n e j
{ A i - 1 } P i { A i } d l a i = 1 , . . . , n
{ A 0 } b e g i n P 1 ; P 2 ; . . . ; P n e n d { A n }
R e g u By d o w o d z e n i a w a |n e d l a k a |d e j i n s t r u k c j i
{ A } P { B } , B ! C
1 .
{ A } P { C }
A ! B , { B } P { C }
2 .
{ A } P { C }
J e d n o c z e s n y z a p i s o b u r e g u B
A ! B , { B } P { C } , C ! D
{ A } P { D }
I n s t r u k c j a a l t e r n a t y w y
{ A '" B } P 1 { C } , { A '" B } P 2 { C }
{ A } i f B t h e n P 1 e l s e P 2 e n d i f { C }
I n s t r u k c j a w a r u n k o w a
{ A '" B } P { C } , { A '" B ! C }
{ A } i f B t h e n P e n d i f { C }
6
I n s t r u k c j a i t e r a c j i d o p k i
{ A '" B } P { A }
{ A } w h i l e B d o P e n d w h i l e { A '" B }
I n s t r u k c j a i t e r a c j i p o w t a r z a j
{ A } P { C } , { C '" B ! A }
{ A } r e p e a t P u n t i l B { C '" B }
I n s t r u k c j e i t e r a c j i d l a
1 . f o r x : = a t o b d o S e n d f o r ;
o z n a c z e n i u
i f a b t h e n
x : = x 1 ; S ;
x : = x 2 ; S ;
. . .
x : = x n ; S ;
e n d i f ;
g d z i e x 1 = a , x n = b o r a z x i = s u c c ( x i - 1 ) d l a i = 2 , . . . , n .
2 . f o r x : = b d o w n t o a d o S e n d f o r ;
o z n a c z e n i u
i f b a t h e n
x : = x 1 ; S ;
x : = x 2 ; S ;
. . .
x : = x n ; S ;
e n d i f ;
g d z i e x 1 = b , x n = a o r a z x i = p r e d ( x i - 1 ) d l a i = 2 , . . . , n .
R e g u By d o w o d z e n i a
{ ( a x b ) '" P ( [ a . . x ) ) } S { P ( [ a . . x ] ) }
{ P ( [ ] ) } f o r x : = a t o b d o S e n d f o r { P ( [ a . . b ] ) }
{ ( a x b ) '" P ( ( x . . b ] ) } S { P ( [ x . . b ] ) }
{ P ( [ ] ) } f o r x : = b d o w n t o a d o S e n d f o r { P ( [ a . . b ] ) }
P r z y k Ba d
{ A l g o r y t m d z i e l e n i a c a Bk o w i t e g o : q = x d i v y . }
{ ( x 0 ) a n d ( y > 0 ) }
b e g i n
q : = 0 ;
r : = x ;
w h i l e r y d o
{ ( x = q " y + r ) a n d ( r 0 ) a n d ( r y ) }
r : = r - y ;
q : = 1 + q ;
e n d w h i l e ;
e n d ;
{ ( x = q " y + r ) a n d ( 0 r < y ) }
7
1 . 4 D o w o d z e n i e s k o Dc z o n o [c i a l g o r y t m w
P r z y k Ba d 1
{ ( n > 0 ) a n d ( m > 0 ) }
b e g i n
i l o c z y n : = 0 ;
N : = n ;
r e p e a t
{ 0 < N = N 0 }
i l o c z y n : = i l o c z y n + m ;
N : = N - 1 ;
{ 0 N < N 0 }
u n t i l N = 0 ;
e n d ;
P r z y k Ba d 2
{ ( x 0 ) a n d ( y > 0 ) }
b e g i n
q : = 0 ;
r : = x ;
w h i l e r y d o
{ r > 0 }
r : = r - y ; { r z m n i e j s z a s i p o z o s t a j c n i e u j e m n e b o r y }
q : = 1 + q ;
{ r 0 }
e n d w h i l e ;
e n d ;
2 Z Bo |o n o [ o b l i c z e n i o w a a l g o r y t m w
2 . 1 O b l i c z a n i e w a r t o [c i w i e l o m i a n u
W ( x ) = a n x n + a n - 1 x n - 1 + . . . + a 2 x 2 + a 1 x + a 0
A l g o r y t m 1 : B e z p o [r e d n i ( n a p o d s t a w i e w z o r u )
b e g i n
W : = a [ 0 ] ;
f o r i : = 1 t o n d o
p : = x ;
f o r j : = 1 t o i - 1 d o
p : = p " x ; { P o t g o w a n i e z a s t p i o n e m n o |e n i a m i . }
e n d f o r ;
W : = a [ i ] " p + W ;
e n d f o r ;
e n d ;
A l g o r y t m 2 : H o r n e r a
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
8
b e g i n
W : = a [ n ] ;
f o r i : = n - 1 d o w n t o 0 d o
W : = W " x + a [ i ] ;
e n d f o r ;
e n d ;
2 . 2 M n o |e n i e l i c z b c a Bk o w i t y c h
Z a d a n i e : N a l e |y w y m n o |y d w i e l i c z b y c a Bk o w i t e d o d a t n i e : n " m , n m
A l g o r y t m 1
b e g i n
i l o c z y n : = 0 ;
N : = n ;
r e p e a t
i l o c z y n : = i l o c z y n + m ;
N : = N - 1 ;
u n t i l N = 0 ;
e n d ;
A l g o r y t m 2
b e g i n
i l o c z y n : = 0 ;
N : = n ;
s : = m ;
w h i l e N > 0 d o
i f o d d ( N ) t h e n
i l o c z y n : = i l o c z y n + s ;
e n d i f ;
N : = N d i v 2 ;
s : = 2 " s ;
e n d w h i l e ;
e n d ;
2 . 3 Z n a j d o w a n i e m a k s y m a l n e g o ( m i n i m a l n e g o ) e l e m e n t u
A l g o r y t m 1
b e g i n
M a x : = A [ 1 ] ;
i : = 1 ;
w h i l e i < n d o
i : = i + 1 ;
i f A [ i ] > M a x t h e n
M a x : = A [ i ] ;
e n d i f ;
e n d w h i l e ;
e n d ;
A l g o r y t m 2 ( z w a r t o w n i k i e m )
b e g i n
i : = 1 ;
w h i l e i n d o
9
M a x : = A [ i ] ;
A [ n + 1 ] : = M a x ; { U s t a w i e n i e w a r t o w n i k a . }
i : = i + 1 ;
w h i l e A [ i ] < M a x d o
i : = i + 1 ;
e n d w h i l e ;
e n d w h i l e ;
e n d ;
2 . 4 J e d n o c z e s n e z n a j d o w a n i e m a k s y m a l n e g o i m i n i m a l n e g o e l e m e n -
t u
Z a d a n i e : N a l e |y z n a l e z j e d n o c z e [n i e m a k s y m a l n y i m i n i m a l n y e l e m e n t w n - e l e m e n t o w y m
z b i o r z e S
A l g o r y t m 1 : S z u k a n i e e l e m e n t u m a k s y m a l n e g o i m i n i m a l n e g o o d d z i e l n i e
b e g i n
M a x : = d o w o l n y e l e m e n t z b i o r u S ;
f o r p o z o s t a By c h e l e m e n t w x z e z b i o r u S d o
i f x > M a x t h e n
M a x : = x ;
e n d i f ;
e n d f o r ;
e n d ;
W p o d o b n y s p o s b m o |n a z n a l e z e l e m e n t m i n i m a l n y .
A l g o r y t m 2 : M e t o d a d z i e l i z w y c i |a j ( a n g . d i v i d e a n d c o n q u e r )
O g r a n i c z e n i e : L i c z b a e l e m e n t w z b i o r u S w i n n a b y p o t g l i c z b y 2 , t j . n = 2 k d l a p e w n e g o
k .
p r o c e d u r e M a x M i n ( S ) ;
b e g i n
i f # S = 2 t h e n
N i e c h S = { a , b } ;
r e t u r n ( M A X ( a , b ) , M I N ( a , b ) ) ;
e l s e
P o d z i e l i S n a d w a r w n e p o d z b i o r y S 1 i S 2 ;
( m a x 1 , m i n 1 ) : = M a x M i n ( S 1 ) ;
( m a x 2 , m i n 2 ) : = M a x M i n ( S 2 ) ;
r e t u r n ( M A X ( m a x 1 , m a x 2 ) , M I N ( m i n 1 , m i n 2 ) ) ;
e n d i f ;
e n d ;
2 . 5 M n o |e n i e d w c h n - b i t o w y c h l i c z b d w j k o w y c h
f u n c t i o n m u l t ( x , y , n : i n t e g e r ) : i n t e g e r ;
{ x o r a z y s l i c z b a m i c a Bk o w i t y m i z e z n a k i e m ( x , y 2 n ) .
n j e s t p o t e g l i c z b y 2 . W a r t o s c i f u n k c j i j e s t x y . }
s : i n t e g e r ; { s p r z e c h o w u j e z n a k x y . }
m 1 , m 2 , m 3 : i n t e g e r ; { W a r t o [c i i l o c z y n w c z e [c i o w y c h . }
a , b , c , d : i n t e g e r ; { L e w e i p r a w e p o B w k i x i y . }
b e g i n
s : = s i g n ( x ) " s i g n ( y ) ;
x : = a b s ( x ) ;
1 0
y : = a b s ( y ) ; { U c z y n i e n i e x i y d o d a t n i m i . }
i f n = 1 t h e n
i f ( x = 1 ) a n d ( y = 1 ) t h e n
r e t u r n ( 1 ) ;
e l s e
r e t u r n ( 0 ) ;
e n d i f ;
e l s e
n
a : = b a r d z i e j z n a c z c e b i t w x ;
2
n
b : = m n i e j z n a c z c e b i t w x ;
2
n
c : = b a r d z i e j z n a c z c e b i t w y ;
2
n
d : = m n i e j z n a c z c e b i t w y ;
2
n
m 1 : = m u l t ( a , c , ) ;
2
n
m 2 : = m u l t ( a - b , d - c , ) ;
2
n
m 3 : = m u l t ( b , d , ) ;
2
n
2
r e t u r n ( s " ( m 1 " 2 n + ( m 1 + m 2 + m 3 ) " 2 + m 3 ) ) ;
e n d i f ;
e n d ; { m u l t }
2 . 6 S o r t o w a n i e p r z e z Bc z e n i e
p r o c e d u r e S O R T ( i , j : i n t e g e r ) ;
b e g i n
i f i = j t h e n
r e t u r n ( x i ) ;
e l s e
m : = ( i + j - 1 ) / / 2 ;
r e t u r n ( AC Z E N I E ( S O R T ( i , m ) , S O R T ( m + 1 , j ) ) ) ;
e n d i f ;
e n d ;
3 K o p c e i k o l e j k i p r i o r y t e t o w e
3 . 1 P r o c e d u r y o p e r u j c e n a k o p c u
p r o c e d u r e p r z e m i e [ w g r ( p : i n t e g e r ) ;
{ E l e m e n t A [ p ] p r z e m i e s z c z a n y j e s t w g r k o p c a .
W a r u n e k w s t p n y : k o p i e c ( 1 , p - 1 ) i p > 0 .
W a r u n e k o s t a t e c z n y : k o p i e c ( 1 , p ) . }
v a r d , r : i n t e g e r ; { d d z i e c k o , r r o d z i c }
b e g i n
d : = p ;
l o o p
{ N i e z m i e n n i k : k o p i e c ( 1 , p ) z w y j t k i e m b y m o |e
r e l a c j i p o m i d z y A [ d ] i j e g o r o d z i c e m . 1 d p . }
i f d = 1 t h e n
b r e a k ;
e n d i f ;
r : = d d i v 2 ;
i f A [ r ] A [ d ] t h e n
b r e a k ;
e n d i f ;
z a m i a n a ( A [ r ] , A [ d ] ) ;
d : = r ;
e n d l o o p ;
e n d ; { p r z e m i e [ w g r e }
1 1
P r o c e d u r a p r z e m i e [ w g r z u |y c i e m w a r t o w n i k a
p r o c e d u r e p r z e m i e [ w g r ( p : i n t e g e r ) ;
v a r d : i n t e g e r ;
x : . . . ; { T y p z g o d n y z t y p e m A . }
b e g i n
x : = A [ p ] ;
A [ 0 ] : = x ; { U s t a w i e n i e w a r t o w n i k a . }
d : = p ;
l o o p
r : = d d i v 2 ;
i f A [ r ] x t h e n
b r e a k ;
e n d i f ;
A [ d ] : = A [ r ] ;
d : = r ;
e n d l o o p ;
A [ d ] : = x ;
e n d ; { p r z e m i e [ w g r }
p r o c e d u r e p r z e m i e [ w d B( p : i n t e g e r ) ;
{ E l e m e n t A [ 1 ] p r z e m i e s z c z a n y j e s t w d B k o p c a .
W a r u n e k w s t p n y : k o p i e c ( 2 , p ) i p 0 .
W a r u n e k o s t a t e c z n y : k o p i e c ( 1 , p ) . }
v a r d , r : i n t e g e r ;
b e g i n
r : = 1 ;
l o o p
{ N i e z m i e n n i k : k o p i e c ( 1 , p ) z w y j t k i e m b y m o |e r e l a c j i
p o m i d z y A [ r ] i j e g o d z i e m i . 1 r p . }
d : = 2 " r ;
i f d > p t h e n
b r e a k ;
e n d i f ;
{ d j e s t d z i e c k i e m l e w y m r }
i f ( d + 1 p ) c a n d ( A [ d + 1 ] < A [ d ] ) t h e n
d : = d + 1 ;
e n d i f ;
{ d j e s t n a j m n i e j s z y m d z i e c k i e m r }
i f A [ r ] A [ d ] t h e n
b r e a k ;
e n d i f ;
z a m i a n a ( A [ r ] , A [ d ] ) ;
r : = d ;
e n d l o o p ;
e n d ; { p r z e m i e [ w d B}
3 . 2 O p e r a c j e n a k o l e j k a c h p r i o r y t e t o w y c h
1 . O p e r a c j a z e r u j
p r o c e d u r e z e r u j ;
n : = 0 ;
e n d ;
2 . O p e r a c j a w s t a w
1 2
p r o c e d u r e w s t a w ( t ) ;
b e g i n
i f n n m a x t h e n
b Bd ;
e l s e
n : = n + 1 ;
A [ n ] : = t ;
{ k o p i e c ( 1 , n - 1 ) }
p r z e m i e [ w g r ( n ) ;
{ k o p i e c ( 1 , n ) }
e n d i f ;
e n d ; { w s t a w }
3 . O p e r a c j a u s u D m i n
p r o c e d u r e u s u D m i n ( t ) ;
b e g i n
i f n < 1 t h e n
b Bd ;
e l s e
t : = A [ 1 ] ;
A [ 1 ] : = A [ n ] ;
n : = n - 1 ;
{ k o p i e c ( 2 , n ) }
p r z e m i e [ w d B( n ) ;
{ k o p i e c ( 1 , n ) }
e n d i f ;
e n d ; { u s u D m i n }
3 . 3 S o r t o w a n i e p r z e z k o p c o w a n i e
t y p e
t y p r e k o r d o w y = r e c o r d
k l u c z : t y p k l u c z a ; { T y p s k a l a r n y . }
{ P o z o s t a Be s k Ba d o w e r e k o r d u . }
e n d ;
v a r
A : a r r a y [ 1 . . n ] o f t y p r e k o r d o w y ; { S o r t o w a n a t a b l i c a . }
Z m o d y f i k o w a n a p r o c e d u r a p r z e m i e [ w d B
p r o c e d u r e p r z e m i e [ w d B( l , p : i n t e g e r ) ;
{ E l e m e n t A [ l ] p r z e m i e s z c z a n y j e s t w d B k o p c a .
W a r u n e k w s t p n y : k o p i e c ( l + 1 , p ) i l p .
W a r u n e k o s t a t e c z n y : k o p i e c ( l , p ) . }
v a r d , r : i n t e g e r ;
t : t y p r e k o r d o w y ;
b e g i n
r : = l ; t : = A [ r ] ;
l o o p
{ N i e z m i e n n i k : k o p i e c ( l , p ) z w y j t k i e m b y m o |e r e l a c j i
p o m i d z y r i j e g o d z i e m i . l r p . }
d : = 2 " r ;
i f d > p t h e n
b r e a k ;
e n d i f ;
1 3
{ d j e s t d z i e c k i e m l e w y m r . }
i f ( d < p ) c a n d ( A [ d + 1 ] . k l u c z > A [ d ] . k l u c z ) t h e n
d : = d + 1 ;
e n d i f ;
{ d j e s t n a j w i k s z y m d z i e c k i e m r . }
i f t . k l u c z A [ d ] . k l u c z t h e n
b r e a k ;
e n d i f ;
A [ r ] : = A [ d ] ;
r : = d ;
e n d l o o p ;
A [ r ] : = t ;
e n d ; { p r z e m i e [ w d B}
p r o c e d u r e s o r t o w a n i e p r z e z k o p c o w a n i e ;
{ S o r t o w a n a j e s t t a b l i c a A [ 1 . . n ] . }
v a r i : i n t e g e r ;
b e g i n
{ F a z a 1 : B u d o w a n i e k o p c a . }
f o r i : = n d i v 2 d o w n t o 1 d o
{ N i e z m i e n n i k : k o p i e c ( i + 1 , n ) . }
p r z e m i e [ w d B( i , n ) ;
{ k o p i e c ( i , n ) . }
e n d f o r ;
{ k o p i e c ( 1 , n ) . }
{ F a z a 2 : W Ba [c i w e s o r t o w a n i e . }
f o r i : = n d o w n t o 2 d o
{ N i e z m i e n n i k : k o p i e c ( 1 , i ) i p o s o r t o w a n e ( i + 1 , n )
i A [ 1 . . i ] . k l u c z A [ i + 1 . . n ] . k l u c z . }
z a m i a n a ( A [ 1 ] , A [ i ] ) ;
{ k o p i e c ( 2 , i - 1 ) i p o s o r t o w a n e ( i , n )
i A [ 1 . . i - 1 ] . k l u c z A [ i . . n ] . k l u c z . }
p r z e m i e [ w d B( 1 , i - 1 ) ;
{ k o p i e c ( 1 , i - 1 ) i p o s o r t o w a n e ( i , n )
i A [ 1 . . i - 1 ] . k l u c z A [ i . . n ] . k l u c z . }
e n d f o r ;
{ p o s o r t o w a n e ( 1 , n ) }
e n d ; { s o r t o w a n i e p r z e z k o p c o w a n i e }
4 W y s z u k i w a n i e
4 . 1 W y s z u k i w a n i e l i n i o w e
p r o c e d u r e w y s z u k i w a n i e l i n i o w e 1 ( x : t y p k l u c z a ;
v a r j e s t : B o o l e a n ;
v a r i : 1 . . n + 1 ) ;
b e g i n
i : = 1 ;
w h i l e ( i n ) c a n d ( A [ i ] . k l u c z < > x ) d o
i : = i + 1 ;
e n d w h i l e ;
j e s t : = i < > ( n + 1 ) ;
e n d ;
4 . 2 W y s z u k i w a n i e l i n i o w e z z a s t o s o w a n i e m w a r t o w n i k a
p r o c e d u r e w y s z u k i w a n i e l i n i o w e 2 ( x : t y p k l u c z a ;
1 4
v a r j e s t : B o o l e a n ;
v a r i : 1 . . n + 1 ) ;
b e g i n
A [ n + 1 ] . k l u c z : = x ; { W a r t o w n i k . }
i : = 1 ;
w h i l e A [ i ] . k l u c z < > x d o
i : = i + 1 ;
e n d w h i l e ;
j e s t : = i < > ( n + 1 ) ;
e n d ;
4 . 3 W y s z u k i w a n i e l i n i o w e w u p o r z d k o w a n e j t a b l i c y
p r o c e d u r e w y s z u k i w a n i e l i n i o w e 3 ( x : t y p k l u c z a ;
v a r j e s t : B o o l e a n ;
v a r i : 1 . . n + 1 ) ;
b e g i n
i : = 1 ;
A [ n + 1 ] . k l u c z : = "; { " > x }
w h i l e A [ i ] . k l u c z < x d o
i : = i + 1 ;
e n d w h i l e ;
j e s t : = A [ i ] . k l u c z = x ;
e n d ;
4 . 4 W y s z u k i w a n i e b i n a r n e ( l o g a r y t m i c z n e )
p r o c e d u r e w y s z u k i w a n i e b i n a r n e ( x : t y p k l u c z a ;
v a r j e s t : B o o l e a n ;
v a r m : 1 . . n ) ;
v a r l e w y , p r a w y : 0 . . n + 1 ;
b e g i n
l e w y : = 1 ;
p r a w y : = n ;
j e s t : = f a l s e ;
r e p e a t
m : = ( l e w y + p r a w y ) d i v 2 ;
i f A [ m ] . k l u c z = x t h e n
j e s t : = t r u e ;
e l s e
i f A [ m ] . k l u c z < x t h e n
l e w y : = m + 1 ;
e l s e
p r a w y : = m - 1 ;
e n d i f ;
e n d i f ;
u n t i l j e s t o r ( l e w y > p r a w y ) ;
e n d ; { w y s z u k i w a n i e b i n a r n e }
4 . 5 D r z e w a p o s z u k i w a D b i n a r n y c h
t y p e
w i e r z c h o Be k d r z e w a = r e c o r d
k l u c z : t y p k l u c z a ;
l e w y , p r a w y : w i e r z c h o Be k d r z e w a ;
e n d ;
o d s y Ba c z = w i e r z c h o Be k d r z e w a ;
1 5
p r o c e d u r e s z u k a j ( x : k l u c z ; v a r t : o d s y Ba c z ) ;
{ S z u k a n i e k l u c z a x w d r z e w i e w s k a z a n y m p r z e z t . }
v a r v : o d s y Ba c z ;
b e g i n
v : = t ;
w h i l e ( v = n i l ) c a n d ( v . k l u c z = x ) d o
i f x < v . k l u c z t h e n
v : = v . l e w y ;
e l s e
v : = v . p r a w y ;
e n d i f ;
e n d w h i l e ;
r e t u r n ( v ) ; { j e [l i v = n i l t o x n i e w y s t p u j e w d r z e w i e }
e n d ; { s z u k a j }
p r o c e d u r e w s t a w ( x : k l u c z ; v a r t : o d s y Ba c z ) ;
{ W s t a w i a n i e k l u c z a x d o d r z e w a w s k a z a n e g o p r z e z t . }
v a r v : o d s y Ba c z ;
b e g i n
v : = t ;
w h i l e ( v = n i l ) c a n d ( v . k l u c z = x ) d o { s z u k a n i a k l u c z a x }
i f x < v . k l u c z t h e n
v : = v . l e w y ;
e l s e
v : = v . p r a w y ;
e n d i f ;
e n d w h i l e ;
i f v = n i l t h e n { x j e s t w d r z e w i e }
r e t u r n ;
e l s e
W s t a w i e n i e x n a k o n i e c [c i e |k i ;
e n d i f ;
e n d ; { w s t a w }
p r o c e d u r e u s u D ( x : k l u c z ; v a r t : o d s y Ba c z ) ;
{ U s u w a n i e k l u c z a x z d r z e w a w s k a z a n e g o p r z e z t . }
v a r v , w : o d s y Ba c z ;
b e g i n
v : = t ;
w h i l e ( v = n i l ) c a n d ( v . k l u c z = x ) d o { s z u k a n i a k l u c z a x }
i f x < v . k l u c z t h e n
v : = v . l e w y ;
e l s e
v : = v . p r a w y ;
e n d i f ;
e n d w h i l e ;
i f v = n i l t h e n { x n i e w y s t p u j e w d r z e w i e }
r e t u r n ;
e l s e
i f ( v . l e w y = n i l ) o r ( v . p r a w y = n i l ) t h e n { b r a k l e w e g o l u b p r a w e g o p o d d r z e w a }
U s u D w i e r z c h o Be k v z d r z e w a ;
e l s e
w : = v . p r a w y ;
w h i l e w n i e j e s t k o Dc e m [c i e |k i w d r z e w i e d o
w : = w . l e w y ; { s z u k a n i e m i n i m a l n e g o e l e m e n t u w p r a w y m p o d d r z e w i e }
e n d w h i l e ;
1 6
W s t a w w . k l u c z d o v . k l u c z i u s u D w i e r z c h o Be k w z d r z e w a ;
e n d i f ;
e n d i f ;
e n d u s u D;
A n a l i z a w y s z u k i w a n i a w d r z e w a c h b i n a r n y c h
W y z n a c z y m y [r e d n i l i c z b p o r w n a D w y m a g a n y c h d l a w y s z u k a n i a k l u c z a w d r z e w i e
w y s z u k i w a D b i n a r n y c h . Z a k Ba d a m y , |e :
1 . D a n e j e s t n r |n y c h k l u c z y o w a r t o [c i a c h 1 , 2 , . . . , n .
2 . K l u c z e p o j a w i a j s i w l o s o w e j k o l e j n o [c i .
3 . P i e r w s z y k l u c z ( a w i c k o r z e D t w o r z o n e g o d r z e w a ) m a w a r t o [ i z p r a w d o p o d o b i e D-
s t w e m 1 / D. W w c z a s l e w e p o d d r z e w o b d z i e z a w i e r a i - 1 w i e r z c h o Bk w , a p r a w e
p o d d r z e w o n - i w i e r z c h o Bk w .
O z n a c z m y :
" P i - 1 [r e d n i a l i c z b a p o r w n a D k o n i e c z n a d o w y s z u k a n i a d o w o l n e g o k l u c z a w l e w y m
p o d d r z e w i e .
" P n - i t a s a m a w i e l k o [ d l a p r a w e g o p o d d r z e w a .
( i )
" P n [r e d n i a l i c z b a p o r w n a D w y m a g a n a d l a w y s z u k a n i a k l u c z a w d r z e w i e o n
w i e r z c h o Bk a c h i o k o r z e n i u i .
W o b e c t e g o
( i )
P n = ( P i - 1 + 1 ) p i - 1 + 1 p i + ( P n - i + 1 ) p n - i
g d z i e p i - 1 , p i i p n - i t o p r a w d o p o d o b i e Ds t w a , |e b d z i e m y s z u k a o d p o w i e d n i o k l u c z a w
l e w y m p o d d r z e w i e , k l u c z a i - t e g o , o r a z k l u c z a w p r a w y m p o d d r z e w i e . Z a k Ba d a j c , |e p r a w -
d o p o d o b i e Ds t w a s z u k a n i a p o s z c z e g l n y c h k l u c z y s r w n e , o t r z y m u j e m y :
i - 1 1 n - i
p i - 1 = , p i = , p n - i = .
n n n
W o b e c t e g o
i - 1 1 n - i
( i )
P n = ( P i - 1 + 1 ) + 1 + ( P n - i + 1 ) =
n n n
1
= [ ( P i - 1 + 1 ) ( i - 1 ) + 1 + ( P n - i + 1 ) ( n - i ) ] .
n
( i )
W i e l k o [ P n j e s t w a |n a t y l k o d l a d r z e w a o k o r z e n i u i . N a l e |y j u [r e d n i , t j . u w z g l d n i
p r z y p a d e k , |e d o w o l n y k l u c z m o |e w y s t p i w k o r z e n i u . O z n a c z m y t u [r e d n i o n w a r t o [
p r z e z P n . W w c z a s
n n
1 1 1
( i )
P n = P n = [ ( P i - 1 + 1 ) ( i - 1 ) + 1 + ( P n - i + 1 ) ( n - i ) ]
n n n
i = 1 i = 1
n
1
= [ P i - 1 ( i - 1 ) + i - 1 + 1 + P n - i ( n - i ) + n - i ]
n 2
i = 1
n
1
= 1 + [ P i - 1 ( i - 1 ) + P n - i ( n - i ) ] .
n 2
i = 1
1 7
M a m y
P i - 1 ( i - 1 ) = P i + 1 - 1 ( i + 1 - 1 ) = P i i
1 i n 0 i + 1 n 0 i n - 1
P n - i ( n - i ) = P n - n + i ( n - n + i ) = P i i
1 i n 1 n - i n 0 i n - 1
a w i c
n - 1
2
P n = 1 + i P i .
n 2
i = 0
M n o |c o b i e s t r o n y r w n a n i a p r z e z n 2 o t r z y m u j e m y
n - 1
n 2 P n = n 2 + 2 i P i . ( 1 )
i = 0
T o s a m o r w n a n i e d l a n - 1
n - 2
( n - 1 ) 2 P n - 1 = ( n - 1 ) 2 + 2 i P i . ( 2 )
i = 0
O d e j m u j c s t r o n a m i ( 1 ) i ( 2 ) o t r z y m u j e m y
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 ) + ( 2 n - 1 ) ( 3 )
Z a s t o s u j e m y m e t o d c z y n n i k a s u m a c y j n e g o [ 1 1 , s t r . 4 1 ] ( a n g . s u m m a t i o n f a c t o r m e t h o d ) ,
k t r a m w i , |e r o z w i z a n i e m r w n a n i a r e k u r e n c y j n e g o o p o s t a c i
a n T n = b n T n - 1 + c n
g d z i e a i , b i = 0 d l a i = 1 , . . . , n , j e s t
n
1
T n = ( s 1 b 1 T 0 + s k c k ) ,
a n s n
k = 1
g d z i e s n t o w Ba [n i e c z y n n i k s u m a c y j n y o w a r t o [c i
a n - 1 a n - 2 . . . a 1
s n = .
b n b n - 1 . . . b 2
R w n a n i e ( 3 ) m a p o s t a
n 2 P n = ( n + 1 ) ( n - 1 ) P n - 1 + ( 2 n - 1 )
a w i c a n = n 2 , b n = ( n + 1 ) ( n - 1 ) , c n = 2 n - 1 . W y l i c z m y w a r t o [ s n :
a n - 1 a n - 2 . . . a 1 ( n - 1 ) 2 ( n - 2 ) 2 ( n - 3 ) 2 . . . 3 2 2 2 1 2
s n = =
b n b n - 1 . . . b 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
W a r t o [ i l o c z y n u b n b n - 2 . . . b 2 j e s t ( n + 1 ) ! / / 2 , a w a r t o [ i l o c z y n u b n - 1 b n - 3 . . . b 1
j e s t ( n - 1 ) ! . W o b e c t e g o o t r z y m u j e m y
( n - 1 ) ! ( n - 1 ) ! 2
s n = = .
( n + 1 ) !
n ( n + 1 )
( n - 1 ) !
2
1 8
P o n i e w a | P 0 = 0 , t o
n n n
1 1 2 n + 1 2 k - 1
P n = s k c k = ( 2 k - 1 ) = .
2
s n a n k = 1 n 2 k ( k + 1 ) n k ( k + 1 )
n ( n + 1 )
k = 1 k = 1
2 k - 1
R o z k Ba d a j c w y r a |e n i e n a u Ba m k i p r o s t e o t r z y m u j e m y
k ( k + 1 )
2 k - 1 3 1
= - .
k ( k + 1 ) k + 1 k
W o b e c t e g o
n n n n
n + 1 1 1 n + 1 1 1 1
P n = 3 - = 3 - 3 + 3 - =
n k + 1 k n n + 1 k k
k = 1 k = 1 k = 1 k = 1
n
n + 1 3 ( 1 - n - 1 ) 1 n + 1
= + 2 = 2 H n - 3 .
n n + 1 k n
k = 1
4 . 6 H a s z o w a n i e
4 . 6 . 1 H a s z o w a n i e o t w a r t e
c o n s t a = { O d p o w i e d n i a s t a Ba . }
t y p e s Bo w o = a r r a y [ 1 . . 1 0 ] o f c h a r ;
e l e m e n t l i s t y = r e c o r d
r : s Bo w o ;
n a s t : e l e m e n t l i s t y ;
e n d ;
t y p l i s t o w y = e l e m e n t l i s t y ;
s Bo w n i k = a r r a y [ 0 . . a - 1 ] o f t y p l i s t o w y ;
F u n k c j a h a s z u j c a
f u n c t i o n h ( x : s Bo w o ) : 0 . . a - 1 ;
v a r i , s u m a : i n t e g e r ;
b e g i n
s u m a : = 0 ;
f o r i : = 1 t o 1 0 d o
s u m a : = s u m a + o r d ( x [ i ] ) ;
e n d f o r ;
r e t u r n ( s u m a m o d a ) ;
e n d ;
P r o c e d u r y o p e r u j c e n a s Bo w n i k u
p r o c e d u r e Z E R U J ( v a r A : s Bo w n i k ) ;
v a r i : i n t e g e r ;
b e g i n
f o r i : = 0 t o a - 1 d o
A [ i ] : = n i l ;
e n d f o r ;
e n d ;
f u n c t i o n J E S T ( x : s Bo w o ; v a r A : s Bo w n i k ) : B o o l e a n ;
v a r b i e |c y : t y p l i s t o w y ;
b e g i n
b i e |c y : = A [ h ( x ) ] ;
1 9
w h i l e b i e |c y < > n i l d o
i f b i e |c y . r = x t h e n
r e t u r n ( t r u e ) ; { S Bo w o z n a l e z i o n o . }
e l s e
b i e |c y : = b i e |c y . n a s t ;
e n d ;
e n d w h i l e ;
r e t u r n ( f a l s e ) ; { S Bo w a n i e z n a l e z i o n o . }
e n d ;
p r o c e d u r e W S T A W ( x : s Bo w o ; v a r A : s Bo w n i k ) ;
v a r k u b e Be k : 0 . . a - 1 ;
s t a r a g Bo w a : t y p l i s t o w y ;
b e g i n
i f n o t J E S T ( x , A ) t h e n
k u b e Be k : = h ( x ) ;
s t a r a g Bo w a : = A [ k u b e Be k ] ;
n e w ( A [ k u b e Be k ] ) ;
A [ k u b e Be k ] . r : = x ;
A [ k u b e Be k ] . n a s t : = s t a r a g Bo w a ;
e n d i f ;
e n d ;
p r o c e d u r e U S U C ( x : s Bo w o ; v a r A : s Bo w n i k ) ;
v a r b i e |c y : t y p l i s t o w y ;
k u b e Be k : 0 . . a - 1 ;
b e g i n
k u b e Be k : = h ( x ) ;
i f A [ k u b e Be k ] < > n i l t h e n
i f A [ k u b e Be k ] . r = x t h e n
{ S Bo w o x j e s t w p i e r w s z y m e l e m e n c i e . }
A [ k u b e Be k ] : = A [ k u b e Be k ] . n a s t ; { U s u n i c i e s Bo w a
z l i s t y . }
e l s e
{ S Bo w o x , j e [l i w y s t p u j e , n i e j e s t z a w a r t e
w p i e r w s z y m e l e m e n c i e . }
b i e |c y : = A [ k u b e Be k ] ; { Z m i e n n a b i e |c y w s k a z u j e
n a p o p r z e d n i e l e m e n t . }
w h i l e b i e |c y . n a s t < > n i l d o
i f b i e |c y . n a s t . r = x t h e n
{ U s u n i c i e s Bo w a z l i s t y . }
b i e |c y . n a s t : = b i e |c y . n a s t . n a s t ;
r e t u r n ; { W y j [c i e z p r o c e d u r y . }
e l s e
{ S Bo w a x j e s z c z e n i e z n a l e z i o n o . }
b i e |c y : = b i e |c y . n a s t ;
e n d i f ;
e n d w h i l e ;
e n d i f ;
e n d i f ;
e n d ;
R o z k Ba d k l u c z y w t a b l i c y
2 0
i A 0
i + 1 A 1
i + 2 A 2
i + 3 A 3
i + 4 A 4
i + 5 A 5
i + 6 A 6
i + 7 A 7
i + 8 A 8
i + 9 A 9
. . . . . .
j A 1 0
j + 1 A 1 1 A 2 0
j + 2 A 1 2 A 2 1 A 3 0
j + 3 A 1 3 A 2 2 A 3 1 A 4 0
j + 4 A 1 4 A 2 3 A 3 2 A 4 1 A 5 0
j + 5 A 1 5 A 2 4 A 3 3 A 4 2 A 5 1 A 6 0
j + 6 A 1 6 A 2 5 A 3 4 A 4 3 A 5 2 A 6 1 A 7 0
j + 7 A 1 7 A 2 6 A 3 5 A 4 4 A 5 3 A 6 2 A 7 1 A 8 0
j + 8 A 1 8 A 2 7 A 3 6 A 4 5 A 5 4 A 6 3 A 7 2 A 8 1 A 9 0
j + 9 A 1 9 A 2 8 A 3 7 A 4 6 A 5 5 A 6 4 A 7 3 A 8 2 A 9 1
j + 1 0 A 2 9 A 3 8 A 4 7 A 5 6 A 6 5 A 7 4 A 8 3 A 9 2
j + 1 1 A 3 9 A 4 8 A 5 7 A 6 6 A 7 5 A 8 4 A 9 3
j + 1 2 A 4 9 A 5 8 A 6 7 A 7 6 A 8 5 A 9 4
j + 1 3 A 5 9 A 6 8 A 7 7 A 8 6 A 9 5
j + 1 4 A 6 9 A 7 8 A 8 7 A 9 6
j + 1 5 A 7 9 A 8 8 A 9 7
j + 1 6 A 8 9 A 9 8
j + 1 7 A 9 9
4 . 6 . 2 H a s z o w a n i e z a m k n i t e
c o n s t p u s t e = ; { 1 0 o d s t p w }
u s u n i t e = " " " " " " " " " " ; { 1 0 g w i a z d e k }
t y p e s Bo w o = p a c k e d a r r a y [ 1 . . 1 0 ] o f c h a r ;
s Bo w n i k = a r r a y [ 0 . . a - 1 ] o f s Bo w o ;
p r o c e d u r e Z E R U J ( v a r A : s Bo w n i k ) ;
v a r i : i n t e g e r ;
b e g i n
f o r i : = 0 t o a - 1 d o
A [ i ] : = p u s t e ;
e n d f o r ;
e n d ;
f u n c t i o n s z u k a j ( x : s Bo w o ; v a r A : s Bo w n i k ) : i n t e g e r ;
{ P r z e s z u k i w a n a j e s t t a b l i c a A p o c z y n a j c o d k u b e Bk a
h 0 ( x ) d o m o m e n t u , g d y x z o s t a j e z n a l e z i o n e a l b o
z o s t a j e z n a l e z i o n y k u b e Be k p u s t y a l b o t e | c a Ba t a b l i c a
z o s t a n i e p r z e s z u k a n a . W a r t o [c i f u n k c j i j e s t n u m e r
k u b e Bk a , n a k t r y m s z u k a n i e z o s t a j e z a k o Dc z o n e ,
w s k u t e k j e d n e g o z w y m i e n i o n y c h w y |e j p o w o d w . }
v a r p o c z , i : i n t e g e r ;
{ Z m i e n n a p o c z p r z e c h o w u j e w a r t o [ h 0 ( x ) ;
z m i e n n a i z a w i e r a l i c z b d o t y c h c z a s p r z e s z u k a n y c h
2 1
k u b e Bk w . }
b e g i n
p o c z : = h 0 ( x ) ;
i : = 0 ;
w h i l e ( i < a ) a n d ( A [ ( p o c z + i ) m o d a ] < > x ) a n d
( A [ ( p o c z + i ) m o d a ] < > p u s t e ) d o
i : = i + 1 ;
e n d w h i l e ;
r e t u r n ( ( p o c z + i ) m o d a ) ;
e n d ;
f u n c t i o n s z u k a j 1 ( x : s Bo w o ; v a r A : s Bo w n i k ) : i n t e g e r ;
{ D z i a Ba n i e p o d o b n e d o f u n k c j i s z u k a j , z t r |n i c ,
|e p r z e s z u k i w a n i e t a b l i c y A z o s t a j e t a k |e z a k o Dc z o n e
p o n a p o t k a n i u k u b e Bk a z w a r t o [c i u s u n i t e . }
f u n c t i o n J E S T ( x : s Bo w o ; v a r A : s Bo w n i k ) : B o o l e a n ;
b e g i n
i f A [ s z u k a j ( x , A ) ] = x t h e n
r e t u r n ( t r u e ) ;
e l s e
r e t u r n ( f a l s e ) ;
e n d i f ;
e n d ;
p r o c e d u r e W S T A W ( x : s Bo w o ; v a r A : s Bo w n i k ) ;
v a r k u b e Be k : 0 . . a - 1 ;
b e g i n
i f A [ s z u k a j ( x , A ) ] = x t h e n
r e t u r n ; { x j e s t w t a b l i c y . }
e n d i f ;
k u b e Be k : = s z u k a j 1 ( x , A ) ;
i f ( A [ k u b e Be k ] = p u s t e ) o r ( A [ k u b e Be k ] = u s u n i t e ) t h e n
A [ k u b e Be k ] : = x ;
e l s e
b Bd ( b Bd w p r o c e d u r z e W S T A W : t a b l i c a j e s t p e Bn a ) ;
e n d i f ;
e n d ;
p r o c e d u r e U S U C ( x : s Bo w o ; v a r A : s Bo w n i k ) ;
v a r k u b e Be k : 0 . . a - 1 ;
b e g i n
k u b e Be k : = s z u k a j ( x , A ) ;
i f A [ k u b e Be k ] = x t h e n
A [ k u b e Be k ] : = u s u n i t e ;
e n d i f ;
e n d ;
4 . 7 M i n i m a l n e , d o s k o n a Be f u n k c j e h a s z u j c e
1 . N i e c h d a n y b d z i e z b i r s k r t w a n g i e l s k i c h n a z w m i e s i c y W = { J U N , S E P , D E C , A U G ,
J A N , F E B , J U L , A P R , O C T , M A Y , M A R , N O V }
W a r t o [c i l i c z b o w e p r z y p o r z d k o w a n e p o s z c z e g l n y m l i t e r o m :
2 2
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
J e |e l i n a z w k a |d e g o m i e s i c a u w a |a z a c i g t r z e c h l i t e r x 1 x 2 x 3 , t o m i n i m a l n a , d o s k o n a Ba
f u n k c j a h a s z u j c a m a p o s t a :
h d ( x 1 x 2 x 3 ) = l i c z b a p r z y p o r z d k o w a n a l i t e r z e x 2 +
l i c z b a p r z y p o r z d k o w a n a l i t e r z e x 3
h d ( J U N ) = 0
h d ( S E P ) = 1
h d ( D E C ) = 2
. . .
h d ( N O V ) = 1 1
2 . N i e c h d a n y b d z i e z b i r s B w z a s t r z e |o n y c h j z y k a P a s c a l W = { D O , E N D , E L S E , C A S E ,
D O W N T O , G O T O , T O , O T H E R W I S E , T Y P E , W H I L E , C O N S T , D I V , A N D , S E T , O R ,
O F , M O D , F I L E , R E C O R D , P A C K E D , N O T , T H E N , P R O C E D U R E , W I T H , R E P E A T ,
V A R , I N , A R R A Y , I F , N I L , F O R , B E G I N , U N T I L , L A B E L , F U N C T I O N , P R O G R A M } ,
c a r d ( W ) = 3 6 .
W a r t o [c i l i c z b o w e p r z y p o r z d k o w a n e p o s z c z e g l n y m l i t e r o m :
A B C D E F G H I J K L M N O P Q R
1 1 1 5 1 0 0 1 5 3 1 5 1 3 0 0 1 5 1 5 1 3 0 1 5 0 1 4
S T U V W X Y Z
6 6 1 4 1 0 6 0 1 3 0
h d ( x 1 x 2 . . . x n ) = d Bu g o [ s Bo w a n +
l i c z b a p r z y p o r z d k o w a n a l i t e r z e x 1 +
l i c z b a p r z y p o r z d k o w a n a l i t e r z e x n
N p . :
h d ( D O ) = 2 + 0 + 0 = 2
h d ( P R O G R A M ) = 7 + 1 5 + 1 5 = 3 7
W a r t o [c i h d d l a s B w D O . . P R O G R A M s z z a k r e s u 2 . . 3 7 . F u n k c j a j e s t w i c d o s k o n a Ba a l e
n i e m i n i m a l n a .
3 . M i n i m a l n a , d o s k o n a Ba f u n k c j a h a s z u j c a d l a s B w z a s t r z e |o n y c h j z y k a P a s c a l 6 0 0 0
s Bo w a :
v a r w : a r r a y [ 1 . . N ] o f c h a r ; { W = { w 1 , w 2 , . . . w N } }
h d ( w ) = ( h 0 ( w ) + g % h 1 ( w ) + g % h 2 ( w ) ) m o d N
N = c a r d ( W )
h 0 ( w ) = d Bu g o [( w ) + ( o r d ( w [ i ] ) , i : = 1 d o d Bu g o [( w )
z k r o k i e m 3 )
h 1 ( w ) = ( o r d ( w [ i ] ) , i : = 1 d o d Bu g o [( w ) z k r o k i e m 2 ) m o d 1 6
h 2 ( w ) = ( ( o r d ( w [ i ] ) , i : = 2 d o d Bu g o [( w ) z k r o k i e m 2 ) m o d 1 6 ) + 1 6
g f u n k c j a z a d a n a z a p o m o c t a b l i c y
P r z y j t o k o d E B C D I C :
2 3
o r d ( A ) = 1 9 3 , o r d ( B ) = 1 9 4 , . . . , o r d ( I ) = 2 0 1 ;
o r d ( J ) = 2 0 9 , o r d ( K ) = 2 1 0 , . . . , o r d ( R ) = 2 1 7 ;
o r d ( S ) = 2 2 6 , o r d ( T ) = 2 2 7 , . . . , o r d ( Z ) = 2 3 3 ;
Z b i r s B w z a s t r z e |o n y c h j z y k a P a s c a l 6 0 0 0 ( c a r d ( W ) = 3 6 ) :
W = { A N D , A R R A Y , B E G I N , C A S E , C O N S T , D I V , D O , D O W N T O , E L S E , E N D ,
F I L E , F O R , F U N C T I O N , G O T O , I F , I N , L A B E L , M O D , N I L , N O T , O F ,
O R , P A C K E D , P R O C E D U R E , P R O G R A M , R E C O R D , R E P E A T , S E G M E N T E D ,
S E T , T H E N , T O , T Y P E , U N T I L , V A R , W H I L E , W I T H }
i g ( i ) i g ( i ) i g ( i ) i g ( i )
0 0 9 1 2 1 8 0 2 7 2 8
1 0 1 0 1 6 1 9 3 0 2 8 2 8
2 0 1 1 2 2 2 0 0 2 9 3
3 3 1 1 2 0 2 1 2 4 3 0 2 6
4 1 2 1 3 1 6 2 2 2 5 3 1 3 0
5 1 2 1 4 1 6 2 3 3 5
6 1 5 1 5 1 1 2 4 1 5
7 3 3 1 6 0 2 5 2 7
8 1 1 1 7 2 9 2 6 3
h d ( N O T ) = 0
h d ( M O D ) = 3 5
5 O p e r a c j e n a t e k s t a c h
t e k s t : a r r a y [ 1 . . n ] o f c h a r ;
w z o r z e c : a r r a y [ 1 . . m ] o f c h a r ;
{ Z w y k l e z a c h o d z i 1 m n . }
5 . 1 W y s z u k i w a n i e n a i w n e
f u n c t i o n w y s z u k i w a n i e n a i w n e : i n t e g e r ;
v a r i , j : i n t e g e r ;
b e g i n
i : = 1 ;
j : = 1 ;
r e p e a t
i f t e k s t [ i ] = w z o r z e c [ j ] t h e n
i : = i + 1 ;
j : = j + 1 ;
e l s e
i : = i - j + 2 ;
j : = 1 ;
e n d i f ;
u n t i l ( j > m ) o r ( i > n ) ;
i f j > m t h e n
r e t u r n ( i - m ) ;
e l s e
r e t u r n ( i ) ; { W z o r c a n i e z n a l e z i o n o ( i = n + 1 ) . }
e n d i f ;
e n d ;
2 4
5 . 2 A l g o r y t m K n u t h a , M o r r i s a i P r a t t a ( K M P )
f u n c t i o n w y s z u k i w a n i e K M P : i n t e g e r ;
v a r i , j : i n t e g e r ;
b e g i n
i : = 1 ;
j : = 1 ;
r e p e a t
i f ( j = 0 ) c o r ( t e k s t [ i ] = w z o r z e c [ j ] ) t h e n
i : = i + 1 ;
j : = j + 1 ;
e l s e
j : = n a s t [ j ] ;
e n d i f ;
u n t i l ( j > m ) o r ( i > n ) ;
i f j > m t h e n
r e t u r n ( i - m ) ;
e l s e
r e t u r n ( i ) ;
e n d i f ;
e n d ;
p r o c e d u r e i n i c j a c j a n a s t ;
v a r i , j : i n t e g e r ;
b e g i n
i : = 1 ;
j : = 0 ;
n a s t [ 1 ] : = 0 ;
r e p e a t
i f ( j = 0 ) o r ( w z o r z e c [ i ] = w z o r z e c [ j ] ) t h e n
i : = i + 1 ;
j : = j + 1 ;
n a s t [ i ] : = j ;
e l s e
j : = n a s t [ j ] ;
e n d i f ;
u n t i l i > m ;
e n d ;
A l g o r y t m w y s z u k i w a n i a K M P z w b u d o w a n y m w z o r c e m 1 0 1 0 0 1 1 1
i : = 0 ;
0 : i : = i + 1 ;
1 : i f t e k s t [ i ] < > 1 t h e n g o t o 0 ; i : = i + 1 ;
2 : i f t e k s t [ i ] < > 0 t h e n g o t o 1 ; i : = i + 1 ;
3 : i f t e k s t [ i ] < > 1 t h e n g o t o 1 ; i : = i + 1 ;
4 : i f t e k s t [ i ] < > 0 t h e n g o t o 2 ; i : = i + 1 ;
5 : i f t e k s t [ i ] < > 0 t h e n g o t o 3 ; i : = i + 1 ;
6 : i f t e k s t [ i ] < > 1 t h e n g o t o 1 ; i : = i + 1 ;
7 : i f t e k s t [ i ] < > 1 t h e n g o t o 2 ; i : = i + 1 ;
8 : i f t e k s t [ i ] < > 1 t h e n g o t o 2 ; i : = i + 1 ;
i f i > n + 1 t h e n
r e t u r n ( n + 1 ) ;
e l s e
r e t u r n ( i - 8 ) ;
e n d i f ;
2 5
5 . 3 W y s z u k i w a n i e n i e z g o d n o [c i o w e
t y p e z n a k = ( , A , B , . . . , Z ) ;
v a r s k o k 1 : a r r a y [ z n a k ] o f i n t e g e r ;
f u n c t i o n w y s z u k i w a n i e n i e z g o d n o [c i o w e : i n t e g e r ;
v a r i , j : i n t e g e r ;
b e g i n
i : = m ;
j : = m ;
r e p e a t
i f t e k s t [ i ] = w z o r z e c [ j ] t h e n
i : = i - 1 ;
j : = j - 1 ;
e l s e
i : = i + s k o k 1 [ t e k s t [ i ] ] ;
j : = m ;
e n d i f ;
u n t i l ( j < 1 ) o r ( i > n ) ;
i f j < 1 t h e n
r e t u r n ( i + 1 ) ;
e l s e
r e t u r n ( n + 1 ) ;
e n d i f ;
e n d ;
p r o c e d u r e i n i c j a c j a s k o k 1 ;
v a r j : z n a k ;
k : i n t e g e r ;
b e g i n
f o r j : = t o Z d o
s k o k 1 [ j ] : = m ;
e n d f o r ;
f o r k : = 1 t o m d o
s k o k 1 [ w z o r z e c [ k ] ] : = m - k ;
e n d f o r ;
e n d ;
M o d y f i k a c j a i n s t u k c j i r e p e a t w a l g o r y t m i e w y s z u k i w a n i a n i e z g o d n o [c i o w e g o
r e p e a t
i f t e k s t [ i ] = w z o r z e c [ j ] t h e n
i : = i - 1 ;
j : = j - 1 ;
e l s e
i : = i + m a x ( s k o k 1 [ t e k s t [ i ] ] , s k o k 2 [ j ] ) ;
j : = m ;
e n d i f ;
u n t i l ( j < 1 ) o r ( i > n ) ;
5 . 4 A l g o r y t m B o y e r a i M o o r a ( B M )
p r o c e d u r e w y s z u k i w a n i e B M ;
v a r d u |y : i n t e g e r : = n + m ; { O g l n i e w i n n o z a c h o d z i :
d u |y n + m . }
i , j , k : i n t e g e r ;
b e g i n
{ m n }
2 6
i : = m ;
l o o p
r e p e a t
i : = i + s k o k 1 [ t e k s t [ i ] ] ;
u n t i l i > n ;
i f i d u |y t h e n
r e t u r n ( n + 1 ) ; { W z o r c a n i e z n a l e z i o n o . }
e n d i f ;
{ Z a c h o d z i : t e k s t [ i - d u |y ] = w z o r z e c [ m ] . }
i : = ( i - d u |y ) - 1 ;
j : = m - 1 ;
l o o p
i f j = 0 t h e n
r e t u r n ( i + 1 ) ; { W z o r z e c z n a l e z i o n o . }
e n d i f ;
i f t e k s t [ i ] = w z o r z e c [ j ] t h e n
i : = i - 1 ;
j : = j - 1 ;
e l s e
b r e a k ;
e n d i f ;
e n d l o o p ;
k : = s k o k 1 [ t e k s t [ i ] ] ;
i f k = d u |y t h e n
i : = i + s k o k 2 [ j ] ;
e l s e
i : = i + m a x ( k , s k o k 2 [ j ] ) ;
e n d i f ;
e n d l o o p ;
e n d ;
6 S o r t o w a n i e
t y p e
t y p r e k o r d u = r e c o r d
k l u c z : t y p k l u c z a ; { W z b i o r z e w a r t o [c i t y p u t y p k l u c z a m u s i b y
z d e f i n i o w a n a r e l a c j a l i n i o w e g o p o r z d k u . }
e n d ;
i n d e k s = 0 . . n ;
v a r
A : a r r a y [ 1 . . n ] o f t y p r e k o r d u ; { T a b l i c a p o d l e g a j c a s o r t o w a n i u . }
6 . 1 S o r t o w a n i e p r z e z p r o s t e w s t a w i a n i e
2 7
k l u c z e p o c z t k o w e
4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7
i = 2 4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7
i = 3 1 2 4 4 5 5 4 2 9 4 1 8 0 6 6 7
i = 4 1 2 4 2 4 4 5 5 9 4 1 8 0 6 6 7
i = 5 1 2 4 2 4 4 5 5 9 4 1 8 0 6 6 7
i = 6 1 2 1 8 4 2 4 4 5 5 9 4 0 6 6 7
i = 7 0 6 1 2 1 8 4 2 4 4 5 5 9 4 6 7
i = 8 0 6 1 2 1 8 4 2 4 4 5 5 6 7 9 4
A b s t r a k c y j n y z a p i s a l g o r y t m u
f o r i : = 2 t o n d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
x : = A [ i ] ;
W s t a w x w o d p o w i e d n i m m i e j s c u w A [ 1 . . i - 1 ] ;
e n d f o r ;
p r o c e d u r e p r o s t e w s t a w i a n i e 1 ;
v a r
i , j : i n d e k s ;
x : t y p r e k o r d u ;
b e g i n
f o r i : = 2 t o n d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
x : = A [ i ] ;
j : = i - 1 ;
w h i l e ( j > 0 ) c a n d ( x . k l u c z < A [ j ] . k l u c z ) d o
A [ j + 1 ] : = A [ j ] ;
j : = j - 1 ;
e n d w h i l e ;
A [ j + 1 ] : = x ;
e n d f o r ;
e n d ;
p r o c e d u r e p r o s t e w s t a w i a n i e 2 ;
v a r
i , j : i n d e k s ;
x : t y p r e k o r d u ;
b e g i n
f o r i : = 2 t o n d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
x : = A [ i ] ;
A [ 0 ] : = x ; { U s t a w i e n i e w a r t o w n i k a . }
j : = i - 1 ;
w h i l e x . k l u c z < A [ j ] . k l u c z d o
2 8
A [ j + 1 ] : = A [ j ] ;
j : = j - 1 ;
e n d w h i l e ;
A [ j + 1 ] : = x ;
e n d f o r ;
e n d ;
N i e c o l e p s z e u s t a w i e n i e w a r t o w n i k a
.
.
.
b e g i n
{ A [ 0 ] . k l u c z : = - "; }
f o r i : = 2 t o n d o
{ N i e z m i e n n i k : . . . }
x : = A [ i ] ;
j : = i - 1 ;
w h i l e . . .
.
.
.
p r o c e d u r e p o B w k o w e w s t a w i a n i e ;
v a r
i , j , l , m , p : i n d e k s ;
x : t y p r e k o r d u ;
b e g i n
f o r i : = 2 t o n d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
x : = A [ i ] ;
l : = 1 ;
p : = i - 1 ;
w h i l e l p d o
m : = ( l + p ) d i v 2 ;
i f x . k l u c z < A [ m ] . k l u c z t h e n
p : = m - 1 ;
e l s e
l : = m + 1 ;
e n d i f ;
e n d w h i l e ;
f o r j : = i - 1 d o w n t o l d o
A [ j + 1 ] : = A [ j ] ;
e n d f o r ;
A [ l ] : = x ;
e n d f o r ;
e n d ;
6 . 2 A l g o r y t m S h e l l a , c z y l i s o r t o w a n i e z a p o m o c m a l e j c y c h p r z y -
r o s t w
t y p e
i n d e k s : - h [ 1 ] . . n ;
v a r
A : a r r a y [ - h [ 1 ] + 1 . . n ] o f t y p r e k o r d u ;
p r o c e d u r e s o r t o w a n i e S h e l l a ;
c o n s t
t = 4 ;
v a r
m : 1 . . t ;
2 9
i , j , k , w : i n d e k s ;
h : a r r a y [ 1 . . t ] o f i n t e g e r ; { T a b l i c a p r z y r o s t w . }
x : t y p r e k o r d u ;
b e g i n
h [ 1 ] : = 4 0 ; h [ 2 ] : = 1 3 ; h [ 3 ] : = 4 ; h [ 4 ] : = 1 ;
f o r m : = 1 t o 4 d o
k : = h [ m ] ;
w : = - k ; { M i e j s c e w a r t o w n i k a . }
f o r i : = k + 1 t o n d o
x : = A [ i ] ;
i f w = 0 t h e n
w : = - k ;
e n d i f ;
w : = w + 1 ;
A [ w ] : = x ; { U s t a w i e n i e w a r t o w n i k a . }
j : = i - k ;
w h i l e x . k l u c z < A [ j ] . k l u c z d o
A [ j + k ] : = A [ j ] ;
j : = j - k ;
e n d w h i l e ;
A [ j + k ] : = x ;
e n d f o r ;
e n d f o r ;
e n d ;
P r o s t a w e r s j a s o r t o w a n i a S h e l l a
p r o c e d u r e s o r t o w a n i e S h e l l a 1 ;
v a r
i , j , p r z y r : i n t e g e r ;
x : t y p r e k o r d u ;
b e g i n
p r z y r : = n d i v 2 ;
w h i l e p r z y r > 0 d o
f o r i : = p r z y r + 1 t o n d o
j : = i - p r z y r ;
w h i l e j > 0 d o
i f A [ j ] . k l u c z > A [ j + p r z y r ] . k l u c z t h e n
z a m i a n a ( A [ j ] , A [ j + p r z y r ] ) ;
j : = j - p r z y r ;
e l s e
j : = 0 ; { W y j [c i e z p t l i . }
e n d i f ;
e n d w h i l e ;
e n d f o r ;
p r z y r : = p r z y r d i v 2 ;
e n d w h i l e ;
e n d ;
6 . 3 S o r t o w a n i e p r z e z p r o s t e w y b i e r a n i e
3 0
4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7
0 6 5 5 1 2 4 2 9 4 1 8 4 4 6 7
0 6 1 2 5 5 4 2 9 4 1 8 4 4 6 7
0 6 1 2 1 8 4 2 9 4 5 5 4 4 6 7
0 6 1 2 1 8 4 2 9 4 5 5 4 4 6 7
0 6 1 2 1 8 4 2 4 4 5 5 9 4 6 7
0 6 1 2 1 8 4 2 4 4 5 5 9 4 6 7
0 6 1 2 1 8 4 2 4 4 5 5 6 7 9 4
f o r i : = 1 t o n - 1 d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
P r z y p i s z z m i e n n e j k i n d e k s r e k o r d u o n a j m n i e j s z y m k l u c z u
s p o [r d r e k o r d w A [ i . . n ] ;
W y m i e D A [ i ] z A [ k ] ;
e n d f o r ;
p r o c e d u r e p r o s t e w y b i e r a n i e ;
v a r
i , j , k : i n d e k s ;
x : t y p r e k o r d u ;
b e g i n
f o r i : = 1 t o n - 1 d o
{ N i e z m i e n n i k : A [ 1 . . i - 1 ] j e s t p o s o r t o w a n e . }
k : = i ;
x : = A [ i ] ;
f o r j : = i + 1 t o n d o
i f A [ j ] . k l u c z < x . k l u c z t h e n
k : = j ;
x : = A [ j ] ;
e n d i f ;
e n d f o r ;
A [ k ] : = A [ i ] ;
A [ i ] : = x ;
e n d f o r ;
e n d ;
p r o c e d u r e s o r t o w a n i e p r z e z w y b i e r a n i e 2 ;
v a r
i , j , k , m , M , p , q : 1 . . n ;
m i n , M a x : t y p r e k o r d u ;
b e g i n
i : = 1 ;
j : = n ;
w h i l e i < j d o
3 1
m i n : = M a x : = A [ j ] ; { m i M s w s k a zn i k a m i , }
m : = M : = j ; { o d p o w i e d n i o , e l e m e n t u }
k : = i ; { m i n i m a l n e g o i m a k s y m a l n e g o . }
r e p e a t
i f A [ k ] . k l u c z A [ k + 1 ] . k l u c z t h e n
p : = k ;
q : = k + 1 ;
e l s e
p : = k + 1 ;
q : = k ;
e n d i f ;
i f A [ p ] . k l u c z < m i n . k l u c z t h e n
m i n : = A [ p ] ;
m : = p ;
e n d i f ;
i f A [ q ] . k l u c z > M a x . k l u c z t h e n
M a x : = A [ q ] ;
M : = q ;
e n d i f ;
k : = k + 2 ;
u n t i l k j ;
i f M = i t h e n
A [ m ] : = A [ j ] ;
e l s e
A [ m ] : = A [ i ] ;
A [ M ] : = A [ j ] ;
e n d i f ;
A [ i ] : = m i n ;
A [ j ] : = M a x ;
i : = i + 1 ;
j : = j - 1 ;
e n d w h i l e ;
e n d ;
f o r i : = n d o w n t o 2 d o
{ N i e z m i e n n i k : A [ i + 1 . . n ] j e s t p o s o r t o w a n e . }
P r z y p i s z z m i e n n e j k i n d e k s r e k o r d u o n a j w i k s z y m k l u c z u
s p o [r d r e k o r d w A [ 1 . . i ] ;
W y m i e D A [ i ] z A [ k ] ;
e n d f o r ;
6 . 4 S o r t o w a n i e p r z e z p r o s t a z a m i a n
3 2
n u m e r p r z e j [c i a
k l u c z e
p o c z t k o w e
k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7
4 4 0 6 0 6 0 6 0 6 0 6 0 6 0 6
5 5 4 4 1 2 1 2 1 2 1 2 1 2 1 2
1 2 5 5 4 4 1 8 1 8 1 8 1 8 1 8
4 2 1 2 5 5 4 4 4 2 4 2 4 2 4 2
9 4 4 2 1 8 5 5 4 4 4 4 4 4 4 4
1 8 9 4 4 2 4 2 5 5 5 5 5 5 5 5
0 6 1 8 9 4 6 7 6 7 6 7 6 7 6 7
6 7 6 7 6 7 9 4 9 4 9 4 9 4 9 4
p r o c e d u r e s o r t o w a n i e b b e l k o w e ;
v a r
i , j : i n d e k s ;
t : t y p r e k o r d u ;
b e g i n
f o r i : = 2 t o n d o
f o r j : = n d o w n t o i d o
i f A [ j ] . k l u c z < A [ j - 1 ] . k l u c z t h e n
t : = A [ j ] ;
A [ j ] : = A [ j - 1 ] ;
A [ j - 1 ] : = t ;
e n d i f ;
e n d f o r ;
e n d f o r ;
e n d ;
p r o c e d u r e s o r t o w a n i e m i e s z a n e ;
v a r
j , k , l , p : i n d e k s ;
t : t y p r e k o r d u ;
b e g i n
l : = 2 ;
p : = n ;
k : = n ; { P o z y c j a o s t a t n i e j z a m i a n y . }
r e p e a t
f o r j : = p d o w n t o l d o
i f A [ j ] . k l u c z < A [ j - 1 ] . k l u c z t h e n
t : = A [ j ] ;
A [ j ] : = A [ j - 1 ] ;
A [ j - 1 ] : = t ;
k : = j ;
e n d i f ;
e n d f o r ;
l : = k + 1 ;
3 3
f o r j : = l t o p d o
i f A [ j ] . k l u c z < A [ j - 1 ] . k l u c z t h e n
t : = A [ j ] ;
A [ j ] : = A [ j - 1 ] ;
A [ j - 1 ] : = t ;
k : = j ;
e n d i f ;
e n d f o r ;
p : = k - 1 ;
u n t i l l > p ;
e n d ;
6 . 5 S o r t o w a n i e s z y b k i e a l g o r y t m Q u i c k s o r t
p r o c e d u r e Q u i c k s o r t ( i , j : i n t e g e r ) ;
1 . i f A [ i ] d o A [ j ] z a w i e r a j c o n a j m n i e j d w a r |n e k l u c z e t h e n
2 . N i e c h v b d z i e w i k s z y m z d w c h r |n y c h k l u c z y n a j b a r d z i e j
n a l e w o p o Bo |o n y c h w c i g u ;
3 . D o k o n a p e r m u t a c j i A [ i ] , . . . , A [ j ] t a k , |e d l a p e w n e g o k " [ i + 1 , j ]
p o d c i g A [ i ] , . . . , A [ k - 1 ] s k Ba d a s i z k l u c z y m n i e j s z y c h o d v ,
a p o d c i g A [ k ] , . . . , A [ j ] z k l u c z y w i k s z y c h l u b r w n y c h v ;
4 . Q u i c k s o r t ( i , k - 1 ) ;
5 . Q u i c k s o r t ( k , j ) ;
6 . e n d i f ;
f u n c t i o n z n a j d z k l u c z o s i o w y ( i , j : i n t e g e r ) : i n t e g e r ;
{ W a r t o [c i f u n k c j i j e s t i n d e k s w i k s z e g o z d w c h n a j b a r d z i e j n a l e w o p o Bo |o n y c h ,
r |n y c h k l u c z y c i g u A [ i ] , . . . , A [ j ] ,
b d z 0 , g d y c i g s k Ba d a s i z i d e n t y c z n y c h k l u c z y . }
v a r
p i e r w s z y : t y p k l u c z a ;
k : i n t e g e r ;
b e g i n
p i e r w s z y : = A [ i ] . k l u c z ;
f o r k : = i + 1 t o j d o
i f A [ k ] . k l u c z > p i e r w s z y t h e n
r e t u r n ( k ) ;
e l s e
i f A [ k ] . k l u c z < p i e r w s z y t h e n
r e t u r n ( i ) ;
e n d i f ;
e n d i f ;
e n d f o r ;
r e t u r n ( 0 ) ; { N i e z n a l e z i o n o r |n y c h k l u c z y . }
e n d ;
f u n c t i o n p o d z i a B( i , j : i n t e g e r ; k l u c z o s i o w y : t y p k l u c z a ) : i n t e g e r ;
{ D o k o n u j e s i p o d z i a Bu c i g u A [ i ] , . . . , A [ j ] t a k , |e k l u c z e < k l u c z o s i o w y
z n a j d s i p o l e w e j s t r o n i e , a k l u c z e k l u c z o s i o w y p o p r a w e j s t r o n i e c i g u .
W a r t o [c i f u n k c j i j e s t p o c z t e k p r a w e j g r u p y k l u c z y . }
v a r
l , p : i n t e g e r ;
b e g i n
3 4
l : = i ;
p : = j ;
r e p e a t
z a m i a n a ( A [ l ] , A [ p ] ) ;
w h i l e A [ l ] . k l u c z < k l u c z o s i o w y d o
l : = l + 1 ;
e n d w h i l e ;
w h i l e A [ p ] . k l u c z k l u c z o s i o w y d o
p : = p - 1 ;
e n d w h i l e ;
u n t i l l > p ;
r e t u r n ( l ) ;
e n d ;
p r o c e d u r e Q u i c k s o r t ( i , j : i n t e g e r ) ;
{ S o r t o w a n a j e s t t a b l i c a A [ i ] , . . . , A [ j ] . }
v a r
k l u c z o s i o w y : t y p k l u c z a ;
i n d e k s k l u c z a o s i o w e g o : i n t e g e r ;
k : i n t e g e r ; { P o c z t e k g r u p y k l u c z y k l u c z o s i o w y . }
b e g i n
i n d e k s k l u c z a o s i o w e g o : = z n a j d z k l u c z o s i o w y ( i , j ) ;
i f i n d e k s k l u c z a o s i o w e g o = 0 t h e n
k l u c z o s i o w y : = A [ i n d e k s k l u c z a o s i o w e g o ] . k l u c z ;
k : = p o d z i a B( i , j , k l u c z o s i o w y ) ;
Q u i c k s o r t ( i , k - 1 ) ;
Q u i c k s o r t ( k , j ) ;
e n d i f ;
e n d ;
p r o c e d u r e q u i c k s o r t ;
p r o c e d u r e s o r t ( l , p : i n d e k s ) ;
v a r
i , j : i n d e k s ;
x , t : t y p r e k o r d u ;
b e g i n
i : = l ;
j : = p ;
W y b i e r z l o s o w o r e k o r d x ; { n p . x : = A [ ( l + p ) d i v 2 ] }
r e p e a t
w h i l e A [ i ] . k l u c z < x . k l u c z d o
i : = i + 1 ;
e n d w h i l e ;
w h i l e x . k l u c z < A [ j ] . k l u c z d o
j : = j - 1 ;
e n d w h i l e ;
i f i j t h e n
t : = A [ i ] ;
A [ i ] : = A [ j ] ;
A [ j ] : = t ;
i : = i + 1 ;
j : = j - 1 ;
e n d i f ;
u n t i l i > j ;
3 5
i f l < j t h e n
s o r t ( l , j ) ;
e n d i f ;
i f i < p t h e n
s o r t ( i , p ) ;
e n d i f ;
e n d ;
b e g i n
s o r t ( 1 , n ) ;
e n d ;
p r o c e d u r e Q u i c k s o r t 1 ( i , j : i n t e g e r ) ;
{ S o r t o w a n a j e s t t a b l i c a A [ i . . j ] . }
v a r
k l u c z o s i o w y : t y p k l u c z a ;
i n d e k s k l u c z a o s i o w e g o : i n t e g e r ;
k : i n t e g e r ; { P o c z t e k g r u p y k l u c z y k l u c z o s i o w y . }
x : t y p r e k o r d u ;
l , m : i n t e g e r ;
b e g i n
i f j - i + 1 9 t h e n
f o r l : = i + 1 t o j d o
{ N i e z m i e n n i k : A [ i . . l - 1 ] j e s t p o s o r t o w a n e . }
x : = A [ l ] ;
m : = l - 1 ;
w h i l e ( m > i - 1 ) c a n d ( x . k l u c z < A [ m ] . k l u c z ) d o
A [ m + 1 ] : = A [ m ] ;
m : = m - 1 ;
e n d w h i l e ;
A [ m + 1 ] : = x ;
e n d f o r ;
e l s e
i n d e k s k l u c z a o s i o w e g o : = z n a j d z k l u c z o s i o w y ( i , j ) ;
i f i n d e k s k l u c z a o s i o w e g o = 0 t h e n
k l u c z o s i o w y : = A [ i n d e k s k l u c z a o s i o w e g o ] . k l u c z ;
k : = p o d z i a B( i , j , k l u c z o s i o w y ) ;
Q u i c k s o r t 1 ( i , k - 1 ) ;
Q u i c k s o r t 1 ( k , j ) ;
e n d i f ;
e n d i f ;
e n d ;
6 . 6 I n n a w e r s j a a l g o r y t m u Q u i c k s o r t
D a n a j e s t n a s t p u j c a w e r s j a a l g o r y t m u s o r t o w a n i a s z y b k i e g o
p r o c e d u r e q s o r t ( d , g : i n d e k s ) ;
v a r
i , s : i n d e k s ;
t : t y p r e k o r d u ;
b e g i n
i f d < g t h e n
t : = A [ d ] ; { t . k l u c z j e s t k l u c z e m o s i o w y m }
s : = d ;
f o r i : = d + 1 t o g d o
{ N i e z m i e n n i k : A [ d + 1 . . s ] < t A [ s + 1 . . i - 1 ] }
3 6
i f A [ i ] . k l u c z < t . k l u c z t h e n
s : = s + 1 ;
Z a m i e D( A [ s ] , A [ i ] ) ;
e n d i f ;
e n d f o r ;
Z a m i e D( A [ d ] , A [ s ] ) ;
{ N i e z m i e n n i k : A [ d . . s - 1 ] < A [ s ] A [ s + 1 . . g ] }
q s o r t ( d , s - 1 ) ;
q s o r t ( s + 1 , g ) ;
e n d i f ;
e n d ;
W y z n a c z y m y z Bo |o n o [ [r e d n i t e g o a l g o r y t m u . W t y m c e l u z a Bo |y m y , |e :
1 . C i g k l u c z y r e k o r d w w t a b l i c y A j e s t l o s o w p e r m u t a c j l i c z b c a Bk o w i t y c h 1 . . . n .
2 . W y s t p i e n i e k a |d e j p e r m u t a c j i j e s t j e d n a k o w o p r a w d o p o d o b n e .
3 . P i e r w s z e w y w o Ba n i e p r o c e d u r y m a p o s t a q s o r t ( 1 , n ) .
4 . O p e r a c j d o m i n u j c j e s t p o r w n a n i e k l u c z y r e k o r d w .
Z a u w a |m y , |e d l a d g w y k o n u j e s i 0 p o r w n a D. W o b e c t e g o
T [r ( 0 ) = T [r ( 1 ) = 0 .
P o r w n a n i a k l u c z y r e k o r d w w y k o n y w a n e s g - d r a z y , w o b e c t e g o p r z y w y w o Ba n i u q s o r t ( 1 , n )
p o r w n a D w y k o n a n y c h b d z i e n - 1 . Z a B |m y , |e k l u c z e m o s i o w y m z o s t a j e w a r t o [ i . W w -
c z a s n a l e w o o d k l u c z a o s i o w e g o t r a f i i - 1 r e k o r d w , a n a p r a w o o d k l u c z a o s i o w e g o n - i
r e k o r d w . W o b e c t e g o w y k o n a m y w w c z a s
n - 1 + T ( i - 1 ) + T ( n - i )
p o r w n a D. W a r t o [ t m u s i m y u [r e d n i p o w s z y s t k i c h w a r t o [c i a c h i z p r z e d z i a Bu 1 . . n . P o n i e -
w a | k a |d a p e r m u t a c j a j e s t j e d n a k o w o p r a w d o p o d o b n a , t o p r a w d o p o d o b i e Ds t w o , |e k l u c z e m
1
o s i o w y m b d z i e w a r t o [ i w y n o s i . W o b e c t e g o
n
n
1
T [r ( n ) = ( n - 1 + T [r ( i - 1 ) + T [r ( n - i ) ) =
n
i = 1
1 1
= n - 1 + T [r ( i - 1 ) + T [r ( n - i )
n n
1 i n 1 i n
P o n i e w a |
T [r ( i - 1 ) = T [r ( i + 1 - 1 ) = T [r ( i )
1 i n 1 i + 1 n 0 i n - 1
T [r ( n - i ) = T [r ( n - ( n - i ) ) = T [r ( i )
1 i n 1 n - i n 0 i n - 1
o t r z y m u j e m y
n - 1
2
T [r ( n ) = n - 1 + T [r ( i ) . ( 4 )
n
i = 0
M n o |c o b i e s t r o n y r w n a n i a ( 4 ) p r z e z n o t r z y m u j e m y
n - 1
n T [r ( n ) = n 2 - n + 2 T [r ( i ) . ( 5 )
i = 0
3 7
R w n a n i e ( 5 ) d l a n - 1 m a p o s t a
n - 2
( n - 1 ) T [r ( n - 1 ) = ( n - 1 ) 2 - ( n - 1 ) + 2 T [r ( i ) . ( 6 )
i = 0
O d e j m u j c s t r o n a m i ( 5 ) i ( 6 ) o t r z y m u j e m y
n - 1 n - 2
n T [r ( n ) - ( n - 1 ) T [r ( n - 1 ) = n 2 - n - ( n - 1 ) 2 + n - 1 + 2 T [r ( i ) - 2 T [r ( n )
i = 0 i = 0
n T [r ( n ) = ( n + 1 ) T [r ( n - 1 ) + 2 ( n - 1 ) . ( 7 )
D o z n a l e z i e n i a r o z w i z a n i a ( 6 ) z a s t o s u j e m y m e t o d c z y n n i k a s u m a c y j n e g o [ 1 1 , s t r . 4 1 ] . Z ( 7 )
w y n i k a , i | a n = n , b n = n + 1 , c n = 2 ( n - 1 ) . W o b e c t e g o
a n - 1 a n - 2 a 1 ( n - 1 ) ( n - 2 ) 3 2 1 2
s n = = =
b n b n - 1 b 2 ( n + 1 ) n ( n - 1 ) ( n - 2 ) 3 ( n + 1 ) n
P o n i e w a | T [r ( 0 ) = 0 , o t r z y m u j e m y
n
1
T [r ( n ) = s k c k =
s n c n k = 1
n
1 2
= 2 ( k - 1 ) =
2
n k ( k + 1 )
n ( n + 1 )
k = 1
n
k - 1
= 2 ( n + 1 ) =
k ( k + 1 )
k = 1
n n
1 1
= 2 ( n + 1 ) - + 2 =
k k + 1
k = 1 k = 1
n n
1 1 2
= 2 ( n + 1 ) - + 2 + - 2 =
k k n + 1
k = 1 k = 1
n
1 2 n
= 2 ( n + 1 ) - =
k n + 1
k = 1
= 2 ( n + 1 ) H n - 4 n .
6 . 7 C z a s y w y k o n a n i a p r o g r a m w s o r t o w a n i a
T a b e l a I .
C i g i o d w r o t .
M e t o d a s o r t o w a n i a
C i g i u p o r z d k . C i g i l o s o w e
u p o r z d k .
W s t a w i a n i e p r o s t e 1 2 2 3 3 6 6 1 4 4 4 7 0 4 2 8 3 6
W s t a w i a n i e p o B w k o w e 5 6 1 2 5 3 7 3 1 3 2 7 6 6 2 2 4 9 0
W y b i e r a n i e p r o s t e 4 8 9 1 9 0 7 5 0 9 1 9 5 6 6 9 5 2 6 7 5
S o r t o w a n i e b b e l k o w e 5 4 0 2 1 6 5 1 0 2 6 4 0 5 4 1 4 9 2 5 9 3 1
S o r t o w a n i e b b e l k o w e z e z n a c z n i k i e m 5 8 1 1 0 4 4 2 7 0 1 6 4 5 6 5 4 2
S o r t o w a n i e m i e s z a n e 5 9 9 6 1 3 6 4 2 1 6 1 9 6 5 2 0
S o r t o w a n i e m e t o d S h e l l a 5 8 1 1 6 1 2 7 3 4 9 1 5 7 4 9 2
S o r t o w a n i e s t o g o w e 1 1 6 2 5 3 1 1 0 2 4 1 1 0 4 2 2 6
S o r t o w a n i e s z y b k i e 3 1 6 9 6 0 1 4 6 3 7 7 9
S o r t o w a n i e p r z e z Bc z e n i e 9 9 2 3 4 1 0 2 2 4 2 9 9 2 3 2
3 8
T a b e l a I I . ( k l u c z e w r a z z e z w i z a n y m i z n i m i d a n y m i )
C i g i o d w r o t .
M e t o d a s o r t o w a n i a
C i g i u p o r z d k . C i g i l o s o w e
u p o r z d k .
W s t a w i a n i e p r o s t e 1 2 4 6 3 6 6 1 1 2 9 7 0 4 2 1 5 0
W s t a w i a n i e p o B w k o w e 4 6 7 6 3 7 3 1 1 0 5 6 6 2 2 0 7 0
W y b i e r a n i e p r o s t e 4 8 9 5 4 7 5 0 9 6 0 7 6 9 5 1 4 3 0
S o r t o w a n i e b b e l k o w e 5 4 0 6 1 0 1 0 2 6 3 2 1 2 1 4 9 2 5 5 9 9
S o r t o w a n i e b b e l k o w e z e z n a c z n i k i e m 5 5 1 1 0 4 3 2 3 7 1 6 4 5 5 7 6 2
S o r t o w a n i e m i e s z a n e 5 5 9 6 1 3 0 7 1 1 6 1 9 5 7 5 7
S o r t o w a n i e m e t o d S h e l l a 5 8 1 8 6 1 2 7 3 7 3 1 5 7 4 3 5
S o r t o w a n i e s t o g o w e 1 1 6 2 6 4 1 1 0 2 4 6 1 0 4 2 2 7
S o r t o w a n i e s z y b k i e 3 1 5 5 6 0 1 3 7 3 7 7 5
S o r t o w a n i e p r z e z Bc z e n i e 9 9 1 9 6 1 0 2 1 9 5 9 9 1 8 7
7 S e l e k c j a
A : a r r a y [ 1 . . n ] o f t y p k l u c z a ;
f u n c t i o n s e l e k c j a ( i , j , k : i n t e g e r ) : t y p k l u c z a ;
{ Z n a j d o w a n y j e s t k - t y n a j m n i e j s z y k l u c z w t a b l i c y A [ i . . j ] . }
v a r
k l u c z o s i o w y : t y p k l u c z a ;
i n d e k s k l u c z a o s i o w e g o : i n t e g e r ;
m : i n t e g e r ; { P o c z t e k g r u p y k l u c z y k l u c z o s i o w y . }
b e g i n
i n d e k s k l u c z a o s i o w e g o : = z n a j d z k l u c z o s i o w y ( i , j ) ;
i f i n d e k s k l u c z a o s i o w e g o = 0 t h e n
k l u c z o s i o w y : = A [ i n d e k s k l u c z a o s i o w e g o ] ;
m : = p o d z i a B( i , j , k l u c z o s i o w y ) ;
i f k m - i t h e n
r e t u r n ( s e l e k c j a ( i , m - 1 , k ) ) ;
e l s e
r e t u r n ( s e l e k c j a ( m , j , k - m + i ) ) ;
e n d i f ;
e l s e
r e t u r n ( A [ i ] ) ;
e n d i f ;
e n d ;
8 S o r t o w a n i e p r z y u w z g l d n i e n i u s z c z e g l n y c h w Ba s n o -
[c i k l u c z y
t y p e t y p r e k o r d u = r e c o r d
k l u c z : 1 . . n ;
. . .
e n d ;
v a r A , B : a r r a y [ 1 . . n ] o f t y p r e k o r d u ;
A l g o r y t m 1
3 9
f o r i : = 1 t o n d o
B [ A [ i ] . k l u c z ] : = A [ i ] ;
e n d f o r ;
A l g o r y t m 2
f o r i : = 1 t o n d o
w h i l e A [ i ] . k l u c z = i d o
z a m i a n a ( A [ i ] , A [ A [ i ] . k l u c z ] ) ;
e n d w h i l e ;
e n d f o r ;
8 . 1 S o r t o w a n i e k u b e Bk o w e
t y p e
t y p k l u c z a = 1 . . m ; { l u b z n a k o w y ; o g l n i e t y p d y s k r e t n y ,
w z b i o r z e w a r t o [c i k t r e g o i s t n i e j e
r e l a c j a p o r z d k u }
t y p r e k o r d u = r e c o r d
k l u c z : t y p k l u c z a ;
. . .
e n d ;
e l e m e n t l i s t y = r e c o r d
r : t y p r e k o r d u ;
n a s t : e l e m e n t l i s t y
e n d ;
t y p l i s t o w y = e l e m e n t l i s t y ;
v a r
A : a r r a y [ 1 . . n ] o f t y p r e k o r d u ; { T a b l i c a r e k o r d w d o s o r t o w a n i a . }
B : a r r a y [ t y p k l u c z a ] o f t y p l i s t o w y ; { T a b l i c a k u b e Bk w .
W k u b e Bk u r e k o r d y s a p o Bc z o n e w l i s t . }
C : a r r a y [ t y p k l u c z a ] o f t y p l i s t o w y ; { T a b l i c a o d s y Ba c z y
d o k o Dc w l i s t w k u b e Bk a c h . }
p r o c e d u r e s o r t o w a n i e k u b e Bk o w e ;
v a r
i : i n t e g e r ;
p , v : t y p k l u c z a ;
b e g i n
f o r v : = n i s k i k l u c z t o w y s o k i k l u c z d o
B [ v ] : = n i l ;
C [ v ] : = n i l ;
e n d f o r ;
f o r i : = 1 t o n d o
W S T A W ( A [ i ] , B [ A [ i ] . k l u c z ] , C [ A [ i ] . k l u c z ] ) ;
e n d f o r ;
p : = n i s k i k l u c z ;
w h i l e B [ p ] = n i l d o
p : = s u c c ( p ) ;
e n d w h i l e ;
i f p = w y s o k i k l u c z t h e n
f o r v : = s u c c ( p ) t o w y s o k i k l u c z d o
i f B [ v ] = n i l t h e n
P O BC Z ( C [ p ] , B [ v ] , C [ v ] ) ;
4 0
e n d i f ;
e n d f o r ;
e n d i f ;
e n d ;
p r o c e d u r e W S T A W ( x : t y p r e k o r d u ; v a r l , m : t y p l i s t o w y ) ;
v a r
t e m p : t y p l i s t o w y ;
b e g i n
t e m p : = l ;
n e w ( l ) ;
l . r : = x ;
l . n a s t : = t e m p ;
i f t e m p = n i l t h e n
m : = l ;
e n d i f ;
e n d ; { W S T A W }
p r o c e d u r e P O BC Z ( v a r l C 1 : t y p l i s t o w y ; l B 2 , l C 2 : t y p l i s t o w y ) ;
{ P a r a m e t r y s o d s y Ba c z a m i d o p o c z t k w i k o Dc w Bc z o n y c h l i s t . }
b e g i n
l C 1 . n a s t : = l B 2 ;
l C 1 : = l C 2 ;
e n d ; { P O BC Z }
8 . 2 S o r t o w a n i e p o z y c y j n e
p r o c e d u r e s o r t o w a n i e p o z y c y j n e ;
{ S o r t o w a n a j e s t l i s t a A o n r e k o r d a c h , k t r y c h k l u c z e
s k Ba d a j s i z p l f 1 , f 2 , . . . , f k
o t y p a c h o d p o w i e d n i o t 1 , t 2 , . . . , t k . }
b e g i n
f o r i : = k d o w n t o 1 d o
f o r k a |d e j w a r t o [c i v t y p u t i d o
B i [ v ] : = n i l ; { O p r |n i a n i e k u b e Bk w . }
e n d f o r ;
f o r k a |d e g o r e k o r d u r n a l i [c i e A d o
p r z e s u D r z A n a k o n i e c l i s t y k u b e Bk a B i [ v ] ,
g d z i e v j e s t w a r t o [c i p o l a f i k l u c z a r e k o r d u r ;
e n d f o r ;
f o r k a |d e j w a r t o [c i v t y p u t i , o d n a j m n i e j s z e j d o
n a j w i k s z e j d o
d o Bc z B i [ v ] n a k o n i e c l i s t y A ;
e n d f o r ;
e n d f o r ;
e n d ;
P r a k t y c z n a i m p l e m e n t a c j a a l g o r y t m u s o r t o w a n i a p o z y c y j n e g o
S o r t o w a n i e l i s t y r e k o r d w A w e d Bu g d a t :
t y p e
t y p r e k o r d u = r e c o r d
4 1
d z i e D: 1 . . 3 1 ;
m i e s : ( s t y , . . . , g r u ) ;
r o k : 1 9 0 0 . . 1 9 9 9 ;
{ I n n e p o l a r e k o r d u . }
e n d ;
e l e m e n t l i s t y = r e c o r d
r : t y p r e k o r d u ;
n a s t : e l e m e n t l i s t y ;
e n d ;
t y p l i s t o w y = e l e m e n t l i s t y ;
v a r
A : t y p l i s t o w y ;
p r o c e d u r e s o r t o w a n i e w g d a t ;
{ S o r t o w a n a j e s t l i s t a A o n r e k o r d a c h , k t r y c h k l u c z e s d a t a m i . }
v a r
p 3 , v 3 : 1 9 0 0 . . 1 9 9 9 ;
p 2 , v 2 : ( s t y , . . . , g r u ) ;
p 1 , v 1 : 1 . . 3 1 ;
B 3 , C 3 : a r r a y [ 1 9 0 0 . . 1 9 9 9 ] o f t y p l i s t o w y ;
B 2 , C 2 : a r r a y [ ( s t y , . . . , g r u ) ] o f t y p l i s t o w y ;
B 1 , C 1 : a r r a y [ 1 . . 3 1 ] o f t y p l i s t o w y ;
b e g i n
{ S o r t o w a n i e r e k o r d w w e d Bu g d n i . }
f o r v 1 : = 1 t o 3 1 d o
B 1 [ v 1 ] : = n i l ;
C 1 [ v 1 ] : = n i l ;
e n d f o r ;
w h i l e A = n i l d o
{ W s t a w i e n i e r e k o r d u A . r n a k o n i e c l i s t y k u b e Bk a
o k r e [l o n e g o p r z e z k l u c z r e k o r d u . }
D O AC Z ( A . r , B 1 [ A . r . d z i e D] , C 1 [ A . r . d z i e D] ) ;
A : = A . n a s t ;
e n d w h i l e ;
p 1 : = 1 ;
w h i l e B 1 [ p 1 ] = n i l d o
p 1 : = s u c c ( p 1 ) ;
e n d w h i l e ;
i f p 1 = 3 1 t h e n
f o r v 1 : = s u c c ( p 1 ) t o 3 1 d o
{ P r z y Bc z e n i e l i s t w s z y s t k i c h k u b e Bk w d o k o Dc a l i s t y
w s k a z a n e j p r z e z B 1 [ p 1 ] . }
i f B 1 [ v 1 ] = n i l t h e n
P O AC Z ( C 1 [ p 1 ] , B 1 [ v 1 ] , C 1 [ v 1 ] ) ;
e n d i f ;
e n d f o r ;
e n d i f ;
A : = B 1 [ p 1 ] ;
{ D o k o n a p o d o b n i e s o r t o w a n i a k u b e Bk o w e g o l i s t y A w e d Bu g p l A . r . m i e s
o r a z A . r . r o k . }
e n d ;
p r o c e d u r e D O AC Z ( x : t y p r e k o r d u ; v a r l B , l C : t y p l i s t o w y ) ;
v a r
t e m p : t y p l i s t o w y ;
4 2
b e g i n
i f l B = n i l t h e n
n e w ( l C ) ;
l C . r : = x ;
l C . n a s t : = n i l ;
l B : = l C ;
e l s e
t e m p : = l C ;
n e w ( l C ) ;
l C . r : = x ;
l C . n a s t : = n i l ;
t e m p . n a s t : = l C ;
e n d i f ;
e n d ; { D O AC Z }
9 A l g o r y t m y z a c h Ba n n e
9 . 1 K o l o r o w a n i e z a c h Ba n n e
p r o c e d u r e k o l o r o w a n i e z a c h Ba n n e ( G : g r a f ;
v a r n o w y k o l o r : z b i r ) ;
{ P r o c e d u r a d o Bc z a d o z b i o r u n o w y k o l o r t e
w i e r z c h o Bk i g r a f u , k t r y m m o |n a p r z y p o r z d k o w a
t e n s a m k o l o r . }
v a r j e s t : B o o l e a n ;
v , w : i n t e g e r ;
b e g i n
n o w y k o l o r : = ";
v : = p i e r w s z y n i e p o k o l o r o w a n y w i e r z c h o Be k w G ;
w h i l e v < > n u l l d o
j e s t : = f a l s e ;
w : = p i e r w s z y w i e r z c h o Be k w z b i o r z e n o w y k o l o r ;
w h i l e w < > n u l l c a n d n o t j e s t d o
i f i s t n i e j e k r a w d z p o m i d z y v i w w G t h e n
j e s t : = t r u e ;
e n d i f ;
w : = n a s t p n y w i e r z c h o Be k w z b i o r z e n o w y k o l o r ;
e n d w h i l e ;
i f j e s t = f a l s e t h e n
O z n a c z v j a k o p o k o l o r o w a n y ;
D o Bc z v d o z b i o r u n o w y k o l o r ;
e n d i f ;
v : = n a s t p n y n i e p o k o l o r o w a n y w i e r z c h o Be k w G ;
e n d w h i l e ;
e n d ;
9 . 2 P r o b l e m k o m i w o j a |e r a
p r o c e d u r e k o m i w o j a |e r ( G : g r a f ; v a r d r o g a : c i g k r a w d z i ) ;
{ W y z n a c z a s i d r o g o m i n i m a l n y m k o s z c i e w g r a f i e G . }
v a r i : i n t e g e r ;
m i n : r e a l ;
b e g i n
m i n : = ";
f o r i : = 1 t o ( n - 1 ) ! d o
4 3
p : = i t a p e r m u t a c j a w i e r z c h o Bk w v 1 , v 2 , . . . , v n - 1 ;
{ N i e c h d ( p ) j e s t d r o g w g r a f i e G o d p o w i a d a j c
p e r m u t a c j i p j e g o w i e r z c h o Bk w . }
i f k o s z t ( d ( p ) ) < m i n t h e n
d r o g a : = d ( p ) ;
m i n : = k o s z t ( d ( p ) ) ;
e n d i f ;
e n d f o r ;
e n d ;
9 . 3 Z n a j d o w a n i e n a j t a Ds z y c h d r g a l g o r y t m D i j k s t r y
p r o c e d u r e D i j k s t r a ;
{ O b l i c z a n e s k o s z t y n a j t a Ds z y c h d r g z w i e r z c h o Bk a 1
d o k a |d e g o i n n e g o w i e r z c h o Bk a w g r a f i e z o r i e n t o w a n y m . }
b e g i n
S : = { 1 } ;
f o r i : = 2 t o n d o
D [ i ] : = C [ 1 , i ] ; { I n i c j a l i z a c j a t a b l i c y D . }
e n d f o r ;
f o r i : = 1 t o n - 1 d o
W y b r a w i e r z c h o Be k w z e z b i o r u V - S t a k i ,
|e D [ w ] j e s t m i n i m a l n e ;
D o Bc z y w d o S ;
f o r k a |d e g o w i e r z c h o Bk a v w z b i o r z e V - S d o
D [ v ] : = m i n ( D [ v ] , D [ w ] + C [ w , v ] ) ;
e n d f o r ;
e n d f o r ;
e n d ;
1 0 A l g o r y t m y g r a f o w e
1 0 . 1 P r z e s z u k i w a n i e g r a f u w g Bb
p r o c e d u r e w g ( v ) ;
{ P r z e s z u k i w a n i e w g Bb z w i e r z c h o l k a v . }
b e g i n
z n a c z n i k [ v ] : = o d w i e d z o n y ;
f o r u " l i s t y i n c y d e n c j i [ v ] d o
i f z n a c z n i k [ u ] = n i e o d w i e d z o n y t h e n
{ K r a w d z ( v , w ) w s t a w i a n a j e s t d o d r z e w a
r o z p i n a j c e g o . }
w g ( u ) ;
e n d i f ;
e n d f o r ;
e n d ;
b e g i n
{ P r z e s z u k i w a n i e g r a f u G = ( V , E ) w g Bb . }
f o r v " V d o
z n a c z n i k [ v ] : = n i e o d w i e d z o n y ;
e n d f o r ;
f o r v " V d o
i f z n a c z n i k [ v ] = n i e o d w i e d z o n y t h e n
w g ( v ) ;
4 4
e n d i f ;
e n d f o r ;
e n d ;
Z a s t o s o w a n i e m e t o d y p r z e s z u k i w a n i a w g Bb w y s z u k i w a n i e s k Ba d o w y c h s p j -
n o [c i
v a r c o m p n u m : a r r a y [ 1 . . | V | ] o f i n t e g e r ; { c o m p n u m [ v ] j e s t
n u m e r e m s k Ba d o w e j s p j n o [c i , d o k t r e j n a l e |y w i e r z c h o Be k v }
f o r v " V d o
c o m p n u m [ v ] : = 0
e n d f o r ;
c : = 0 ;
f o r v " V d o
i f c o m p n u m [ v ] = 0 t h e n
c : = c + 1 ;
C O M P ( v )
e n d i f ;
e n d f o r ;
p r o c e d u r e C O M P ( x : w i e r z c h o Be k ) ;
b e g i n
c o m p n u m ( x ) : = c ;
f o r w " a d j [ x ] d o
i f c o m p n u m [ w ] = 0 t h e n
C O M P ( w )
e n d i f ;
e n d f o r ;
e n d ;
N i e r e k u r s y w n a w e r s j a p r o c e d u r y p r z e s z u k i w a n i a w g Bb
p r o c e d u r e w g 1 ( v ) ;
{ N a p o c z t k u p r o c e s u p r z e s z u k i w a n i a P [ t ] = w s k a zn i k
d o p i e r w s z e g o r e k o r d u l i s t y a d j [ t ] d l a k a |d e g o u . }
b e g i n
s t o s ! "; s t o s ! v ; o d w i e d z v ; n o w y [ v ] : = f a l s e ;
w h i l e s t o s < > " d o
t : = t o p ( s t o s ) ; { o d c z y t a j s z c z y t o w y
e l e m e n t s t o s u }
w h i l e ( P [ t ] < > n i l ) c a n d ( n o t n o w y [ P [ t ] . w i e r z c h ] ) d o
P [ t ] : = P [ t ] . n a s t ; { z n a j d z n o w y w i e r z c h o Be k
n a l i [c i e a d j [ t ] }
e n d w h i l e ;
i f P [ t ] < > n i l t h e n { n o w y w i e r z c h o Be k z n a l e z i o n y }
t : = P [ t ] . w i e r z c h ; s t o s ! t ;
o d w i e d z t ; n o w y [ t ] : = f a l s e ;
e l s e { w i e r z c h o Be k t z o s t a B w y k o r z y s t a n y }
t ! s t o s ; { z d e j m i j s z c z y t o w y w i e r z c h o Be k z e s t o s u }
e n d i f ;
e n d w h i l e ;
e n d ;
4 5
1 0 . 2 P r z e s z u k i w a n i e g r a f u w s z e r z
p r o c e d u r e w s z ( v ) ;
{ P r z e s z u k i w a n i e w s z e r z z w i e r z c h o Bk a v . }
v a r K : k o l e j k a w i e r z c h o Bk w ( t y p u F I F O ) ;
b e g i n
z n a c z n i k [ v ] : = o d w i e d z o n y ;
w s t a w d o k o l e j k i ( v , K ) ;
w h i l e n o t p u s t a k o l e j k a ( K ) d o
x : = p i e r w s z y ( K ) ;
u s u D p i e r w s z y z k o l e j k i ( K ) ;
f o r y " l i s t y i n c y d e n c j i [ x ] d o
i f z n a c z n i k [ y ] = n i e o d w i e d z o n y t h e n
z n a c z n i k [ y ] : = o d w i e d z o n y ;
w s t a w d o k o l e j k i ( y , K ) ;
{ K r a w e d z ( x , y ) w s t a w i a n a j e s t d o d r z e w a
r o z p i n a j c e g o . }
e n d i f ;
e n d f o r ;
e n d w h i l e ;
e n d ;
b e g i n
{ P r z e s z u k i w a n i e g r a f u G = ( V , E ) w s z e r z . }
f o r v " V d o
z n a c z n i k [ v ] : = n i e o d w i e d z o n y ;
e n d f o r ;
f o r v " V d o
i f z n a c z n i k [ v ] = n i e o d w i e d z o n y t h e n
w s z ( v ) ;
e n d i f ;
e n d f o r ;
e n d ;
A l t e r n a t y w n a w e r s j a B F S
k o l e j k a ! " ; k o l e j k a ! v ; n o w y [ v ] : = f a l s e ;
w h i l e k o l e j k a < > " d o
p ! k o l e j k a ; { p o b i e r z p z k o l e j k i ( t j . z u s u n i c i e m ) }
f o r n " a d j [ p ] d o
i f n o w y [ n ] t h e n
k o l e j k a ! u ;
n o w y [ u ] : = f a l s e ;
e n d i f ;
e n d f o r ;
e n d w h i l e ;
Z a s t o s o w a n i e p r z e s z u k i w a n i a g r a f u w s z e r z z n a j d o w a n i e n a j k r t s z e j d r o g i p o -
m i d z y w i e r z c h o Bk a m i v i x w g r a f i e
v a r p r e d : a r r a y [ 1 . . | V | ] o f 1 . . | V | ; { w i e r z c h o Bk i p o p r z e d z a j c e
n a n a j k r t s z e j d r o d z e }
o d l : a r r a y [ 1 . . | V | ] o f i n t e g e r ; { d Bu g o [ n a j k r t s z e j d r o g i }
b e g i n
f o r v " V d o
n o w y [ v ] : = t r u e
4 6
e n d f o r ;
k o l e j k a : = p u s t a k o l e j k a ; k o l e j k a ! v 0 ; n o w y [ v 0 ] : = f a l s e ;
p r e d [ v 0 ] : = - 1 ;
o d l [ v 0 ] : = 0 ;
w h i l e n o w y [ x ] d o
p ! k o l e j k a ;
f o r u " a d j [ p ] d o
i f n o w y [ u ] t h e n
k o l e j k a ! u ; n o w y [ u ] : = f a l s e ;
p r e d [ u ] : = p ; o d l [ u ] : = o d l [ p ] + 1 ;
e n d i f ;
e n d f o r ;
e n d w h i l e ;
e n d ;
1 0 . 3 W y z n a c z a n i e c y k l i p o d s t a w o w y c h ( f u n d a m e n t a l n y c h )
b e g i n
f o r x " V d o
n u m [ x ] : = 0 ; { i n i c j a c j a n u m e r a c j i w i e r z c h o Bk w }
e n d f o r ;
i : = 0 ; { l i c z n i k d o n u m e r a c j i k o l e j n y c h w i e r z c h o Bk w
o d w i e d z a n y c h w g Bb }
j : = 0 ; { l i c z n i k c y k l i f u n d a m e n t a l n y c h }
k : = 0 ; { w s k a zn i k s t o s u }
f o r x " V d o
i f n u m [ x ] = 0 t h e n
k : = k + 1 ;
s t o s [ k ] : = x ;
Z N A J D y C Y K L E ( x , 0 ) ;
k : = k - 1 ;
e n d i f ;
e n d f o r ;
e n d ;
p r o c e d u r e Z N A J D y C Y K L E ( v , u ) ; { v w i e r z c h o Be k a k t u a l n y ,
u w i e r z c h o Be k p o p r z e d n i }
b e g i n
i : = i + 1 ; { O d w i e d z o n e w i e r z c h o Bk i z o s t a j p o n u m e r o w a n e }
n u m [ v ] : = i ; { r o s n c o z g o d n i e z l i c z n i k i e m i . }
f o r w " a d j [ v ] d o
i f n u m [ w ] = 0 t h e n
k : = k + 1 ;
s t o s [ k ] : = w ;
Z N A J D z C Y K L E ( w , v ) ;
k : = k - 1
e l s e
i f n u m [ w ] < n u m [ v ] c a n d w < > u t h e n
j : = j + 1 ; { l i c z n i k c y k l i }
s j j e s t c y k l e m ( w , s t o s [ k ] , s t o s [ k - 1 ] , . . . , s t o s [ t ] )
g d z i e s t o s [ t ] = w , s t o s [ k ] = v
e n d i f ;
e n d i f ;
e n d f o r ;
e n d ;
4 7
1 0 . 4 M i n i m a l n e d r z e w a r o z p i n a j c e
A l g o r y t m K r u s k a l a
T z b i r k r a w d z i m i n i m a l n e g o d r z e w a r o z p i n a j c e g o ; V S r o d z i n a ( z b i r ) r o z Bc z n y c h
z b i o r w w i e r z c h o Bk w ;
b e g i n
T : = ";
V S : = ";
S k o n s t r u u j k o l e j k p r i o r y t e t o w Q z a w i e r a j c
w s z y s t k i e k r a w d z i e z e z b i o r u E ;
f o r v " V d o
D o d a j { v } d o V S ;
e n d f o r ;
w h i l e | V S | > 1 d o
W y b i e r z z k o l e j k i Q k r a w d z ( v , w ) o n a j m n i e j s z y m k o s z c i e ;
U s u D ( v , w ) z Q ;
i f v i w n a l e | d o r |n y c h z b i o r w W 1 i W 2
n a l e |c y c h d o V S t h e n
Z a s t p W 1 i W 2 w V S p r z e z W 1 *" W 2 ;
D o d a j ( v , w ) d o T ;
e n d i f ;
e n d w h i l e ;
e n d ;
A l g o r y t m n a j b l i |s z e g o s s i e d z t w a ( P r i m a i D i j k s t r y )
( n = | V | )
v a r n e a r : a r r a y [ 1 . . n ] o f 1 . . n ; { d l a k a |d e g o w i e r z c h o Bk a v ,
k t r y n i e z n a l a z B s i j e s z c z e w d r z e w i e , e l e m e n t
n e a r [ v ] z a p a m i t u j e n a j b l i |s z y m u w i e r z c h o Be k d r z e w a }
d i s t : a r r a y [ 1 . . n ] o f r e a l ; { d i s t [ v ] z a p a m i t u j e
o d l e g Bo [ v o d n a j b l i |s z e g o m u w i e r z c h o Bk a d r z e w a }
W = [ w i j ] { m a c i e r z k o s z t w }
b e g i n
W y b i e r z a r b i t r a l n i e v 0 ;
f o r v " V d o
d i s t [ v ] : = W [ v , v 0 ] ; { k o s z t k r a w d z i ( v 0 , v ) }
n e a r [ v ] : = v 0 ;
e n d f o r ;
V t : = { v 0 } ; { w i e r z c h o Bk i d r z e w a }
E t : = "; { k r a w d z i e d r z e w a }
W t : = 0 ; { s u m a r y c z n y k o s z t d r z e w a }
w h i l e V t < > V d o
v : = w i e r z c h o Be k z V - V t o n a j m n i e j s z e j
w a r t o [c i d i s t [ v ] ;
V t : = V t *" { v } ;
E t : = E t *" { ( v , n e a r ( v ) ) } ;
W t : = W t + d i s t [ v ] ;
f o r x " V - V t d o
i f d i s t [ x ] > W [ v , x ] t h e n
d i s t [ x ] : = W [ v , x ] ;
4 8
n e a r [ x ] : = v
e n d i f ;
e n d f o r ;
e n d w h i l e ;
e n d ;
1 0 . 5 W y z n a c z a n i e c y k l i E u l e r a
b e g i n
S T O S ! "; { o p r |n i a n i e }
C E ! "; { s t o s w }
v : = d o w o l n y w i e r z c h o Be k g r a f u ;
S T O S ! v ;
w h i l e S T O S = " d o
v : = s z c z y t ( S T O S ) ; { v j e s t s z c z y t o w y m e l e m e n t e m s t o s u }
i f i n c [ v ] = " t h e n { l i s t a i n c y d e n c j i v j e s t n i e p u s t a }
u : = p i e r w s z y w i e r z c h o Be k l i s t y i n c [ v ] ;
S T O S ! u ;
{ u s u w a n i e k r a w d z i ( u , v ) z g r a f u }
i n c [ v ] : = i n c [ v ] - { u } ;
i n c [ u ] : = i n c [ u ] - { v } ;
e l s e { l i s t a i n c y d e n c j i v j e s t p u s t a }
v ! S T O S ; { p r z e n i e s i e n i e s z c z y t o w e g o w i e r z c h o Bk a s t o s u S T O S }
C E ! v ; { d o s t o s u C E }
e n d i f ;
e n d w h i l e ;
e n d ;
1 1 W y s z u k i w a n i e w y c z e r p u j a c e . A l g o r y t m z p o w r o t a m i
p r o c e d u r e w y s z u k i w a n i e z p o w r o t a m i ;
b e g i n
W y z n a c z S 1 ; { n a p o d s t a w i e A 1 i o g r a n i c z e D}
k : = 1 ;
w h i l e k > 0 d o
w h i l e S k < > " d o
a k : = e l e m e n t z S k ;
S k : = S k { a k } ;
i f ( a 1 , a 2 , . . . , a k ) j e s t r o z w i z a n i e m t h e n
w r i t e ( ( a 1 , a 2 , . . . , a k ) ) ;
e n d i f ;
k : = k + 1 ;
W y z n a c z S k ; { n a p o d s t a w i e A k i o g r a n i c z e D}
e n d w h i l e ;
k : = k - 1 ; { p o w r t }
e n d w h i l e ;
e n d ;
1 2 P r z e s z u k i w a n i e h e u r y s t y c z n e
1 2 . 1 P r z e s z u k i w a n i e w s z e r z
p r o c e d u r e B F S ;
4 9
b e g i n
Q ! "; { z e r o w a n i e k o l e j k i }
Q ! s 0 ; { s t a n p o c z t k o w y d o k o l e j k i }
l o o p
i f k o l e j k a Q p u s t a t h e n
r e t u r n ( p o r a |k a ) ;
e n d i f ;
s ! Q ; { p o b r a n i e s t a n u z k o l e j k i }
W y g e n e r o w a n i e n a s t p n i k w s j s t a n u s n a p o d s t a w i e
o p e r a t o r a d l a s t a n u s ;
W s t a w i e n i e s t a n w s j d o k o l e j k i ;
i f d o w o l n y s t a n s j j e s t s t a n e m k o Dc o w y m t h e n
r e t u r n ( s u k c e s ) ;
e n d i f ;
e n d l o o p ;
e n d B F S ;
1 2 . 2 P r z e s z u k i w a n i e w g Bb z i t e r a c y j n y m p o g Bb i a n i e m
p r o c e d u r e D F S ( s , g Bb o k o [, o d c i c i e ) ;
{ P r z e s z u k i w a n i e w g Bb z o d c i c i e m . s b i e |c y s t a n ,
g Bb o k o [ b i e |c a g Bb o k o [. }
b e g i n
f o r s j " n a s t p n i k i ( s ) d o
i f s j j e s t s t a n e m k o Dc o w y m t h e n
r e t u r n ( s u k c e s ) ; { z n a l e z i o n o r o z w i z a n i e }
e n d i f ;
i f g Bb o k o [ + 1 < o d c i c i e t h e n
D F S ( s j , g Bb o k o [ + 1 , o d c i c i e )
e n d i f ;
e n d f o r ;
e n d D F S ;
f o r o d c i c i e : = 1 t o o d c i c i e m a x d o
D F S ( s 0 , 0 , o d c i c i e ) ;
e n d f o r ;
r e t u r n ( p o r a |k a ) ;
1 2 . 3 P r z e s z u k i w a n i e w e d Bu g s t r a t e g i i n a j l e p s z y w i e r z c h o Be k j a k o
p i e r w s z y
O T W A R T E ! ( s , f ( s ) ) ; { w i e r z c h o Be k p o c z t k o w y n a l i s t }
w h i l e l i s t a O T W A R T E n i e p u s t a d o
( * ) P o b r a n i e z l i s t y O T W A R T E w i e r z c h o Bk a i o m i n i m a l n e j w a r t o [c i f ( i ) ;
Z A M K N I T E ! ( i , f ( i ) ) ;
i f i j e s t w i e r z c h o Bk i e m k o Dc o w y m t h e n
r e t u r n ( s u k c e s ) ;
e n d i f ;
R o z s z e r z e n i e w i e r z c h o Bk a i p r z e z w y z n a c z e n i e w s z y s t k i c h j e g o
n a s t p n i k w j i o b l i c z e n i e f ( j ) ;
i f j n i e w y s t p u j e n a l i s t a c h O T W A R T E i Z A M K N I T E t h e n
O P E N ! ( j , f ( j ) ) ;
U s t a n o w i e n i e w s k a zn i k a o d w i e r z c h o Bk a j d o j e g o p o p r z e d n i k a i
5 0
( a b y u m o |l i w i o d t w o r z e n i e r o z w i z a n i a k o Dc o w e g o ) ;
e l s e
( * * ) i f j w y s t p u j e n a l i [c i e O T W A R T E l u b Z A M K N I T E t h e n
i f n o w e f ( j ) < s t a r e f ( j ) t h e n
s t a r e f ( j ) : = n o w e f ( j ) ;
U s t a n o w i e n i e w s k a zn i k a o d j d o n o w e g o p o p r z e d n i k a i ;
e n d i f ;
i f w i e r z c h o Be k j j e s t n a l i [c i e Z A M K N I T E t h e n
P r z e s u n i c i e ( j , f ( j ) ) n a l i s t O T W A R T E ;
e n d i f ;
e n d i f ;
e n d i f ;
e n d w h i l e ;
r e t u r n ( p o r a |k a ) ;
1 3 G e n e r o w a n i e p e r m u t a c j i
p r o c e d u r e P E R M U T A C J E ( n , m ) ;
b e g i n
( p 1 p 2 . . . p m ) : = ( 1 2 . . . m ) ;
W y p r o w a d z ( p 1 p 2 . . . p m ) n a w y j [c i e ;
u 1 , u 2 , . . . , u n : = ( 1 , 1 , . . . , 1 ) ;
n
f o r i : = 1 t o P m - 1 d o
N A S T P N A P E R M U T A C J A ( n , m , p 1 , p 2 , . . . , p m ) ;
e n d f o r ;
e n d ;
p r o c e d u r e N A S T P N A P E R M U T A C J A ( n , m , p 1 , p 2 , . . . , p m ) ;
b e g i n
f o r i : = 1 t o m d o
u [ p i ] : = 0 ; { z a z n a c z e n i e , k t r e e l e m e n t y s w p e r m u t a c j i }
e n d f o r ;
{ Z n a l e z i e n i e n a j w i k s z e g o , n i e u |y w a n e g o e l e m e n t u w z b i o r z e { 1 , 2 , . . . , n } . }
f : = n ;
w h i l e u [ f ] < > 1 d o
f : = f - 1 ;
e n d w h i l e ;
{ Z n a l e z i e n i e n a j b a r d z i e j n a p r a w o p o Bo |o n e g o ,
m o d y f i k o w a l n e g o e l e m e n t u p e r m u t a c j i . }
k : = m + 1 ;
i : = 0 ; { I n d e k s e l e m e n t u p e r m u t a c j i , k t r y z o s t a n i e z m o d y f i k o w a n y . }
w h i l e i = 0 d o
k : = k - 1 ;
u [ p k ] : = 1 ;
i f p k < f t h e n { u a k t u a l n i j p k }
Z n a j d z n a j m n i e j s z e j t a k i e , |e p k < j n o r a z u [ j ] = 1 ;
i : = k ;
p i : = j ; { z m o d y f i k o w a n i e p e r m u t a c j i }
u [ p i ] : = 0 ;
e l s e
f : = p k ; { n a j w i k s z y , n i e u |y w a n y e l e m e n t j e s t u s t a w i a n y n a w a r t o [ p k }
e n d i f ;
e n d w h i l e ;
{ U a k t u a l n i e n i e e l e m e n t w l e |c y c h n a p r a w o o d p i }
5 1
f o r k : = 1 t o m - i d o
i f u [ s ] j e s t k - t p o z y c j w t a b l i c y u r w n 1 t h e n
p i + k : = s ;
e n d i f ;
e n d f o r ;
{ P r z y w r 1 - k i w t a b l i c y u . }
f o r k : = 1 t o i d o
u [ p k ] : = 1 ;
e n d f o r ;
W y p r o w a d z ( p 1 p 2 . . . p m ) n a w y j [c i e ;
e n d ;
p r o c e d u r e R Z D ( n , m , p 1 , p 2 , . . . , p m , d ) ;
b e g i n
f o r i : = 1 t o m d o
d : = 0 ;
f o r j : = 1 t o i - 1 d o
i f p i < p j t h e n
d : = d + 1 ;
e n d i f ;
e n d f o r ;
r i : = p i - i + d ;
e n d f o r ;
d : = r m + 1 ;
w a g a : = 1 ;
f o r k : = m - 1 d o w n t o 1 d o
w a g a : = ( n - k ) " w a g a ;
d : = d + r k " w a g a ;
e n d f o r ;
e n d R Z D ;
p r o c e d u r e R Z D O D W R ( n , m , d , p 1 , p 2 , . . . , p m ) ;
b e g i n
d : = d - 1 ;
f o r i : = 1 t o n d o
s i : = 0 ;
e n d f o r ;
a : = 1 ; { o b l i c z e n i e ( n - m + 1 ) ( n - m + 2 ) . . . ( n - 1 ) }
f o r i : = m - 1 d o w n t o 1 d o
a : = a " ( n - m + i ) ;
e n d f o r ;
{ w y z n a c z a n i e p i , i = 1 , 2 , . . . , m }
f o r i : = 1 t o m d o
r : = d / ;
d : = d - r " a ;
i f n > i t h e n
a : = a / / ( n - i ) ;
e n d i f ;
k : = 0 ; j : = 0 ;
{ s z u k a n i e ( r + 1 ) - e g o e l e m e n t u t a b l i c y s r w n e g o 0 }
w h i l e k < r + 1 d o
j : = j + 1 ;
i f s j = 0 t h e n { e l e m e n t = j n i e w y s t p i B j e s z c z e w p e r m u t a c j i }
k : = k + 1 ;
e n d i f ;
5 2
e n d w h i l e ;
p i : = j ; { e l e m e n t p e r m u t a c j i = j }
s j : = 1 ; { w p e r m u t a c j i w y s t p i B e l e m e n t = j }
e n d f o r ;
e n d R Z D O D W R ;
1 4 P y t a n i a
1 . M e t o d y e m p i r y c z n e g o t e s t o w a n i a p r o g r a m w . D l a c z e g o t e s t o w a n i e e m p i r y c z n e j e s t
n i e d o s k o n a Be ? C o s d z i D i j k s t r a o t e s t o w a n i u e m p i r y c z n y m ?
2 . C o t o s : a k s j o m a t , a s e r c j a , r e g u Ba d o w o d z e n i a ? P o d a a k s j o m a t y l i c z b c a Bk o w i t y c h i
r z e c z y w i s t y c h . C o t o s : z d a n i e , p r e d y k a t . P o d a k i l k a a k s j o m a t w r a c h u n k u z d a D.
3 . P o d a i o m w i n a w y b r a n y c h p r z y k Ba d a c h r e g u By d o w o d z e n i a d l a i n s t r u k c j i p r z y p i -
s a n i a o r a z i n s t r u k c j i z Bo |o n e j .
4 . P o d a i o m w i n a w y b r a n y c h p r z y k Ba d a c h r e g u By d o w o d z e n i a d l a i n s t r u k c j i a l t e r n a -
t y w y o r a z i n s t r u k c j i w a r u n k o w e j .
5 . P o d a i o m w i n a w y b r a n y m p r z y k Ba d z i e r e g u B d o w o d z e n i a d l a i n s t r u k c j i i t e r a c j i
d o p k i . C o t o j e s t n i e z m i e n n i k p t l i ?
6 . P o d a i o m w i n a w y b r a n y m p r z y k Ba d z i e r e g u B d o w o d z e n i a d l a i n s t r u k c j i i t r a c j i
p o w t a r z a j . C o t o j e s t n i e z m i e n n i k p t l i ?
7 . P o d a i o m w i n a w y b r a n y m p r z y k Ba d z i e r e g u By d o w o d z e n i a d l a i n s t r u k c j i i t e r a c j i
d l a . C o t o j e s t n i e z m i e n n i k p t l i ?
8 . C z [c i o w a o r a z p e Bn a p o p r a w n o [ a l g o r y t m u . J a k d o w o d z i s i d o c h o d z e n i e o b l i c z e D
a l g o r y t m u d o p u n k t u k o Dc o w e g o ( w Ba s n o [ s t o p u ) ?
9 . P o d a d e f i n i c j e p o j : r o z m i a r d a n y c h , d z i a Ba n i e d o m i n u j c e , z Bo |o n o [ c z a s o w a a l g o -
r y t m u , z Bo |o n o [ p a m i c i o w a a l g o r y t m u . W y m i e n i t y p o w e f u n k c j e o k r e [l a j c e z Bo |o -
n o [c i o b l i c z n i o w e a l g o r y t m w . P o c o w y z n a c z a s i z Bo |o n o [ o b l i c z e n i o w a l g o r y t m u ?
1 0 . C o r o z u m i e s z p r z e z : z Bo |o n o [ p e s y m i s t y c z n a l g o r y t m u , z Bo |o n o [ [r e d n i a l g o r y t m u ?
U d o w o d n i j , |e W ( n ) = a m n m + . . . + a 1 n + a 0 = O ( n m ) d l a n > 0 .
1 1 . J a k b r z m i d e f i n i c j a O - n o t a c j i ? P o d a i u d o w o d n i t r z y d o w o l n e w Ba s n o [c i r z d u f u n k c j i .
1 2 . O k r e [l i z Bo |o n o [ o b l i c z e n i o w a l g o r y t m u w y z n a c z a n i a w a r t o [c i w i e l o m i a n u d l a p r z y -
p a d k w : ( a ) k o r z y s t a j c b e z p o [r e d n i o z e w z o r u , ( b ) k o r z y s t a j c z e s c h e m a t u H o r n e r a .
1 3 . P o d a d w a a l g o r y t m y z n a j d o w a n i a m a k s y m a l n e g o e l e m e n t u w t a b l i c y . W y z n a c z y i
p o r w n a i c h z Bo |o n o [c i .
1 4 . P o d a a l g o r y t m y z n a j d o w a n i a e l e m e n t u m a k s y m a l n e g o i m i n i m a l n e g o w z a d a n y m
z b i o r z e d l a p r z y p a d k w : ( a ) k o l e j n e z n a j d o w a n i e e l e m e n t u m a k s y m a l n e g o a n a s t p -
n i e m i n i m a l n g o , ( b ) d z i e l e n i e z a d a n i a n a p o d z a d a n i a . O k r e [l i z Bo |o n o [ o b l i c z n i o w
a l g o r y t m w .
1 5 . P o d a a l g o r y t m m n o |e n i a d w c h n - b i t o w y c h l i c z b d w j k o w y c h z z a s t o s o w a n i e m m e -
t o d y d z i e l e n i a z a d a n i a n a p o d z a d a n i a . O k r e [l i z Bo |o n o [ o b l i c z e n i o w a l g o r y t m u .
1 6 . W y p r o w a d z i r o z w i z a n i a r w n a D r e k u r e n c y j n y c h : T ( n ) = b d l a n = 1 o r a z T ( n ) =
n
a T ( ) + b n d l a n > 1 . P o d a i n t e r p r e t a c j r o z w i z a D.
c
1 7 . O m w i z a s a d r w n o w a |e n i a r o z m i a r w p o d z a d a D n a p r z y k Ba d z i e z a d a n i a s o r t o w a -
n i a , r o z w a |a j c a l g o r y t m s o r t o w a n i a p r z e z w y b r p r o s t y o r a z r e k u r s y w n y a l g o r y t m
s o r t o w a n i a p r z e z Bc z e n i e . O k r e [l i z Bo |o n o [c i o b l i c z e n i o w e a l g o r y t m w .
5 3
1 8 . S f o r m u Bo w a z a d a n i e s o r t o w a n i a . P o d a o g l n k l a s y f i k a c j a l g o r y t m w s o r t o w a n i a
o r a z k l a s y f i k a c j a l g o r y t m w s o r t o w a n i a w e w n t r z n e g o . P o d a d e f i n i c j e p o j : d r z e w o
d e c y z y j n e s o r t o w a n i a , g Bb o k o [ i w y s o k o [ w i e r z c h o Bk a w d r z e w i e , w y s o k o [ d r z e w a .
O k r e [l i k r e s d o l n y z Bo |o n o [c i o b l i c z e n i o w e j a l g o r y t m w s o r t o w a n i a w e w n t r z n e g o z
p o m o c p o r w n a D.
1 9 . P o d a w Ba s n o [c i k o p c a o r a z o m w i s p o s b j e g o i m p l e m e n t a c j i . P o d a i w y j a [n i d z i a -
Ba n i e p r o c e d u r : p r z e m i e [ w g r i p r z e m i e [ w d B.
2 0 . P o d a a b s t r a k c y j n y o p i s k o l e j k i p r i o r y t e t o w e j . P o d a i w y j a [n i d z i a Ba n i e p r o c e d u r
w s t a w i u s u D m i n d l a k o l e j k i i m p l e m e n t o w a n e j z p o m o c k o p c a . J a k i e s i n n e m o |l i w e
i m p l e m e n t a c j e k o l e j k i ? P o r w n a j e z e s o b p o d k t e m z Bo |o n o [c i o b l i c z e n i o w e j .
2 1 . P o d a a l g o r y t m b u d o w a n i a k o p c a ( f a z a 1 . s o r t o w a n i a p r z e z k o p c o w a n i e ) . W y z n a c z y
j e g o z Bo |o n o [ p e s y m i s t y c z n .
2 2 . P o d a a l g o r y t m s o r t o w a n i a p r z e z k o p c o w a n i e o r a z o k r e [l i j e g o p e s y m i s t y c z n z Bo |o -
n o [ o b l i c z e n i o w .
2 3 . P o d a a l g o r y t m s o r t o w a n i a l i c z b n a t u r a l n y c h z z a k r e s u [ 1 . . n ] o z Bo |o n o [c i l i n i o w e j .
C z y p r z y s o r t o w a n i u n i e z b d n a j e s t d o d a t k o w a t a b l i c a ?
2 4 . P o d a a l g o r y t m s o r t o w a n i a k u b e Bk o w e g o . J a k a j e s t j e g o z Bo |o n o [? C o t o j e s t p o r z d e k
l e k s y k o g r a f i c z n y ? P o d a a l g o r y t m s o r t o w a n i a p o z y c y j n e g o . J a k a j e s t j e g o z Bo |o n o [?
2 5 . P o d a a l g o r y t m s o r t o w a n i a p r z e z p r o s t e w s t a w i a n i e ( z w a r t o w n i k i e m ) . O k r e [l i j e g o
z Bo |o n o [ p e s y m i s t y c z n o r a z [r e d n i .
2 6 . P o d a a l g o r y t m s o r t o w a n i a m e t o d S h e l l a . J a k n a l e |y d o b i e r a p r z y r o s t y ? J a k a j e s t
z Bo |o n o [ a l g o r y t m u ?
2 7 . P o d a a l g o r y t m s o r t o w a n i a p r z e z p r o s t e w y b i e r a n i e . O k r e [l i j e g o z Bo |o n o [ p e s y m i -
s t y c z n o r a z [r e d n i . J a k i e s m o |l i w o [c i u l e p s z a n i a a l g o r y t m u ?
2 8 . P o d a a l g o r y t m s o r t o w a n i a b b e l k o w e g o . J a k a j e s t j e g o z Bo z o n o [? J a k i e s m o |l i w o [c i
u l e p s z a n i a a l g o r y t m u ?
2 9 . P o d a a l g o r y t m s o r t o w a n i a s z y b k i e g o ( Q u i c k s o r t ) . C o w a r u n k u j e j e g o s z y b k i e d z i a Ba -
n i e .
3 0 . W y z n a c z y z Bo |o n o [ p e s y m i s t y c z n i [r e d n i a l g o r y t m u s o r t o w a n i a s z y b k i e g o .
3 1 . O m w i d w i e m e t o d y w y z n a c z a n i a k - t e g o c o d o w i e l k o [c i k l u c z a w t a b l i c y : a ) m o -
d y f i k a c j a a l g o r y t m u s o r t o w a n i a p r z e z k o p c o w a n i e ; b ) a l g o r y t m r e k u r s y w n y . J a k i e s
z Bo |o n o [c i t y c h m e t o d ?
3 2 . P o d a a l g o r y t m s o r t o w a n i a p l i k w s e k w e n c y j n y c h p r z e z Bc z e n i e p r o s t e ( n a [r e d n i m
p o z i o m i e a b s t r a k c j i ) . J a k a j e s t z Bo |o n o [ a l g o r y t m u ?
3 3 . P o d a a l g o r y t m s o r t o w a n i a p l i k w s e k w e n c y j n y c h p r z e z Bc z e n i e n a t u r a l n e ( n a [r e d -
n i m p o z i o m i e a b s t r a k c j i ) . J a k a j e s t z Bo |o n o [ a l g o r y t m u ?
3 4 . O m w i i d e e s o r t o w a n i a p r z e z w i e l o k i e r u n k o w e Bc z e n i e w y w a |o n e o r a z s o r t o w a n i a
p o l i f a z o w e g o . J a k i e s z Bo |o n o [c i t y c h m e t o d ?
3 5 . S f o r m u Bo w a z a d a n i e w y s z u k i w a n i a . P o d a a l g o r y t m y w y s z u k i w a n i a l i n i o w e g o ( b e z
w a r t o w n i k a i z w a r t o w n i k i e m ) o r a z o k r e [l i i c h z Bo |o n o [c i [r e d n i e i p e s y m i s t y c z n e .
3 6 . P o d a a l g o r y t m w y s z u k i w a n i a b i n a r n e g o . O k r e [l i j e g o z Bo |o n o [ p e s y m i s t y c z n .
3 7 . P o r w n a a l g o r y t m y w y s z u k i w a n i a l i n i o w e g o i b i n a r n e g o p o d k t e m p e s y m i s t y c z n e j
z Bo |o n o [c i o b l i c z e n i o w e j o r a z n a r z u t u z w i z a n e g o z k o n i e c z n o [c i r e o r g a n i z a c j i p l i k u
r e k o r d w .
5 4
3 8 . P o d a w Ba s n o [c i d r z e w a p o s z u k i w a D b i n a r n y c h o r a z p r o c e d u r y s z u k a j i w s t a w o p e r u -
j c e n a d r z e w i e . J a k i j e s t k o s z t w y s z u k i w a n i a k l u c z a w d r z e w i e ?
3 9 . P o d a i o m w i p r o c e d u r u s u w a n i a k l u c z a z d r z e w a p o s z u k i w a D b i n a r n y c h .
4 0 . D l a m e t o d y h a s z o w a n i a o t w a r t e g o p o d a p r o c e d u r y w y s z u k i w a n i a , w s t a w i a n i a i u s u -
w a n i a e l e m e n t u z t a b l i c y h a s z u j c e j . J a k a j e s t [r e d n i a z Bo |o n o [ o b l i c z e n i o w a k a |d e j z
p r o c e d u r ?
4 1 . D l a m e t o d y h a s z o w a n i a z a m k n i t e g o p o d a p r o c e d u r y w y s z u k i w a n i a , w s t a w i a n i a i
u s u w a n i a e l e m e n t u z t a b l i c y h a s z u j c e j .
4 2 . P o d a w y m a g a n i a j a k i e p o w i n n a s p e Bn i a p o d s t a w o w a f u n k c j a h a s z u j c a . W y m i e n i i
o m w i c z s t o s t o s o w a n e p o d s t a w o w e f u n k c j e h a s z u j c e .
4 3 . O m w i m e t o d y p r z e z w y c i |a n i a k o l z j i w m e t o d z i e h a s z o w a n i a z a m k n i t e g o . J a k i e s
w a d y i z a l e t y w y s z u k i w a n i a i w s t a w i a n i a h a s z u j c e g o ?
4 4 . O k r e [l i z Bo |o n o [ o b l i c z e n i o w h a s z o w a n i a z a m k n i t e g o . J a k n a l e |y d o b r a o b j t o [
t a b l i c y h a s z u j c e j ?
4 5 . N a c z y m p o l e g a r e s t r u k t u r y z a c j a t a b l i c h a s z u j c y c h ? C o t o j e s t m i n i m a l n a d o s k o n a Ba
f u n k c j a h a s z u j c a ? P o d a p r z y k Ba d t a k i e j f u n k c j i .
4 6 . P o d a a l g o r y t m n a i w n y w y s z u k i w a n i a w z o r c a w t e k [c i e . J a k a j e s t j e g o z Bo |o n o [?
4 7 . P o d a a l g o r y t m w y s z u k i w a n i a K n u t h a , M o r r i s a i P r a t t a . J a k w y z n a c z a s i w a r t o [c i
e l e m e n t w t a b l i c y n a s t ?
4 8 . D l a w y b r a n e g o p r z y k Ba d u p o d a a l g o r y t m w y s z u k i w a n i a K n u t h a , M o r r i s a i P r a t t a z
w b u d o w a n y m w z o r c e m . C o t o j e s t k o m p i l a t o r p r o c e d u r w y s z u k i w a n i a ?
4 9 . P o d a a l g o r y t m w y s z u k i w a n i a n i e z g o d n o [c i o w e g o . O m w i j e g o d z i a Ba n i e n a p r z y k Ba -
d z i e . J a k w y z n a c z a s i w a r t o [c i e l e m e n t w t a b l i c y s k o k 1 .
5 0 . P o d a a l g o r y t m w y s z u k i w a n i a B o y e r a i M o o r a . C z y j e s t o n b a r d z i e j e f e k t y w n y o d
a l g o r y t m u w y s z u k i w a n i a n i e z g o d n o [c i o w e g o .
5 1 . O m w i i d e a l g o r y t m u z a c h Ba n n e g o n a p r z y k Ba d z i e p r o j e k t o w a n i a s e k w e n c j i z m i a n y
[w i a t e B d l a s k r z y |o w a n i a . N a c z y m p o l e g a p r o b l e m k o l o r o w a n i a g r a f u ?
5 2 . S f o r m u Bo w a p r o b l e m k o m i w o j a |e r a . P o d a : a ) a l g o r y t m t y p u s p r a w d z w s z y s t k i e
m o |l i w o [c i ; b ) a l g o r y t m h e u r y s t y c z n y o p a r t y n a p o s t p o w a n i u z a c h Ba n n y m . J a k i e
s z Bo |o n o [c i a l g o r y t m w ?
5 3 . S f o r m u Bo w a i p o r w n a p r o b l e m y z n a l e z i e n i a m a r s z r u t y k o m i w o j a |e r a , c y k l u E u l e r a
i c y k l u H a m i l t o n a .
5 4 . P o d a a l g o r y t m D i j k s t r y z n a j d o w a n i a n a j k r t s z y c h d r g z u s t a l o n e g o w i e r z c h o Bk a .
O b j a [n i j e g o d z i a Ba n i e n a w y b r a n y m p r z y k Ba d z i e .
5 5 . O m w i p r z e s z u k i w a n i e g r a f u w g Bb . P o d a z a s t o s o w a n i e t e g o p r z e s z u k i w a n i a d l a
p r o b l e m u z n a j d o w a n i a s k Ba d o w y c h s p j n o [c i .
5 6 . O m w i p r z e s z u k i w a n i e g r a f u w s z e r z . P o d a z a s t o s o w a n i e t e g o p r z e s z u k i w a n i a d l a
p r o b l e m u z n a j d o w a n i a n a j k r t s z e j [c i e |k i w g r a f i e ( d Bu g o [ [c i e |k i l i c z o n a l i c z b k r a -
w d z i ) .
5 7 . P o d a i o m w i a l g o r y t m z n a j d o w a n i a c y k l i f u n d a m e n t a l n y c h w g r a f i e . J a k a j e s t j e g o
z Bo |o n o [?
5 8 . P o d a i o m w i a l g o r y t m K r u s k a l a z n a j d o w a n i a m i n i m a l n e g o d r z e w a r o z p i n a j c e g o .
J a k a j e s t j e g o z Bo |o n o [?
5 5
5 9 . P o d a i o m w i a l g o r y t m P r i m a i D i j k s t r y z n a j d o w a n i a m i n i m a l n e g o d r z e w a r o z p i n a -
j c e g o . J a k a j e s t j e g o z Bo |o n o [?
6 0 . P o d a i o m w i a l g o r y t m w y z n a c z a n i a c y k l i E u l e r a . J a k a j e s t j e g o z Bo |o n o [?
n
6 1 . P o d a i o m w i a l g o r y t m w y z n a c z a n i a P m p e r m u t a c j i . J a k a j e s t j e g o z Bo |o n o [?
1 5 P o d z i k o w a n i a
W p r z y g o t o w a n i u p i e r w s z e j w e r s j i n i n i e j s z y c h m a t e r i a B w u c z e s t n i c z y By B e a t a B a r t k o w i a k i
B e a t a G a w l i k , z a [ d r u g w e r s j p r z y g o t o w a l i M a g d a l e n a B i e d z k a i Z d z i s Ba w K o c h . K o l e j n
w e r s j p r z y g o t o w a By Z o f i a I m i e l a o r a z B o |e n a B a r t o s z e k . W e r s j e n a s t p n e p r z y g o t o w a l i M o -
h a m e d D a g h e s t a n i o r a z I l o n a B a r g i e B, W o j c i e c h M i k a n i k i J o a n n a S i m
a k . W s z y s t k i m t y m
o s o b o m s k Ba d a m s e r d e c z n e p o d z i k o w a n i a .
L i t e r a t u r a
[ 1 ] W i r t h , N . , A l g o r y t m y + S t r u k t u r y D a n y c h = P r o g r a m y , W N T , W a r s z a w a , 1 9 8 0 .
[ 2 ] B a n a c h o w s k i , L . , K r e c z m a r , A . , E l e m e n t y A n a l i z y A l g o r y t m w , W N T , W a r s z a w a , 1 9 8 2 .
[ 3 ] A l a g i , S . , A r b i b , M . A . , P r o j e k t o w a n i e P r o g r a m w P o p r a w n y c h i D o b r z e Z b u d o w a n y c h ,
W N T , W a r s z a w a , 1 9 8 2 .
[ 4 ] A h o , A . V . , U l l m a n , J . D . , P r o j e k t o w a n i e i A n a l i z a A l g o r y t m w K o m p u t e r o w y c h , P W N ,
W a r s z a w a , 1 9 8 3 .
[ 5 ] R e i n g o l d , E . M . , N i e v e r g e l t , J . , D e o , N . , A l g o r y t m y K o m b i n a t o r y c z n e , P W N , W a r s z a w a ,
1 9 8 5 .
[ 6 ] B e n t l e y , J . , P e r e Bk i O p r o g r a m o w a n i a , W N T , W a r s z a w a , 1 9 8 6 .
[ 7 ] L i p s k i , W . , K o m b i n a t o r y k a d l a P r o g r a m i s t w , W N T , W a r s z a w a , 1 9 8 7 .
[ 8 ] B a n a c h o w s k i , L . , K r e c z m a r , A . , R y t t e r , W . , A n a l i z a A l g o r y t m w i S t r u k t u r D a n y c h ,
W N T , W a r s z a w a , 1 9 8 7 .
[ 9 ] H a r e l , D . , R z e c z o I s t o c i e I n f o r m a t y k i . A l g o r y t m i k a , W N T , W a r s z a w a , 1 9 9 2 .
[ 1 0 ] B a n a c h o w s k i , L . , D i k s , K . , R y t t e r , W . , A l g o r y t m y i S t r u k t u r y D a n y c h , W N T , W a r s z a -
w a , 1 9 9 6 .
[ 1 1 ] G r a h a m , R . L . , K n u t h , D . E . , P a t a s h n i k , O . , M a t e m a t y k a K o n k r e t n a , P W N , W a r s z a w a ,
1 9 9 6 .
[ 1 2 ] C o r m e n , T . H . , L e i s e r s o n , C . E . , R i v e s t , R . L . , W p r o w a d z e n i e d o A l g o r y t m w , W N T ,
W a r s z a w a , 1 9 9 7 .
5 6
Wyszukiwarka
Podobne podstrony:
analiza algorytmowZestawienie tematów objętych zakresem egzaminu z budowy i analizy algorytmówAnaliza algorytmów ukrywania w dźwiękuWyklad 6 Budowa i analiza algorytmówWyklad 4 Budowa i analiza algorytmówAnaliza Algorytmów ĆwiczeniaWyklad 5 Budowa i analiza algorytmówProjektowanie i analiza algorytmowPS 6 Analiza czasowo czestotliwosciowaMegatutorial M B Analiza efektywności algorytmów56$3105 specjalista analizy i rozwoju rynkuwięcej podobnych podstron