, , , , , . .

 

 

!

 

:

:

 

 

 

?

StudentHelp, , MS Word. , , antiplagiat.ru, etxt.ru advego.ru. StudentHelp , Word .


:


:

: . : 05.07.2012. : 2010. : 9. antiplagiat.ru: < 30%

():



()


. .
(Ƞ )






:



:








. 2009 .
:



..3
    腅...4
    , 텅4
    ꅅ..5
    ....5
    6
    ..7
    ...7
    酅..9
    14
    .15
.17
...18
















, [1,2]. , .
, , backtracking algorithms ( ). , [3].
[3-5]. , N M , . , ( N*M-1 ). , .



















1. .


:
    , ( 1);
    ( 2);
    ( 3);
    ( 4).


1.1. , .

( ), . , , . , , , . , , , .
:

int solution_impossible ()
{
//
// , .
return ((size_x*size_y) % 2 != 0) && ((start_x+start_y) % 2 != 0);


, . , 3*7, , , (2,4).

1.2. .

, , , , . , .
, , .   , , (, 100*100 ).


1.3. .

[5], , . , . , , , , [5]. , .






1.4. .

, , :
int possible_moves_sh [] [2] = {
{-1, -2}, {-2, -1}, {-2, 1}, {1, -2},
{-1, 2}, {2, -1}, {1, 2}, {2, 1} };

. . , . (GOOD_RET), , . MAX_RET. GOOD_RET , , , , . (, 14*3) (,100*100 ).










2. .

2.1. .

:
    , ;
    , , ;
    , ( );
    , . , .
, :

int possible_moves_sh [] [2] = {
void find_path ()
{
for ( move_num = 1 ; move_num <= max_moves ; )
{
if( make_move() ) // .
move_num++ ;
else // .
if (move_num > 1 )
{
undo_move() ; // .
move_num-- ;
}
else
return ; // .
}
}


, . , . .
. 1 3 4 (2,4).   .

1. 3 4 (2,4)

(2,4) 4 (2,1) 3 (1,1)
2 (3,2) 4 (3,4) 4 (2,3)
3 (1,3) 5 (2,2) 5 (3,1)
4 (2,1) 6 (1,4) 6 (1,2)
5 (3,3) 7 (3,3) 7 (3,3)
6 (1,4) 8 (1,2) 8 (1,4)
7 (2,2) 9 (3,1) 9 (2,2)
8 (3,4) 10 (2,3) 10 (3,4)
8 (3,4) 11 (1,1) 11 (1,3)
7 (2,2) 11 (1,1) 12 (2,1)
6 (1,4) 10 (2,3)
6 (1,2) 9 (3,1) (2,4),
7 (3,1) 8 (1,2) 19:
8 (2,3) 8 (2,1) 3 12 5
9 (1,1) 8 (2,1)
9 (1,1) 7 (3,3) 6 9 2
8 (2,3) 6 (1,4)
7 (3,1) 5 (2,2) 11 4 7
6 (1,2) 4 (3,4)
5 (3,3) 3 (1,3) 8 1 10

. , 6*6 (5,2) 290 .






2.2. .

[5] , N*M M*N:
    N,M < 3; N = 3, M = 5,6; N = M = 4;
    , N = 3, M = 4; N = 3, M >= 7; N >= 4, M >= 5.
, . [5] .
. , , . N. , (MAX_RET = 400000), , LIM. , , , ( A E), (GOOD_RET = 1). , , A . .

, 5 5, . 2.




2. 5 5
1 33951 N 212310 N 4543
N 52061 N 123374 N
69216 N 23411 N 32116
N 214142 N LIM N
1300 N 325867 N 30565
1 3 0 N 127 N 0
N 0 N 0 N
127 N 0 N 0
N 0 N 0 N
0 N 127 N 0
1 2 950 N 4676 N 256
N 1596 N 3057 N
2102 N 629 N 1417
N 4296 N 7463 N
94 N 4426 N 381
1 4 0 N B0 N 0
N 0 N 0 N
B0 N 0 N 0
N 0 N 0 N
0 N D0 N 0
1 3 0 N 1709 N 0
N 0 N 0 N
1709 N 0 N 0
N 0 N 0 N
0 N 1709 N 0
(5,5), 0: 5 14 19 24 3
20 9 4 13 18
15 6 23 2 25
10 21 8 17 12
7 16 11 22 1

, 7 7, . 3.

3. 7 7
1 29032 N LIM N
LIM N LIM
N LIM N LIM
N 172170 N
19396 N 19396 N
LIM N LIM
N 29032 N LIM
N LIM N
LIM N 39629 N
14807 N LIM
N LIM N LIM
N LIM N
6415 N 33488 N
386809 N LIM




1 3 8339 N 0 N 0 N 0
N 0 N 0 N 0 N
0 N 0 N 3 N 0
N 0 N 0 N 5972 N
0 N 14204 N 0 N 0
N 0 N 5972 N 0 N
0 N 0 N 0 N 0
1 2 1426 N 17178 N
293292 N 17178
N LIM N
302303 N 3353 N
966 N 966 N
LIM N 133190
N 1426 N LIM
N 28390 N
70852 N 2052 N
980 N 30757
N 9903 N LIM
N 24272 N
491 N 681 N
5118 N 108858
1 4 B0 N 0 N 0 N 0
N 0 N 0 N 0 N
0 N 0 N B0 N 0
N 0 N 0 N B0 N
0 N D0 N 0 N 0
N 0 N B0 N 0 N
0 N 0 N 0 N 0
1 3 291565 N 0 N
0 N 0
N 0 N 0
N 0 N
0 N 0 N
375 N 0
N 0 N 0
N LIM N
0 N LIM N
0 N 0
N 0 N LIM
N 0 N
0 N 0 N
0 N 0



(7,7), 0: 9 6 11 40 29 4 27
12 39 8 5 26 43 30
7 10 35 44 41 28 3
36 13 38 25 48 31 42
19 16 47 34 45 2 23
14 37 18 21 24 49 32
17 20 15 46 33 22 1


8 8 :
    1 2 (MAX_RET). (5, 5) 2502;
    1 3 , (4, 1) (6, 4), . 9 79 , ;
    1-3 (6, 4) . ;
    1-4 . (6, 4) .
9 9 , , 1-3 ( 1-4, , ).
50 50 :
    1-3 , , ;
    1-4 .
77 77, , , :
    1-3 , , ;
    1-4 .
100 100 :
    1-3 , , ;
    1-4 , (94, 24) (94, 79), .
, . , 14 3, . 4.
4. 14 3
1 4 B0 B0 E997 E45274 B0 E0 0 B0 D0 0 E17 E626
0 0
B0 E390577 E56 0 0 C0 E16 E10378 B0 0 0
E1006 E67 0
B0 B0 E997 E45274 C0 B0 C0 B0 C0 B0 E17 E626
0 0
(14, 3), 0: 20 17 14 11 26 23 32 9 30 7 36 39
2 5
15 12 19 22 33 10 25 28 35 40 3 6
37 42
18 21 16 13 24 27 34 31 8 29 38 41
4 1













3.

젖 [2]. , , :
int find_path ( int cur_x, int cur_y, int move_num )
{
desk_state [cur_x] [cur_y] = nove_num ; // .
if ( move_num > max_moves ) return 1 ; // .
// .
for ( int I = 0 ; I < 8 ; i++ )
{
int next_x = cur_x + possible_moves [i] [0] ; // .
int next_y = cur_y + possible_moves [i] [1]

if ( move_possible (next_x, next_y )
&& find_path (next_x, next_y, move_num+1 )) return 1 ;
}
// .
desk_state [cur_x] [cur_y] = 0 ;
back_ret++ ;
return 0 ;
}
, .














4. .

, [2].
, , [7]. , [8].
, . . 1, 2 .




. 1.
, . , .




. 2.
, , :
void find_path_switch ( int limit )
{
y = 0 ;

do
switch ( y )
{
case 0 :
if ( x4 () ) y = 3 ;
else
{ z1_0 () ; y = 1 ;}
break ;
case 1:
if ( x1() ) y = 4 ;
else
if ( x3() ) { z1_1() ; }
else
if ( x2() ){ z2 () ; z1_2() ; y = 2 ; }
else y = 3 ;
break ;
case 2 :
if ( x5 (limit) ) y = 5 ;
else
y = 1 ;
break ;
case 3 : y = 0 ; break ;
case 4 : y = 0 ; break ;
case 5 : y = 0 ; break ;
}
while ( y < 3 ) ;
}


, . , , Pentium II 400 , 200 200 20 ( 0,03 ). . , , [5]. , 2000 2000 , , .
, , , .














:
    . : AI //. 2002. 7.
    . + = . .: : , 1985.
    . : //. 2002. 3.
    . . .: , 1974.
    . . .: , 1983.
    . ., . . //. 2002. 4.
    . ., . . // . 2001. 6.
    ..................



90% antiplagiat.ru, etxt.ru advego.ru




* . , .