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

Đề tài: Cải tiến giải thuật bài con mã đi tuần như thế nào?(với bảng 6x6)

  1. #1
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    611

    Mặc định Cải tiến giải thuật bài con mã đi tuần như thế nào?(với bảng 6x6)

    Bài mã đi tuần: cho bảng có kích thước n x n, con mã bắt đầu từ ô (0,0)
    Tìm đường đi của con mã đi qua tất cả các ô và chỉ qua mỗi ô 1 lần
    Mình có thuật toán như bên dưới, với bảng 3x3,4x4,5x5 đều cho kết không có đường đi. Với bảng 6x6 thì treo luôn
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    4. using namespace std;
    5.  
    6. vector<int> banco;
    7. vector<int> co;
    8. int n;
    9. int dx[]={2,1,-1,-2,-2,-1,1,2};
    10. int dy[]={-1,-2,-2,-1,1,2,2,1};
    11. int x=0;
    12. int y=0;
    13. void bancomoi(int m)
    14. {
    15.     n=m;
    16.     banco.resize(n*n);
    17.     banco.shrink_to_fit();
    18.     co.resize(n*n);
    19.     co.shrink_to_fit();
    20.     for(int i=0;i<n*n;i++)
    21.     {
    22.         banco[i]=-1;
    23.         co[i]=-1;
    24.     }
    25.     co[0]=0;
    26.     banco[0]=0;
    27. }
    28. int& oo(int h,int c)
    29. {
    30.     if(h<0||h>=n) throw "ngoai ban co";
    31.     if(c<0||c>=n) throw "ngoai ban co";
    32.     return banco[h*n+c];
    33. }
    34. bool otrong(int h,int c)
    35. {
    36.     if(h<0||h>=n) return false;
    37.     if(c<0||c>=n) return false;
    38.     return oo(h,c)<=-1;
    39. }
    40. void gan(int i)
    41. {
    42.     //cout<<i<<",";
    43.     //if(i>=n*n)//<------------nếu comment dòng dưới và uncomment dòng này thì chương trình bị treo với n=6
    44.     if(i>=n*n-5)//<-----------------sửa dòng bên trên thành như dòng này chỉ để kiểm tra đường đi của con mã có đúng luật hay không
    45.     {
    46.         throw "day";
    47.     }
    48.     int j=0;
    49.     int h,c;
    50.     h=co[i]/n;
    51.     c=co[i]%n;
    52.     //cout<<co[i]<<" "<<h<<" "<<c<<endl;
    53.     while(j<8)
    54.     {
    55.         //cout<<" x:"<<h<<","<<c<<":x ";
    56.         h+=dy[j];
    57.         c+=dx[j];
    58.         //cout<<":"<<h<<","<<c<<","<<otrong(h,c)<<":";
    59.         if(otrong(h,c))
    60.         {
    61.             //cout<<j<<"("<<h<<":"<<c<<")";
    62.             oo(h,c)=i+1;
    63.             co[i+1]=h*n+c;
    64.             gan(i+1);
    65.             co[i+1]=-1;
    66.             oo(h,c)=-1;
    67.         }
    68.         h-=dy[j];
    69.         c-=dx[j];
    70.         //cout<<" z:"<<h<<","<<c<<"z ";
    71.         j++;   
    72.     }
    73.     cout<<"\n";
    74. }
    75. void num(int m)
    76. {
    77.     cout.width(3);
    78.     cout<<m;
    79. }
    80. void display()
    81. {
    82.     for(int i=0;i<n;i++)
    83.     {
    84.         for(int j=0;j<n;j++)
    85.         {
    86.             num(banco[i*n+j]);
    87.         }
    88.         cout<<endl;
    89.     }
    90.     //cout<<"display\n";
    91. }
    92. int main()
    93. {
    94.     try
    95.     {
    96.         bancomoi(6);
    97.         gan(0);
    98.         //display();
    99.     }
    100.     catch (const char* loi)
    101.     {
    102.         if(loi=="day")
    103.         {
    104.             display();
    105.         }
    106.     }
    107. }
    108. // kết quả là
    109. /*
    110.    0 -1 10  5 24  3
    111.  11  6 23  2  9 14
    112.  22  1  8 13  4 25
    113.   7 12 21 28 15 18
    114.  -1 29 16 19 26 31
    115.  -1 20 27 30 17 -1
    116.  
    117. [Program finished]
    118. */
    Các bạn có thuật toán nào tốt hơn không?

  2. #2
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    998

    C Code:
    1. // vtBoard : vector được khởi tạo = -1 theo cách thức của bạn. Khi ra khỏi hàm, lần cuối nó sẽ chứa thứ tự bước tới của quân mã nếu có đường đi đáp ứng yêu cầu ( cũng theo cách thiết kế của bạn)
    2. // iCur : chỉ mục đang xét hiẽn tại
    3. // nLen : chiều dài cạnh của bàn cờ
    4. // iStep : Đếm bước nhảy của quân mã
    5. bool LoopSteps(vector<int> & vtBoard, int iCur, int nLen, int iStep)
    6. {
    7. int row = iCur/nLen;
    8. int col = iCur%nLen;
    9. vtBoard[iCur] = iStep;  // Cho đi thử
    10. int iNext;
    11. // Kiểm tra đã bước qua tất cả các ô bàn cờ
    12. if(iStep == nLen * nLen - 1)
    13. return true;
    14. // Từ 1 vị trí, quân mã có thể nhảy tới 8 ô khác, xét từng ô để đệ quy sâu hơn
    15. // Hướng 1 giờ
    16. iNext = (row - 2) * nLen + (col + 1);
    17. if(row > 1 && col + 1 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    18. return true;
    19. // Hướng 2 giờ
    20. iNext = (row - 1) * nLen + (col + 2);
    21. if(row > 0 && col + 2 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    22. return true;
    23. // Hướng 4 giờ
    24. iNext = (row + 1) * nLen + (col + 2);
    25. if(row + 1 < nLen && col + 2 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    26. return true;
    27. // Hướng 5 giờ
    28. iNext = (row + 2) * nLen + (col + 1);
    29. if(row + 2 < nLen && col + 1 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    30. return true;
    31. // Hướng 7 giờ
    32. iNext = (row + 2) * nLen + (col - 1);
    33. if(row + 2 < nLen && col > 0 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    34. return true;
    35. // Hướng 8 giờ
    36. iNext = (row + 1) * nLen + (col - 2);
    37. if(row + 1 < nLen && col > 1 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1))
    38. return true;
    39. // Hướng 10 giờ
    40. iNext = (row - 1) * nLen + (col - 2);
    41. if(row > 0 && col > 1 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1)
    42. return true;
    43. // Hướng 11 giờ
    44. iNext = (row - 2) * nLen + (col - 1);
    45. if(row >1 && col > 0 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1)
    46. return true;
    47.  
    48. vtBoard[iCur] = -1;  // quay lui
    49. return false;
    50. }
    51.  
    52. int main()
    53. {
    54. vector<int> vtBoard;
    55. int iLen;
    56. // Khởi tạo cho các thành phần cùng với các kiểm tra khác
    57. //........
    58. //........
    59. // Gọi đệ quy có thể như sau
    60. if(LoopSteps(vtBoard, 0, iLen, 0))
    61. {
    62. // xuất liệu
    63. }
    64. else
    65. {
    66. // không có đường đi
    67. }
    68. return 0;
    69. }

    Mình viết theo suy nghĩ thôi, không ở trên máy có TBD nên chưa thử nghiệm, bạn xem thử.

  3. #3
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    611

    Mình đã sửa code của bạn một chút xíu để có thể chạy được (lỗi thiếu ")" và thiếu #include)thì đã cho kết quả với n=6,7,8
    Với n=9 thì bị treo

    Để kiểm tra vị trí tiếp theo có nằm trong bảng mình dùng đến 4 lệnh so sánh, còn bạn chỉ dùng 2, còn khi có kết quả thì mình throw, còn bạn thì trả về một chuỗi các "return true" cho đến lời gọi đầu tiên

    Cảm ơn bạn đã cho mình mở rộng tầm mắt
    Ps:code sửa lại mình chưa lưu thì đã lỡ tay xóa mất mà mình nhác đánh lại và máy sắp hết pin rồi, bạn thông cảm

  4. #4
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    998

    Với n=9 thì máy báo lỗi hay mã chạy quá lâu vậy bạn. Bạn có thể đếm số lần gọi đệ quy với n=6,7,8 cho mình xem thử không. Đang mùa ở không nên kiếm cái gì vừa học vừa tiêu khiển qua ngày. Mà không có máy nên ngứa tay hà.😅😅😅😅😅

  5. #5
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    611

    Code cũ bên trên của mình có lỗi gì đó rồi, với n=5 nó không cho ra kết quả, code của bạn thì cho kết quả đúng
    Để đếm số lần gọi đệ qui, mình sửa code bạn lại như sau
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. using namespace std;
    4.  
    5. // vtBoard : vector được khởi tạo = -1 theo cách thức của bạn. Khi ra khỏi hàm, lần cuối nó sẽ chứa thứ tự bước tới của quân mã nếu có đường đi đáp ứng yêu cầu ( cũng theo cách thiết kế của bạn)
    6. // iCur : chỉ mục đang xét hiẽn tại
    7. // nLen : chiều dài cạnh của bàn cờ
    8. // iStep : Đếm bước nhảy của quân mã
    9. bool LoopSteps(vector<int> & vtBoard, int iCur, int nLen, int iStep, unsigned long long& nDeQui)
    10. {
    11. int row = iCur/nLen;
    12. int col = iCur%nLen;
    13. vtBoard[iCur] = iStep;  // Cho đi thử
    14. int iNext;
    15. nDeQui++;
    16. if(nDeQui%1000000==0)
    17. {
    18.     cout<<"("<<nDeQui/1000000<<")";
    19. }
    20. // Kiểm tra đã bước qua tất cả các ô bàn cờ
    21. if(iStep == nLen * nLen - 1)
    22. return true;
    23. // Từ 1 vị trí, quân mã có thể nhảy tới 8 ô khác, xét từng ô để đệ quy sâu hơn
    24. // Hướng 1 giờ
    25. iNext = (row - 2) * nLen + (col + 1);
    26. if(row > 1 && col + 1 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    27. return true;
    28. // Hướng 2 giờ
    29. iNext = (row - 1) * nLen + (col + 2);
    30. if(row > 0 && col + 2 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    31. return true;
    32. // Hướng 4 giờ
    33. iNext = (row + 1) * nLen + (col + 2);
    34. if(row + 1 < nLen && col + 2 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    35. return true;
    36. // Hướng 5 giờ
    37. iNext = (row + 2) * nLen + (col + 1);
    38. if(row + 2 < nLen && col + 1 < nLen && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    39. return true;
    40. // Hướng 7 giờ
    41. iNext = (row + 2) * nLen + (col - 1);
    42. if(row + 2 < nLen && col > 0 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    43. return true;
    44. // Hướng 8 giờ
    45. iNext = (row + 1) * nLen + (col - 2);
    46. if(row + 1 < nLen && col > 1 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    47. return true;
    48. // Hướng 10 giờ
    49. iNext = (row - 1) * nLen + (col - 2);
    50. if(row > 0 && col > 1 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    51. return true;
    52. // Hướng 11 giờ
    53. iNext = (row - 2) * nLen + (col - 1);
    54. if(row >1 && col > 0 && vtBoard[iNext] == -1 && LoopSteps(vtBoard, iNext, nLen, iStep + 1,nDeQui))
    55. return true;
    56.  
    57. vtBoard[iCur] = -1;  // quay lui
    58. return false;
    59. }
    60. void xuatLieu(vector<int>& vtBoard,int iLen,int nDeQui)
    61. {
    62.     cout<<"\n";
    63.     for(int hang=0;hang<iLen;hang++)
    64.     {
    65.         for(int cot=0;cot<iLen;cot++)
    66.         {
    67.             cout.width(3);
    68.             cout<<vtBoard[hang*iLen+cot];
    69.         }
    70.         cout<<"\n";
    71.     }
    72.     cout<<"So lan de qui : "<<nDeQui<<"\n";
    73. }
    74. int main()
    75. {
    76. vector<int> vtBoard;
    77. unsigned long long nDeQui=0;
    78. int iLen;
    79. iLen=8;
    80. vtBoard.resize(iLen*iLen,-1);
    81. // Khởi tạo cho các thành phần cùng với các kiểm tra khác
    82. //........
    83. //........
    84. // Gọi đệ quy có thể như sau
    85. if(LoopSteps(vtBoard, 0, iLen, 0,nDeQui))
    86. {
    87. // xuất liệu
    88.     xuatLieu(vtBoard,iLen,nDeQui);
    89. }
    90. else
    91. {
    92. // không có đường đi
    93.     cout<<"Khong co duong di\n";
    94. }
    95. return 0;
    96. }
    97. /*
    98. n=6
    99.  
    100. 0 27 32 19  2 25
    101.  33 18  1 26  7 12
    102.  28 31 20 11 24  3
    103.  17 34 29  6 13  8
    104.  30 21 10 15  4 23
    105.  35 16  5 22  9 14
    106. So lan de qui : 5422
    107.  
    108. [Program finished]
    109.  
    110. n=7
    111.  
    112. (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)
    113.   0 27 36 23  2 25 16
    114.  35 38  1 26 17 10  3
    115.  28 41 22 37 24 15  8
    116.  39 34 29 18  9  4 11
    117.  42 21 40 31 14  7 46
    118.  33 30 19 44 47 12  5
    119.  20 43 32 13  6 45 48
    120. So lan de qui : 11272348
    121.  
    122. [Program finished]
    123.  
    124. n=8
    125.  
    126. (1)(2)(3)
    127.   0 37 54 33  2 35 18 21
    128.  53 46  1 36 19 22  3 16
    129.  38 55 32 45 34 17 20  9
    130.  47 52 39 56 23 10 15  4
    131.  58 31 44 51 40 25  8 11
    132.  43 48 57 24 61 14  5 26
    133.  30 59 50 41 28  7 12 63
    134.  49 42 29 60 13 62 27  6
    135. So lan de qui : 3242065
    136.  
    137. [Program finished]
    138.  
    139. n=9
    140.  
    141. (1)...(2147)...
    142. chạy trong 4 phútnghĩa là gọi đệ qui đến 2147 triệu lần vẫn chưa ra kết quả
    143. chạy trong 66 phút, đệ qui lượt thứ 30000 triệu, số vẫn in ra đều đều, nhưng vẫn chưa ra kết quả, chạy lâu quá nên mình dừng c trình
    144. Mình dùng TBD miễn phí cxx droid chạy trên android, không biết người ta cho sử dụng free đến bao lâu nữa
    145. */
    Đã được chỉnh sửa lần cuối bởi khoaph : 14-04-2020 lúc 04:01 PM.

  6. #6
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    998

    Mặc định Cải tiến giải thuật bài con mã đi tuần như thế nào?(với bảng 6x6)

    OK bạn, giải thuật này vấp phải sự bùng nổ bước lặp, để nghĩ xem có giải pháp nào tốt hơn không!

  7. #7
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    611

    Mình đã tìm ra lỗi trong code của mình, mừng dễ sợ
    C++ Code:
    1. void gan(int i)
    2. {
    3.     //cout<<i<<",";
    4.     if(i>=n*n-1)//<------------ mới sửa lại ở đây, lúc trước là i>=n*n
    5.     {
    6.         throw "day";
    7.     }
    8.     int j=0;
    9.     int h,c;
    10.     h=co[i]/n;
    11.     c=co[i]%n;
    12.     //cout<<co[i]<<" "<<h<<" "<<c<<endl;
    13.     while(j<8)
    14.     {
    15.         //cout<<" x:"<<h<<","<<c<<":x ";
    16.         h+=dy[j];
    17.         c+=dx[j];
    18.         //cout<<":"<<h<<","<<c<<","<<otrong(h,c)<<":";
    19.         if(otrong(h,c))
    20.         {
    21.             //cout<<j<<"("<<h<<":"<<c<<")";
    22.             oo(h,c)=i+1;
    23.             co[i+1]=h*n+c;
    24.             gan(i+1);
    25.             co[i+1]=-1;
    26.             oo(h,c)=-1;
    27.         }
    28.         h-=dy[j];
    29.         c-=dx[j];
    30.         //cout<<" z:"<<h<<","<<c<<"z ";
    31.         j++;  
    32.     }
    33.     cout<<"\n";
    34. }
    35. /*
    36.   0  9 22 63  6  3 12 17
    37.  23 62  7  2 11 16  5 14
    38.   8  1 10 21  4 13 18 31
    39.  61 24 39 42 19 30 15 50
    40.  38 43 20 57 40 49 32 29
    41.  25 60 41 46 35 28 51 54
    42.  44 37 58 27 56 53 48 33
    43.  59 26 45 36 47 34 55 52
    44.  
    45. [Program finished]*/
    Code của mình đã ra kết quả đúng với n=5,6,7. Với n=8 thì code mình mất tới hơn 3 phút, code của bạn thì cho kết quả ngay lập tức
    Đã được chỉnh sửa lần cuối bởi khoaph : 14-04-2020 lúc 09:24 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