.


:




:

































 

 

 

 





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).

 





:


: 2016-03-27; !; : 809 |


:

:

,
==> ...

1019 - | 833 -


© 2015-2024 lektsii.org - -

: 0.372 .