Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Xây dựng thuật toán cho nước đi bàn cờ nxn. Di chuyển tốt ko lặp lại nước đã đi

  1. #1
    Ngày gia nhập
    03 2009
    Bài viết
    7

    Mặc định Xây dựng thuật toán cho nước đi bàn cờ nxn. Di chuyển tốt ko lặp lại nước đã đi

    đề như sau

    Trên bàn cờ nxn có một con tốt nằm ở góc trái dưới. Hai người chơi trò như sau: Mỗi người được đi con tốt một nước sang ô bên cạnh. Không được đi con tốt vào ô đã đi qua. Người thua cuộc là người không đi được nước của mình.
    Lập thuật toán tối ưu cho các người chơi ( nếu n chẵn, người đi đầu thắng, n lẻ người đi sau thắng).

  2. #2
    Ngày gia nhập
    05 2008
    Bài viết
    224

    bài nỳ thuộc chương trình ôn thi olympic , phần các trò chơi , bạn tìm hiểu thêm một số bài tương tư, tuy nhiên ko nên tập trung học vào hướng này trừ phi bạn muốn ôn thi olympic
    Em có thấy nắng vàng kỷ niệm
    Hạ ngồi ru thanh thản những môi cười
    Thuở ngồi ngóng tay choàng tay nỗi nhớ
    Vin tay vào tháng năm chơi vơi...

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    7

    bài này là đề tài môn học mà mình phải nộp cho giảng viên chứ mình ko có dự định đi olympic làm gì . Vì ậy ai biết bài giải hoặc thuật toán thì chỉ mình nha . Càng nhanh càng tốt để mình còn viết nữa . Thank trước nha!!!!!!

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đi ngang hết qua phải rồi đi lên 1 ô rồi đi sang trái hết vì "Tốt" không thể đi lùi mà. Đi hết n ô lại sang phải cứ vậy mà làm thôi cho tới khi 2 tốt gặp nhau. Chú ý cái này sẽ giải ra thôi !
    nếu n chẵn, người đi đầu thắng, n lẻ người đi sau thắng).

  5. #5
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Nhìn cái topic sốc thiệt á.

    Bạn có thể nói cho mình nó hay ở chổ nào được không? Nếu đúng là nó hay như bạn nói và nếu trong khả năng của mình, mình sẽ cố đưa ra 1 cái gì đó cho bạn .
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 01-03-2009 lúc 09:39 PM.

  6. #6
    Ngày gia nhập
    01 2009
    Nơi ở
    Hà Nội
    Bài viết
    205

    Mặc định Xây dựng thuật toán cho nước đi bàn cờ nxn. Di chuyển tốt ko lặp lại nước đã đi

    Chủ đề hay ở chỗ đó là bài tập mà bạn ấy phải làm, còn khó thì đương nhiên rùi.

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Bài này không khó, suy nghĩ tí là ra thôi, con tốt không đi ngược được và mỗi lần chỉ move qua trái hay phải, lên đúng 1 ô. Cách duy trì nước đi tối ưu sẽ là cách đi như tui đã nói ở trên nhưng hình như điều kiện của chủ topic bị sai. Trong trường hợp N lẻ thì thằng đi trước mới thắng.
    - Tui nháp thử và kết quả là N chẵn thằng đi trước die trước T_T, nhưng tui nghĩ có thể tui hiểu sai điều kiện đi trước hoặc sau, cậu coi thật kĩ lại đề bài xem. Tui demo thử :
    Java Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    4.  
    5. using namespace std;
    6.  
    7. const unsigned N = 7;
    8.  
    9. vector< vector< char > > chess_board( N, vector< char >( N, '_' ) );
    10. bool check_board[ N ][ N ] = { 0 };
    11.  
    12. enum direction { LEFT_D, RIGHT_D, UP_D };
    13. enum bishop_type { BOTTOM_POSITION, TOP_POSITION };
    14.  
    15.  
    16. class Bishop {
    17.    
    18. public :
    19.     unsigned dx, dy;
    20.     direction dir;
    21.     bishop_type bt;
    22.     string bis_name;
    23.  
    24. public :
    25.     Bishop( const string& bis_name, unsigned dx, unsigned dy, direction dir, bishop_type bt )
    26.         :bis_name( bis_name ), dx( dx ), dy( dy ), dir( dir ), bt( bt )
    27.     {   }
    28.    
    29. public :
    30.     void move( direction d );
    31.  
    32. };
    33.  
    34. void Bishop::move( direction d ) {
    35.  
    36.     if( bt == BOTTOM_POSITION ) {
    37.    
    38.         if( dir == RIGHT_D )
    39.             dy = dy + 1;
    40.         else if( dir == LEFT_D )
    41.                 dy = dy - 1;
    42.         else
    43.             dx = dx - 1;
    44.     }
    45.     else {
    46.        
    47.         if( dir == RIGHT_D )
    48.             dy = dy - 1;
    49.         else if( dir == LEFT_D )
    50.             dy = dy + 1;
    51.         else
    52.             dx = dx + 1;
    53.     }
    54.  
    55. }
    56.  
    57. inline ostream& operator <<( ostream& o, const Bishop& bis ) {
    58.        
    59.     o << "Bishop " << bis.bis_name << " moving to the ";
    60.        
    61.     switch( bis.dir )
    62.     {
    63.     case LEFT_D :
    64.         o << "left : " << endl;
    65.         break;
    66.     case RIGHT_D :
    67.         o << "right : " << endl;
    68.         break;
    69.     case UP_D :
    70.         ( bis.bt == BOTTOM_POSITION ) ? o << "top : " : o << "bottom : ";
    71.         break;
    72.     default :
    73.         break;
    74.     }
    75.  
    76.     return o << "\t->[ " << bis.dx << ", " << bis.dy << " ] " << endl;
    77.  
    78. }
    79.  
    80.  
    81. void draw_board( const Bishop& b1, const Bishop& b2 ) {
    82.    
    83.     for( int x = 0; x < N; ++x ) {
    84.         for( int y = 0; y < N; ++y ) {
    85.             if( ( x == b1.dx && y == b1.dy ) || ( x == b2.dx && y == b2.dy ) )
    86.                 cout << 'x' << " ";
    87.             else if( check_board[ x ][ y ] == true )
    88.                 cout << '.' << " ";
    89.             else
    90.                 cout << chess_board[ x ][ y ] << " ";
    91.         }
    92.         cout << endl;
    93.     }
    94.     cout << endl << endl;
    95.  
    96. }
    97.  
    98. void play_move() {
    99.  
    100.     Bishop bishop_no1( "bis_no.1", N - 1, 0, RIGHT_D, BOTTOM_POSITION );
    101.     Bishop bishop_no2( "bis_no.2", 0, N - 1, RIGHT_D, TOP_POSITION );
    102.  
    103.     bool no_more_move = false;
    104.     string loser;
    105.  
    106.     do {
    107.        
    108.         /*
    109.             Start bishop-1 move
    110.             ...*/
    111.         {
    112.            
    113.             direction bishop_no1_dir = bishop_no1.dir;
    114.        
    115.             if( bishop_no1_dir == RIGHT_D ) {
    116.  
    117.                 cout << bishop_no1 << endl;
    118.  
    119.                 if( check_board[ bishop_no1.dx ][ bishop_no1.dy + 1 ] == false ) {
    120.            
    121.                     bishop_no1.move( RIGHT_D );
    122.  
    123.                     if( bishop_no1.dy == N - 1 )
    124.                         bishop_no1.dir = UP_D;
    125.  
    126.                     check_board[ bishop_no1.dx ][ bishop_no1.dy ] = true;
    127.                
    128.                 }
    129.                 else {
    130.  
    131.                     no_more_move = true;
    132.                     loser = bishop_no1.bis_name;
    133.                     break;
    134.                 }
    135.  
    136.             }
    137.             else if( bishop_no1.dir == LEFT_D ) {
    138.  
    139.                 cout << bishop_no1 << endl;
    140.  
    141.                 if( check_board[ bishop_no1.dx ][ bishop_no1.dy - 1 ] == false ) {
    142.                
    143.                     bishop_no1.move( LEFT_D );
    144.  
    145.                     if( bishop_no1.dy == 0 )
    146.                         bishop_no1.dir = UP_D;
    147.  
    148.                     check_board[ bishop_no1.dx ][ bishop_no1.dy ] = true;
    149.                
    150.                
    151.                 }
    152.                 else {
    153.  
    154.                     no_more_move = true;
    155.                     loser = bishop_no1.bis_name;
    156.                     break;
    157.                 }
    158.             }
    159.             else {
    160.  
    161.                 cout << bishop_no1 << endl;
    162.  
    163.                 if( check_board[ bishop_no1.dx - 1 ][ bishop_no1.dy ] == false ) {
    164.                    
    165.                     bishop_no1.move( UP_D );
    166.                    
    167.                     if( bishop_no1.dy == N - 1 )
    168.                         bishop_no1.dir = LEFT_D;
    169.                    
    170.                     if( bishop_no1.dy == 0 )
    171.                         bishop_no1.dir = RIGHT_D;
    172.                    
    173.                     check_board[ bishop_no1.dx ][ bishop_no1.dy ] = true;
    174.                    
    175.  
    176.                 }
    177.                 else {
    178.  
    179.                     no_more_move = true;
    180.                     loser = bishop_no1.bis_name;
    181.                     break;
    182.                 }
    183.             }
    184.        
    185.         } // End bishop-1 move
    186.  
    187.  
    188.         /*
    189.             Start bishop-2 move
    190.             ...*/
    191.         {
    192.            
    193.             direction bishop_no2_dir = bishop_no2.dir;
    194.             if( bishop_no2_dir == RIGHT_D ) {
    195.  
    196.                 cout << bishop_no2 << endl;
    197.  
    198.                 if( check_board[ bishop_no2.dx ][ bishop_no2.dy - 1 ] == false ) {
    199.                     bishop_no2.move( RIGHT_D );
    200.                    
    201.                     if( bishop_no2.dy == 0 )
    202.                         bishop_no2.dir = UP_D;
    203.                    
    204.                     check_board[ bishop_no2.dx ][ bishop_no2.dy ] = true;
    205.                 }
    206.                 else {
    207.  
    208.                     no_more_move = true;
    209.                     loser = bishop_no2.bis_name;
    210.                     break;
    211.                 }
    212.             }
    213.             else if( bishop_no2_dir == LEFT_D ) {
    214.  
    215.                 cout << bishop_no2 << endl;
    216.  
    217.                 if( check_board[ bishop_no2.dx ][ bishop_no2.dy + 1 ] == false ) {
    218.                    
    219.                     bishop_no2.move( LEFT_D );
    220.                    
    221.                     if( bishop_no2.dy == N - 1 )
    222.                         bishop_no2.dir = UP_D;
    223.  
    224.                     check_board[ bishop_no2.dx ][ bishop_no2.dy ] = true;
    225.                 }
    226.                 else {
    227.  
    228.                     no_more_move = true;
    229.                     loser = bishop_no2.bis_name;
    230.                     break;
    231.                 }
    232.             }
    233.             else {
    234.                 cout << bishop_no2 << endl;
    235.                 if( check_board[ bishop_no2.dx + 1 ][ bishop_no2.dy ] == false ) {
    236.                        
    237.                     bishop_no2.move( UP_D );
    238.                    
    239.                     if( bishop_no2.dy == 0 )
    240.                         bishop_no2.dir = LEFT_D;
    241.                    
    242.                     if( bishop_no2.dy == N - 1 )
    243.                         bishop_no2.dir = RIGHT_D;
    244.                    
    245.                     check_board[ bishop_no2.dx ][ bishop_no2.dy ] = true;
    246.                 }
    247.                 else {
    248.  
    249.                     no_more_move = true;
    250.                     loser = bishop_no2.bis_name;
    251.                     break;
    252.                 }
    253.             }
    254.  
    255.         } // End bishop-2 move
    256.  
    257.         // draw move
    258.         draw_board( bishop_no1, bishop_no2 );
    259.         cout << "---> Press enter to watch move \n";
    260.         cin.get();
    261.     }
    262.     while( no_more_move == false );
    263.  
    264.     ( loser == bishop_no1.bis_name ) ?
    265.         cout << "Winner is bishop 2 !!!\n"
    266.         :
    267.         cout << "Winner is bishop 1 !!! \n";
    268.  
    269. }
    270.  
    271. int main() {
    272.  
    273.     play_move();
    274.  
    275.     return 0;
    276.  
    277. }

  8. #8
    Ngày gia nhập
    03 2009
    Bài viết
    7

    mình nói bài này hay ko phải vì bài này mình phải làm mà vì mình thấy bài này hay nên mình chọn nó làm bài tiểu luận . Vì trong 70 đề thì bài này thuộc dạng khó trong đó nên mình thử sức nhưng thiệt là suy nghĩ ko ra nên mình mới post lên cho các bạn tìm giải pháp giúp . Để mình test thử bài đã nhưng cũng thank các bạn nhiều nha .

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Coi kĩ lại cái đề dùm tui được không cậu ? N chẵn là win hay lose vậy ? Còn đề thì cậu cứ post hết 70 cái lên 1 host nào đi rùi tui sẽ down về coi thử ! Thanks cậu trước !

  10. #10
    Ngày gia nhập
    01 2011
    Bài viết
    1

    Mặc định Mình cũng có đề như vậy

    Vừa mới nhận đề tài đồ án hô qua, trúng đề này luôn. Đọc qua bài trả lời của rook thì không đúng rồi. Tốt đây chỉ đơn thuần là quân cờ, có thể thay bằng hạt thóc cũng được nên nó có thể đi lùi . Với giả sử bàn cờ 1x1 thì người đi đầu thua chắc rồi, nên dữ kiện đề ra là đúng đó bạn.
    Hiện tại vẫn chưa nghĩ ra thuật toán cho bài này. Mọi người có thể giúp mình một tay không

Các đề tài tương tự

  1. Thuật toán chuyển ngày dương qua âm và ngược lại
    Gửi bởi latdat089 trong diễn đàn Thắc mắc lập trình Java
    Trả lời: 1
    Bài viết cuối: 04-11-2013, 10:27 PM
  2. Thuật toán xác định ảnh chuyển động và xoay?
    Gửi bởi voicewithin trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 23-03-2012, 12:00 PM
  3. Thuật toán chuyển đổi base64
    Gửi bởi sakervista trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 24-03-2011, 06:06 PM
  4. Thuật toán chuyển mã morse.please help me!
    Gửi bởi kiensnow trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 1
    Bài viết cuối: 02-04-2010, 12:50 AM
  5. Thuật toán chuyển mã văn bản ?
    Gửi bởi tienlbhoc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 05-11-2008, 06:23 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn