IJͲ Dz
( )
( )
2011
̲Ͳ ²
ղ ֲ Ͳ
IJͲ Dz
( )
( )
.
1 29.08.2008
2011
004(076)
( )/ .: .. : - . .., 2011.-**.
. , . , .
: .., .
³. .., .
..,
1
:
, .
1. ;
2. ;
3. ;
4. .
, . , , , , .
, :
1. .
2. .
3. .
4. .
5. .
6. .
7. .
8. .
. .
, . , . :
1. , ?
2. ?
3. ?
|
|
|
4. ?
5. ?
6. ?
7. ?
8. .
' (); 20 , . 50% . , . ³ .
? , . . ci j, i j. 20 20 .
? . . ij, , , . , , . , ? , , , . , , , . , .
. ³ , , , . , , , , . , ' . , . , .
. , .
, :
1. ?
2. ?
. ij, , , ( ). 䳺 , , .
:
1. ;
2. ;
3. ;
4. , ' .
, '. , :
1. '?
|
|
|
2. , ?
3. - ' ?
4. ? ?
. ? , , . . ?
, , . , , i j, . - , ' i j C.
, , - .
, ' .
. ' .
? , . . . , .
, . , , .
, .
. , .
1. ³ . begin end. ( , , .)
2. while, for, repeat if, then, else , .
3. ▷ ( ).
4. ije ( i j e) je ij ( ).
5. ( ).
6. : A[i] i- . .. : A[1..j] , A[1], A[2], , A[j].
7. ', , , , . '_ [_']. , length, length [A]. , ( '). , ', . ϳ y x - f f [y] = f [x]. , f [x] 3, f [x] = 3, f [y] = 3, '. NIL ( ').
8. (by value): ; . ' , ', ' - . , - , , , , f [x] 3 - .
, . , , . , .
|
|
|
.
. .
n. .
, n-1 . . , ' , . , . .
0. ▷ -
Set TOUR Æ; and MIN∞.
1. ▷
For I1 to (N-1)! Do
2. ▷
Set PI- 1, 2,..., N-1. (, .)
3. ▷
(), ; and COST(T(P)).
(, (, .)
4. ▷
if COST(T(P))<MIN then set TOURT(P); and MINCOST(T(P))
: . . . 䳿 , . , ', .
.
- , .
, - . , , . , , .
. , 0 m. . , . , .
.
, . , ; , . ³ - , . , , , . ; .
ϳ , . .
.
|
|
|
' . , , , :
9. ?
10. ?
11. ?
12. ' ?
13. (, )?
14. ?
, - -. , .
.
, ' , .
, .
- , n- . f(n) , (, . .), n. , , f(n) , n, . , . ' , .
f(n) [g(n)] , g (n) n,
n∞ lim(f(n) / g(n))=constant¹0
, f(n) = O[g(n)]. h(n) o[z(n)] n,
n∞ lim(h(n) / z(n))=0
ֳ , . , f(n) O[g(n)], , , n∞. f(n) o[g(n)], g(n) , f(n).
.
a) f(n)=2n5+6n4+6n2+18 O(n5),
n∞ lim((2n5+6n4+6n2+18)/n5)=2
o(n5,1), o(en) o(2n). ij, - , , ' .
b) f (n) = 2 n o (n!),
n∞ lim (2n / n!)=0
, 2n O(2n+1) o(5n-1)
c) f(n)= 1000*n^(1/2) o(n).
f(n) ; O(n2) , .
³ . . , n O(n2) , O(n!) O(nn) .
.
( ). ³ , O(n!). , O[(n-1)!] . , O(n) . - O(n!).
, 20 , . , , (, , , ) 10-10 . , 20!2*1018, 6 7 .
. , , ' .
.
, .
? . - , , . , . , .
|
|
|
. , .
. , . . , - . , , . , , , , .
, , , , . , .
.
: , , .
. , . , -, -, , , / .
1.
:
1. .
2. , , .
3. , , .
4. [; ].
5. N (0 <N <99).
6. .
7. , [, ].
8. .
9. 2- , : , .
10. , : , .
11. , .
12. , X, Y, Z : X = Y = Z.
13. : . .
14. N. 1,2,..., N , .
15. N. ', N, N +1, N +2,...., 2N "", , . , .
16. , , , . 0.
17. 3 , N * N. .
18. 3 , 2 * N. , .
19. 3 , 2 * N. , .
20. 3 , 2 * N. , , - .
21. 3 , 2 * N. , .
22. .
23. : N ,
1£2£3£...£n
B1£B2£B3£...£Bm
+ N ( ), :
1£2£3£...£n+m
24. .
25. .
26. , .
27. .
28. .
29. .
30. .
:
:
1. . . , , , , , ( ), .
2. . . - .
3. . , , . . .
4. ˳ .
5. . ϳ .
6. .
2
: . .
, .
.
, . , . , .
. 1
.
1. .
2. ( , . . .)
3. - , , . i- , , i- . , .
4. . ( )
.
, .
' , .
. . , ?
G1 G2 , - G1 G2, , 1 2 G1 , G2 .
, , . , , .
. .
 |
, , ( ) .
, , G1 G2: 10 3 . - h V1 V2 ; 10! . G1 G2 10! , , .
, .
G , , G. :
1. ׳ .
2. .
3. ׳ .
4. .
:
1. ³, , , ' , .
2. , - ( .)
, . , , . , . , , .
 |
.
, A (G). , G G1 , A (G) A (G1). G G1 M , O(!) . , .
A2 (Gi) i = 1, 2. A2 (G1) A2 (G2) , . G1 G2 , . , . , , , , ' , .
2.
, :
1. . 12 .
2. .
3. .
4. .
5. .
6. .
7. ' .
8. .
9. .
10. .
11. .
12. .
13. .
14. .
15. .
16. .
17. .
18. г .
19. , .
20. .
21. , .
22. . , .
23. . , .
24. , .
:
:
1. . . , , , , , ( ), .
2. . . - .
3. . , , . . .
4. ˳ .
5. . ϳ .
6. .
3
: .
, .
˳ - (), , . ʳ , .
' , ' , ( ) head. , , .
, .
:
typedef struct TNode / * * /
{
float val; / * , * /
TNode * n; / * * /
}
:
:
1. ;
2. ;
3. ;
, .
:
, .
:
, .
:
3.
' . .
, ' .
1. , : . 䳿:
a) ;
b) j- i- ( , 0);
c) i- j- ;
d) i- ﳺ j-;
2. , : . 䳿:
a) i- ﳿ j- ;
b) j- ;
c) , , i () j ();
d) .
3. , : . 䳿:
a) , ;
b) ;
c) E1 2;
d) .
4. , : . 䳿:
a) , ;
b) ;
c) E1 2;
d) .
5. , : . 䳿:
a) , ;
b) , , ;
c) , ;
d) ( ).
6. , : . 䳿:
a) , ;
b) , , ;
c) , ;
d) .
7. , : . 䳿:
a) ;
b) , ;
c) , , ;
d) .
8. , : . 䳿:
a) ;
b) , ( );
c) , ;
d) .
9. , : . 䳿:
a) 1 , ;
b) 1 2 ;
c) ;
d) .
10. , : . 䳿:
a) ;
b) ;
c) , ;
d) .
11. , : . 䳿:
a) ;
b) ;
c) ;
d) .
12. , : . 䳿:
a) ;
b) ﳿ ;
c) , ;
d) , .
13. , : . 䳿:
a) L1 L2;
b) L1 L2, L1;
c) , ;
d) , , .
14. , : . 䳿:
a) , ;
b) ;
c) ;
d) E1 E2.
15. , : . 䳿:
a) ;
b) , ;
c) ;
d) .
16. , : . 䳿:
a) , , ;
b) , ( ). , - ;
c) , ;
d) .
17. , : . 䳿:
a) L1 L2;
b) ;
c) , ;
d) .
18. , : . 䳿:
a) ;
b) , L1 L2;
c) , ;
d) ( ).
19. , : . 䳿:
a) ;
b) , ;
c) ;
d) .
20. , : . 䳿:
a) ;
b) , ( ). , - ;
c) ;
d) .
:
:
1. . . , , , , , ( ), .
2. . . - .
3. . , , . . .
4. ˳ .
5. . ϳ .
6. .
4
: .
, .
.
. ? . () . , . : ' ( ) .
', .
' '. , , ', . ' . ' . , .
. , . .
, . , , , .
- , .
.
1. O (k * f) = O (f)
2. O (f * g) = O (f) * O (g) O (f / g) = O (f) / O (g)
3. O (f + g) O (f) O (g)
k , a f g - .
, .
1,5 * N = O (N)
, .
O ((17 * N) * N) = O (17 * N) * O (N) = O (N) * O (N) = O (N * N) = O (N2)
, , .
O(N5 + N2) = O(N5)
.
O (1)
. . - , , .
(N)
.
(N2), (N3), (N)
. (N2)- , (N3) -
(Log (N))
, N. , .
O (N * log (N))
, , , , ' .
O (2N)
. .
. .
. , . , .
. , .
For i: = 1 to N do
Begin
...
End;
O (N), N , O (1).
, .
For i: = 1 to N do
For j: = 1 to N do
Begin
...
End;
(N2).
.
- .
: . , . . , .
function search (low, high, key: integer): integer;
var mid, data: integer;
begin
while low <= high do
begin
mid: = (low + high) div 2;
data: = a [mid];
if key = data then
search: = mid
else
if key <data then
high: = mid-1
else
low: = mid +1;
end;
search: =- 1;
end;
:
. . , n n/21 n/22 n/23 n/24... n/2m
m, n/2m <2 n <2m +1
m - , n/2m <2,
(n/2m-1 > = 2) (2m <= n)
, 2m = < n <2m+1
³ m =< (log2n = x) <m +1
m - , = <.
, O (log2n).
