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

Đề tài: Lỗi chạy mãi không xong trong bài mã đi tuần

  1. #1
    Ngày gia nhập
    11 2008
    Nơi ở
    ĐH Công Nghệ - ĐHQG Hà Nội
    Bài viết
    28

    Mặc định Lỗi chạy mãi không xong trong bài mã đi tuần

    Khi chạy với bàn cờ kích thước cỡ 8*8 hoặc 10*10 thì ra ngay đáp án, tuy nhiên khi nhập hàng cột là 1 1 với bàn cờ 10*10 thì chạy mãi không xong. Hoặc là với bàn cờ 5*5, ô xuất phát là 2 2 thì cũng ko ra đáp án, trong khi với đoạn mã của thầy thì lại ra ngay đáp án. Ko hiểu thuật toán của mình có gì sai nữa. Ai xem giùm đc ko ạ.

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip.h>
    3. using namespace std;
    4.  
    5. /* Knight Tour */
    6. const int maxx=100;
    7.  
    8. int size;
    9. int K[maxx][maxx],access[maxx][maxx];
    10.  
    11.  
    12. int SUB_ROW[8],SUB_COL[8];
    13. int ver[]={+2,-1,-1,-2,-2,+1,+1,+2};
    14. int hor[]={-1,+2,-2,-1,+1,-2,+2,+1};
    15. int row,col,times;
    16.  
    17. bool CHECK(int row,int col)
    18. {
    19.     if(row>size-1||row<0||col>size-1||col<0||K[row][col]!=0)
    20.     return false;
    21.     else
    22.     return true;
    23. }
    24. void PRINT()
    25. {
    26.     cout<<"\nCac nuoc di cua con ma theo thu tu nhu sau tren ban co\n\n";
    27.     for(int i=0;i<size;i++)
    28.     {        
    29.         for(int j=0;j<size;j++) cout<<setw(4)<<K[i][j];
    30.         cout<<endl<<endl;
    31.     }
    32. }  
    33.  
    34. void SWAP(int &a,int &b)
    35. {
    36.     int temp=a;
    37.     a=b;
    38.     b=temp;  
    39. }
    40.  
    41. void HEURISTIC(int row,int col,int &step,int ORDER[8])
    42. {
    43.     int poss_row,poss_col; // GIA SU NHUNG KHA NANG XAY RA CUA ROW VA COL
    44.      
    45.     /* BAT DAU SINH BANG ACCESSIBILITY */
    46.     for(int i=0;i<size;i++)
    47.     {
    48.         for(int j=0;j<size;j++)
    49.         {
    50.             access[i][j]=0;
    51.             for(int k=0;k<size;k++)
    52.             {
    53.                 poss_row=i + ver[k];
    54.                 poss_col=j + hor[k];
    55.                 if(CHECK(poss_row,poss_col))
    56.                     access[i][j]++;
    57.             }  
    58.         }
    59.     }
    60.     /* KET THUC SINH BANG */
    61.        
    62.     int ROW_I,ROW_II;
    63.     int COL_I,COL_II;
    64.        
    65.     /* BAT DAU KHOI TAO GIA TRI CHO SUB_ROW[] va SUB_COL[] */  
    66.     step=0;
    67.     for(int i=0;i<8;i++)
    68.     {
    69.         poss_row=row + ver[i];
    70.         poss_col=col + hor[i];
    71.         if(CHECK(poss_row,poss_col))
    72.         {
    73.             SUB_ROW[step]=poss_row;
    74.             SUB_COL[step]=poss_col;
    75.             ORDER[step]=step; // LUU LAI TRANG THAI CUA ROW VA COL
    76.             step++;
    77.         }
    78.     }
    79.     /* KET THUC */
    80.    
    81.     /* SO SANH CHON RA BUOC NHAY TOI UU NHAT */
    82.     for(int i=0;i<step ;i++)
    83.     {
    84.         for(int j=i + 1;j<step;j++)
    85.         {
    86.             ROW_I=SUB_ROW[ORDER[i]];
    87.             COL_I=SUB_COL[ORDER[i]];
    88.             ROW_II=SUB_ROW[ORDER[j]];
    89.             COL_II=SUB_COL[ORDER[j]];
    90.             if(access[ROW_I][COL_I]>access[ROW_II][COL_II])
    91.                 SWAP(ORDER[i],ORDER[j]);
    92.         }
    93.     }
    94. /*---------------------------------------------------*/
    95. }      
    96. void Knight(int times,int row,int col)
    97. {
    98.     int ORDER[8];
    99.     int moves=0;
    100.     int next_row,next_col;
    101.    
    102.     K[row][col]=times+1;
    103.     while(times!=size*size)
    104.     {
    105.         if(times==size*size-1) break;
    106.         HEURISTIC(row,col,moves,ORDER);
    107.         for(int i=0;i<moves;i++)  
    108.         {
    109.             next_col=SUB_COL[ORDER[i]];
    110.             next_row=SUB_ROW[ORDER[i]];
    111.             if(CHECK(next_row,next_col))
    112.                 Knight(times+1,next_row,next_col);
    113.         }
    114.     }
    115.     PRINT();
    116. }
    117.  
    118. main()
    119. {
    120.     cout<<"Nhap kich thuoc ban co(n*n) n=";cin>>size;
    121.     cout<<"Nhap vi tri xuat phat cua quan ma (Hang Cot): ";
    122.     cin>>row>>col; fflush(stdin);
    123.     Knight(0,row-1,col-1);
    124.     system("pause");
    125. }

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Bạn xem code này thử xem có giúp gì thêm cho b ko ha
    Bài này sử dụng kỹ thuật quay lui kết hợp nhánh cận rất hay.

    Yêu cầu nhập từ file (MA.INP), với dòng đầu tiên là một số cho biết kích thước bàn cờ, dòng thứ hai là hai số tọa độ ban đầu xuất phát của mã
    Ví dụ:
    100
    1 1

    -> bài này chạy với bàn cờ có kích thước 100x100 vẫn ok

    C++ Code:
    1. #include<iostream>
    2. #include<fstream.h>
    3. #include<conio.h>
    4. using namespace std;
    5. int n,x,y,dd[10000][10000],kn[10000][10000],vt[3][10000],di[3][9];
    6. bool ngung=false;
    7. ofstream f1("MA.OUT",ios::out);
    8. int ktkn(int i,int j){
    9.     int dem=0;
    10.     for(int l=1;l<=8;l++)
    11.         if(i+di[1][l]>=1 && i+di[1][l]<=n && j+di[2][l]>=1 && j+di[2][l]<=n) dem++;
    12.     return dem;
    13. }
    14. void doc_file(){
    15.     ifstream f("MA.INP",ios::in);
    16.     f>>n;// Kich thuoc ban co
    17.     f>>x>>y;//Toa do ban dau xuat phat
    18.     f.close();
    19.     //khoi tao
    20.     for(int i=1;i<=n;i++)
    21.         for(int j=1;j<=n;j++) dd[i][j]=0;
    22.     di[1][1]=-1; di[2][1]=-2;
    23.     di[1][2]=1; di[2][2]=-2;
    24.     di[1][3]=-1; di[2][3]=2;
    25.     di[1][4]=1; di[2][4]=2;  
    26.     di[1][5]=-2; di[2][5]=-1;
    27.     di[1][6]=-2; di[2][6]=1;
    28.     di[1][7]=2; di[2][7]=-1;
    29.     di[1][8]=2; di[2][8]=1;
    30.     for(int i=1;i<=n;i++)
    31.         for(int j=1;j<=n;j++) kn[i][j]=ktkn(i,j);
    32. }
    33.  
    34. int kiemtra(){
    35.     for(int i=1;i<=n;i++)
    36.         for(int j=1;j<=n;j++) if(dd[i][j]==0) return 0;
    37.     return 1;
    38. }
    39. void in(){
    40.     cout<<endl;
    41.     for(int i=1;i<=n;i++){
    42.         cout<<endl;
    43.         for(int j=1;j<=n;j++) cout<<kn[i][j]<<" ";
    44.     }
    45.     getch();
    46. }
    47.  
    48. void xuly(int _i,int _x,int _y){    
    49.  
    50. if(_i==n*n&&ngung==false){
    51.     ngung=true;
    52.     if(kiemtra()==1){
    53.         cout<<endl;
    54.         for(int j=1;j<=_i-1;j++){
    55.             cout<<endl<<vt[1][j]<<" "<<vt[2][j];
    56.         }
    57.     }
    58. }
    59. else if(ngung==false){
    60.     int _di[3][9],dem=0,i,j,l;
    61.     //tim cac duong di tiep
    62.     for( l=1;l<=8;l++)
    63.         if(_x+di[1][l]>=1 && _x+di[1][l]<=n && _y+di[2][l]>=1 && _y+di[2][l]<=n &&dd[_x+di[1][l]][_y+di[2][l]]==0){
    64.             dem++;
    65.             _di[0][dem]=kn[_x+di[1][l]][_y+di[2][l]];
    66.             _di[1][dem]=_x+di[1][l];
    67.             _di[2][dem]=_y+di[2][l];
    68.         }
    69.     //sap xep theo kha nang
    70.     int temp[3];
    71.     for( i=2;i<=dem;i++)
    72.         for( j=dem;j>=i;j--)
    73.         if(_di[0][j]<_di[0][j-1]){
    74.                 temp[0]=_di[0][j];temp[1]=_di[1][j];temp[2]=_di[2][j];
    75.                 _di[0][j]=_di[0][j-1];_di[1][j]=_di[1][j-1];_di[2][j]=_di[2][j-1];
    76.                 _di[0][j-1]=temp[0];_di[1][j-1]=temp[1];_di[2][j-1]=temp[2];
    77.         }
    78.     //Giam kha nang
    79.     for(i=1;i<=dem;i++)
    80.         kn[_di[1][i]][_di[2][i]]--;
    81.     kn[_x][_y]--;
    82.     //bat dau duyet
    83.     for(i=1;i<=dem;i++){
    84.         //danh dau
    85.         dd[_di[1][i]][_di[2][i]]=1;
    86.         //vi tri tiep theo
    87.         vt[1][_i]=_di[1][i];
    88.         vt[2][_i]=_di[2][i];
    89.         //goi xu ly cho vi tri tiep theo
    90.         xuly(_i+1,_di[1][i],_di[2][i]);
    91.         //bo danh dau
    92.         dd[_di[1][i]][_di[2][i]]=0;
    93.     }
    94.     //Tang lai kha nang
    95.     for(i=1;i<=dem;i++)
    96.         kn[_di[1][i]][_di[2][i]]++;
    97.     kn[_x][_y]++;
    98. }
    99. }
    100.  
    101. int main(){
    102.     doc_file();
    103.     dd[x][y]=1;
    104.     xuly(1,x,y);
    105.     if(ngung) cout<<"\nKet thuc.";
    106.     else cout<<"\nKhong co duong di";
    107.     getch();
    108.     return 0;
    109. }

    Có gì thắc mắc, tớ sẽ giúp thêm cậu nếu có thể
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 06-12-2008 lúc 11:29 AM.
    Không biết ghi gì luôn ...

  3. #3
    Ngày gia nhập
    11 2008
    Nơi ở
    ĐH Công Nghệ - ĐHQG Hà Nội
    Bài viết
    28

    Cảm ơn bác đã share code, nhưng em kém dịch ngược code ra giải thuật lắm. Em đã làm gần xong bài này rồi, nhưng chưa nghĩ ra phương pháp nào để mà khi quay lui lại bước trước thì có thể bỏ qua cái ô mà đặt quân hậu vào đó thì các ô sau ko đặt được. Em nghĩ cả ngày ko ra. Thứ 2 này phải thi môn Cấu trúc dữ liệu & giải thuật rồi. Hix. Bó tay trường mình, học Điện tử viễn thông mà cũng vẫn phải học cái môn của bên CNTT này.

  4. #4
    Ngày gia nhập
    11 2007
    Bài viết
    32

    sao mình thấy các code cũng giống giống trong sách nhỉ? hỏng có cái ThuatToan nào khác biệt, cải tiến, hay hơn ....
    bài MĐT nào mình cũng thấy cài là quai lui, rồi mảng hằng hay ban đầu sẽ gán a[1]=-1.....a[]=-2....a[]=2......
    hic hic hic hic hic.

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

    Code trên của Kenshin tui viết cách đây 2 năm làm sao cậu có được vậy ? Và hình như tui nhớ tui chưa post code đó lần nào

  6. #6
    Ngày gia nhập
    01 2008
    Bài viết
    148

    Red face Lỗi chạy mãi không xong trong bài mã đi tuần

    bài này nếu cài đặt bằng quay lui kết hợp nhánh cận như Forl_hope nói trên chạy nhanh hơn rất nhiều so với chỉ đơn thuần dùng quay lui.
    Y tưởng như thế này :
    +Quay lui :chúng ta cứ đi đến các ô khác có thể đến được nếu sai thì quay lui
    + Nhánh cận : Chúng ta sẽ đánh gia khả năng tìm bước đi tốt nhất (quay lui ít nhất) đồng nghỉa với việc từ ô đang đứng ta sẽ đi đến được một ô khác mà ô này có thể đi đến các ô khác là ít nhât(tránh quay lui nhiều lần).
    ==>quan trọng và khó là việc thêm nhánh cận :khi ban đầu chạy ta sẽ tạo 1 mảng bàn cờ khoi tạo khả năng di tới các ô khác từ 1 ô bất kỳ : ví dụ bàn cờ 5x5 vị trí ban đầu của quân cờ là (4,4) thì chúng ta sẽ khởi tạo mảng khả năng như sau : mangKhaNang[1][1] =2 , mangKhaNang[1][2]=3,mangKhaNang[1][3]=4,...,mangKhaNang[2][1]=3,.....Như vậy khi quân cờ tìm được ô thích hợp thì nó sẽ nhảy tới đó,nhiệm vụ chúng ta là phãi cập nhập lại mảng khả năng của bàn cờ lại bằng cách xét những ô xung quanh nếu ô nào chua đi và có thể đến ô hiện tại thì ta trừ đi 1
    ****đi được ở đây tức là theo quy luật của con mã(ngựa)

    Chúc bạn thành công

  7. #7
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    Bài Mã đi tuần vốn vô nghiệm khi bàn cờ có kích thước lẻ mà (hình như sách của thầy LMH nói thế đúg hok ta) bạn cứ thử 101x101 xem nó chạy đến tết cũng không ra nghiệm ) tốt nhất nên cài đặt thêm bộ chặn thời gian
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  8. #8
    Ngày gia nhập
    06 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    48

    Trích dẫn Nguyên bản được gửi bởi hungphong10tin Xem bài viết
    Bài Mã đi tuần vốn vô nghiệm khi bàn cờ có kích thước lẻ mà (hình như sách của thầy LMH nói thế đúg hok ta) bạn cứ thử 101x101 xem nó chạy đến tết cũng không ra nghiệm ) tốt nhất nên cài đặt thêm bộ chặn thời gian
    bài "Mã đi tuần" nếu coi nghiệm chỉ là các đường đi khép kín (xuất phát từ đâu về được đúng chỗ đấy) thì đúng là với kích thước bàn cờ lẻ sẽ vô nghiệm (hoặc bàn m x n với m lẻ, n lẻ cũng thế)

    tuy nhiên nó vẫn có thể có nghiệm là đường đi không khép kín (nhưng vẫn đi hết tất cả các ô trên bàn cờ nha)
    Java Code:
    1. System.out.println("We are electric !");

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

  1. Bài tập C Bạn nào xem dùm mềnh với .mình làm xong mà ko chạy đc .hức hức
    Gửi bởi mrkhiet trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 17-07-2012, 11:04 AM
  2. Cách tạo quảng cáo chạy trong khi chờ game load xong!
    Gửi bởi tranphu0ng trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 3
    Bài viết cuối: 30-11-2011, 11:38 PM
  3. Tại sao lập trình xong chạy file .exe ko dc
    Gửi bởi quoctai2009 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 24-06-2011, 02:47 PM
  4. Lập trình C# | Kiểm tra Thread đã chạy xong chưa
    Gửi bởi mouseover trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 12-11-2010, 11:16 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