.


:

:



,



( , )

:

































 

 

 

 
FAQ

⇐ 123



 

0
, , .
- , () ().
.
().
.
- , .
- , , .
, .
, , .
.

:

: - -:

1. . , .

2. , , .

L0 - ,

V1 - ,

V2 - ,

T - ,

L1 - .

3. .

4. , ( 4- ).

5. , a, b, (c+k), k=1,2,...,15.

6. S=m(m+1)(m+2)...(m+n), m, n- .

 

:

1) .

2) ?

3) , ?

4) , -?

5) , -?

 

: 1.3, 1.4, 1.5.

2 " "

: .

: .

: 4 .

:

:

1. , . , . S={S1,S2,.,Sm}, . ( S1) .

2. , . , .

3. (), . . {q1,q2,,qn}. , . .

, : , , ,

;

;

.

{q1,q2,,qn} {,,} .

. S, . . q1. Sk qi, qj, Sk Sl ( ) .

 

qiSk qjSl (,).

, .

, (2,3)-.

 

:

 

      S1 S2 Sk Sm              

 

Q - , - . .

( ) U . , U. , , B, , U B.

, , U.

, .

: {1, +, Ù}, Ù .

{q1, q2, q3,!}, q1 , ! .

:

 

                       
            +          

:

                         
                         

 

, , :

 

1q1 →Ùq3 1q3→1q3 +q3→+q3 Ùq3→1q2H +q2 →+q2 1q2→1q2 Ùq2 →Ùq1 +q1 →Ù!

=q1, :

                     
          +          

 

YY=q3, .

 

                     
          +          

 

                     
          +          

 

YY q2. .

YY q1 (.)

 

                     
          +          

, , , .

 

  q1 q2 q3
  Ùq3 1q2 1q3
Ù Ùq1 Ùq1 1q2H
+ Ù! +q2 +q3

 

:

  1. ,

. A={1,0}, u=1010101,

  q1 q2
  0q2 0q2
  1q0 0q1

. A={1,0}, u=111

  q1 q2
  1q1 0q2
  0q2 1q0

. A={1,0}, u=1001011

  q1 q2
  0q2 1q2
  1q0 0q1

. A={1,0}, u=110001

  q1 q2 q3
  1q3 1q2 1q1
  1q2 1q3 1q0

 

  1. A = {a0, 1} Q = {q0, q1,..., q13} :
Q A
a0 1
q1 q2a0L q01
q2 q5a0 q3 a0
q3 q4a0L q01
q4 q51 q41L
q5 q0a0 q61L
q6 q0a0 q7a0
q7 q8a0R q01
q8 q91 q81R
q9 q0a0 q101L
q10 q0a0 q11a0
q11 q12a0L q01
q12 q131 q121L
q13 q0a0 q01

, , ( q1 , a0, a01 a0111 a0.

:

  1. ,

A={1,0}, u=111,

  q1 q2
  1q2 0q2
  1q0 0q1

:

2. A = {a0, 1} Q = {q0, q1,..., q13} :

 

Q A
a0 1
q1 q2a0L q01
q2 q5a0 q3 a0
q3 q4a0L q01
q4 q51 q41L
q5 q0a0 q61L
q6 q0a0 q7a0
q7 q8a0R q01
q8 q91 q81R
q9 q0a0 q101L
q10 q0a0 q11a0
q11 q12a0L q01
q12 q131 q121L
q13 q0a0 q01

, , ( q1 , a0, a011 a01111 a0.

:

a011 a01111 a0

a011 a01111 a0 q1 a011 a01111 q2 a0 a011 a0111 a0 q3 a0 a011 a0111 q4 a0a0 a011 a011 q4 1a0a0 a011 a01 q4 11a0a0 a011 a0 q4 111a0a0

a011 1 q5 111a0a0 a011 q6 1111a0a0 a01 a0 q7 1111a0a0 a01 a0 1 q8111a0a0 a01 a0 11q811a0a0 a01 a0 111q81a0a0 a01 a0 1111q8a0a0

a01 a0 1111a0q8a0 a01 a0 11111q9a0 a01 a0 1111q101a0 a01 a0 111 a0q111a0 a01 a0 111 q12 a01a0 a01 a0 11 q12 1a01a0 a01 a0 1 q12 11a01a0

a01 a0 q12 111a01a0 a01 1 q13 111a01a0 a01 1 q0 111a01a0

: a01 1 q0 111a01a0

:

1) ?

2) ?

3) ?

4) ?

 

: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 2.3, 2.4, 2.5.

 

3 " "

: .

: .

: 4 .

:

.

 

" " (). , , .
:

  • , .
  • .
  • .
  • , .
  • .
  • .
  • .

. -> , , <Ins>. " ":

, , -> , , <Ctrl>+<Del>. , , .

: , , ( ), ( ).

, . -> , , <Shift>+<Ins>. " ":

, , , -> , , <Shift>+<Ctrl>+<Del>. , , .

: < > - ( , ).

, . -> , , <Ctrl>+<E>. :

. ( ): < > <> < >,

< > - ;

<> - : , , , - , ;

< > - .

: _ 0, - _, ( ).

- -. . .

, . / (), .

, . -> , , <Shift>+<Ctrl>+<Ins>. " ":

, -> , , <Ctrl>+<D>. , , .

. : , , .

. . .

, , . : , .. . .

. .

. : , , . , . : .

, -> , , <F9>. , , : . ( : ).

, , <Ctrl>+<P>, -> . , <F8> ( -> ). , .

. : , . , , , . , , -> , <Ctrl>+<F2>.

: -> <Shift>+<Ctrl>+<F9>. , .

, .

, -> , <Ctrl>+<Q>. , , " ":

:

. .

  1. F(x)=x+y
  2. F(x)=x-y
  3. F(x)=2x+y
  4. F(x)=3x
  5. F(x): 2
  6. F(x)= 2y
  7. F(x): 3
  8. F(x)=x+2y

:

1. .

2. .

3. ?

 

: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 2.3, 2.4, 2.5.

 

4 " "

:.

: .

: 4 .

, , . , , . , , - .. , .

, , . - , , .

, . , , . , . . - . - .

- T(n), ( n) , ().

- S(n), ( n) () .

() , . , .

, f(n) g(n), c n0, n ³ n0, f(n) £ c * g(n) [7]. : f(n) O (g(n)). . , f(n) = 10*n3 O (n3), .. c=10 n0 = 1, 10*n3 £ 10*n3. , 10*n3 O (n2), c n0 , f(n) ³ c * g(n) n ³ n0.

. , , . , , , , .

, . . ( ), , .

. , , , .. . ( ) .

.

, () , .

. l(i)- , :

æ [ log2 i ] + 1, i ¹ 0;

l(i) = í

è 1, i=0.

[...] - .

, l(i), i - .

( ) . - l(xi), xi - , i- .

.

. .

. , , , , , . i - , j - "" ( elem_up), A(j) - j- , n - . , , :

program Sort;

procedure elem_up (i: integer); { }

begin

j:= i

while (j > 1) and (A(j) < A(j-1)) do

begin

X:= A(j); { }

A(j):=A(j-1);

A(j-1):=X;

j:= j-1;

end

end;

begin { }

for i:= 2 to n do elem_up(i);

end.

. , n , - . (n-1) . elem_up ("" ) - i . , :

n

å i = (n+2)*(n-1)/2 = (n2+n-2)/2.

i=2

, O(n2).

. i- log(i). :

n

å log(i) = log(n!)

i=2

elem_up . -, "" j. i 1, i- :

log(i) + log(i-1) +... + log1 = log(i!).

n :

n n

å log(i!) = log(Õ (i!)).

i=2 i=2

-, ( ). log(Amax), Amax - . i- i*log(Amax). :

n

å(i*log(Amax)) = (n*(n+1)/2)*log(Amax).

i=2

: n

log(n!) + log(Õ (i!)) + (n*(n+1)/2)*log(Amax).

i=1

n

O(MAX(log(Õ (i!)), n2*log(Amax)).

i=1

. n , O(n).

. , - :

log(n) + n*log Amax.

O(n*log Amax).

 

:

.

- n!.

- nn.

- A(n,m)= n!/(m!*(n-m)!).

- n , ( ).

 

:

  1. ?
  2. ?
  3. ?
  4. ?

: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 2.3, 2.4, 2.5.

 

 


1.1 Turbo Pascal. . 2- . / .. . .: , 2003 230 .

1.2 Turbo Pascal. : . 2- . / .. . .: , 2004. 496 .

1.3 .. . : , -, 2008. 432 .

1.4 .. . : -, 2008. 440 .

1.5 .. : . : , -, 2006. 416 .

1.6 ., Turbo Pascal : . : -, 2006. 256 .

1.7 .. ++ - : : . : , 2007. 288 .

1.8 .., Turbo Pascal : . : , 2003. 528 .

2.1 .., .. ++. - : . .: , 2008. 264 .

2.2 .. . . 2-, . .: . ̻, 2006. 288 .

2.3 . : / .. . .: , 2007 325 .

2.4 .., .. Turbo Pascal 7.0/ . .. 6- . .:+, 2006. 464 .

2.5 .., .. Turbo Pascal 7.0. . .: , 2006 168 .

 

230115

 

 

⇐ 123


:

: 2016-10-06; !; : 779 |

:

:

, .
==> ...

1619 - | 1431 -


© 2015-2024 lektsii.org - -

: 0.185 .