Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Bài toán xếp 8 quân hậu trong lập trình C

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Talking Bài toán xếp 8 quân hậu trong lập trình C

    Đây là bài toán hay: cho bàn cờ 8*8 với 8 quân hậu, hãy xếp các quân hậu lên bàn cờ sao cho chúng không ăn được lẫn nhau.
    Bài này có mấy thuật toán sau có thể làm:
    1.Duyệt đệ quy
    2.Duyệt theo thuật toán quay lui.
    3.Duyệt theo thuật toán nhánh cận
    ...
    Sau đây là code theo thuật toán quay lui:
    C Code:
    1. //#include <stdio.h>
    2. #include <stdlib.h>
    3. //#include <conio.h>
    4.  
    5. #define KICHTHUOC 8                    // Kich thuoc cua ban co
    6. #define SODUONGCHEO (2*KICHTHUOC-1)    // So duong cheo cua ban co
    7. #define SOGIA (KICHTHUOC-1)            // so gia
    8. #define TRUE 1
    9. #define FALSE 0
    10.  
    11. // prototypes
    12. void hoanghau(int);
    13. void inloigiai(int loigiai[]);
    14.  
    15. int cottrong[KICHTHUOC];          // mang cac cot co the dat hoang hau
    16. int cheoxuoitrong[SODUONGCHEO];   // mang cac duong cheo xuoi co the dat hhau
    17. int cheonguoctrong[SODUONGCHEO];  // mang cac duong cheo nguoc co the dat hhau
    18.  
    19. int loigiai[KICHTHUOC];        /* mang loigiai cho biet cot dat cac hoang
    20.                                              hau tren ban co. Vi du cac phan tu cua mang
    21.                                              la: 7   3   0   2   5   1   6   4
    22.                                              cho biet hoanghau0 dat o cot 7, hoanghau1
    23.                                              dat o cot 3, ..., hoanghau7 o cot 4      */
    24.  
    25. int SoLoiGiai = 0;
    26.  
    27. void T_HAU(void)
    28. {
    29.    int i;
    30.  
    31.    /* Khoi dong tat ca cac cot duong cheo xuoi, duong cheo nguoc deu co the
    32.       dat hoang hau */
    33.    for(i = 0; i < KICHTHUOC; i++)
    34.       cottrong[i] = TRUE;
    35.    for(i = 0; i < SODUONGCHEO; i++)
    36.    {
    37.       cheoxuoitrong[i] = TRUE;
    38.       cheonguoctrong[i] = TRUE;
    39.    }
    40.  
    41.    // Goi ham de qui de bat dau dat HoangHau0 (hoang hau o hang 0)
    42.    hoanghau(0);
    43. }
    44.  
    45. // Ham hoanghau giup dat hoang hau i (i tu 0 den KICHTHUOC-1) tren hang i
    46. void hoanghau(int i)
    47. {
    48.    int j;
    49.    for(j = 0; j < KICHTHUOC; j++)
    50.       if(cottrong[j] && cheoxuoitrong[i-j+SOGIA] && cheonguoctrong[i+j])
    51.       {
    52.           // Dat hoang hau vao o (i, j) tren ban co
    53.           loigiai[i] = j;
    54.           cottrong[j] = FALSE;
    55.           cheoxuoitrong[i-j+SOGIA] = FALSE;
    56.           cheonguoctrong[i+j] = FALSE;
    57.  
    58.           if(i == KICHTHUOC-1)   // Dkien dung, dat duoc con hoang hau cuoi
    59.              inloigiai(loigiai);
    60.           else                   // Buoc de qui, goi dat hoang hau i+1
    61.              hoanghau(i + 1);
    62.  
    63.           // lan nguoc
    64.           cottrong[j] = TRUE;
    65.           cheoxuoitrong[i-j+SOGIA] = TRUE;
    66.           cheonguoctrong[i+j] = TRUE;
    67.       }
    68. }
    69.  
    70. void inloigiai(int *loigiai)
    71. {
    72.    int i, j;
    73.    char c;
    74.    randomize();
    75.    textmode(C80);
    76.    textbackground(BLACK);
    77.    clrscr();
    78.    textcolor(1 + random(15));
    79.    cprintf("\n                           CHUONG TRINH 8 HOANG HAU\n   ");
    80.    cprintf("\n Loi giai %d", ++SoLoiGiai);
    81.    printf("\n\n                      0     1    2    3    4    5    6    7");
    82.    printf("\n                    ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿");
    83.    printf("\n                   0³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    84.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    85.    printf("\n                   1³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    86.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    87.    printf("\n                   2³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    88.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    89.    printf("\n                   3³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    90.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    91.    printf("\n                   4³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    92.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    93.    printf("\n                   5³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    94.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    95.    printf("\n                   6³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    96.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    97.    printf("\n                   7³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    98.    printf("\n                    ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
    99.    for(i = 0; i < KICHTHUOC; i++)
    100.    {
    101.       gotoxy(24+5*loigiai[i], 8+2*i);
    102.       textcolor(1 + random(15));
    103.       cprintf("Q");
    104.    }
    105.    gotoxy(13, 25);
    106.    printf("Nhan phim <ESC> de thoat, nhan phim bat ky de tiep tuc ...");
    107.    c = getche();
    108.    if(c == 27)
    109.       //return;
    110.       exit(1);
    111. }

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Tổng quát ta có thể giải cho bài toán n quân hậu.

  3. #3
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Mặc định Mã nguồn tám quân hậu trong lập trình C

    Ngoài bài toán 8 hậu, mình còn có mã nguồn của bài toán mã đi tuần, mình post code lên cho mọi người tham khảo nhé, bài này cũng áp dụng backtracking đó:
    C Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <conio.h>
    4.  
    5. #define KICHTHUOC 5 // Kich thuoc cua ban co
    6. void nuocdi(int, int, int);
    7. void innuocdi(int BanCo[][KICHTHUOC]);
    8. void vebanco(void);
    9.  
    10. // To chuc ban co la mang hai chieu
    11.  
    12. int BanCo[KICHTHUOC][KICHTHUOC];
    13.  
    14. // 8 cach di cua con ma
    15. int a[8] = {2, 2, 1, -1, -2, -2, -1, 1};
    16. int b[8] = {1, -1, -2, -2, -1, 1, 2, 2};
    17.  
    18. int SoLoiGiai = 0;
    19.  
    20. int main(void)
    21. {
    22.     int i, j, m, n;
    23.  
    24.     clrscr();
    25.     vebanco();
    26.  
    27.     for(i = 0; i < KICHTHUOC; i++)
    28.     for(j = 0; j < KICHTHUOC; j++)
    29.     {
    30.         // Khoi dong tat ca cac o tren ban co deu chua di
    31.         for(m = 0; m < KICHTHUOC; m++)
    32.         for(n = 0; n < KICHTHUOC; n++)
    33.         BanCo[m][n] = 0;
    34.  
    35.         // Chon nuoc di dau tien va goi ham de qui de di nuoc thu hai
    36.         BanCo[i][j] = 1;
    37.         nuocdi(2, i, j);
    38.     }
    39.     return 0;
    40. }
    41.  
    42. // Ham NuocDi giup di nuoc thu n xuat phat tu o(x, y)
    43. void nuocdi(int n, int x, int y)
    44. {
    45.     int i;
    46.     char c;
    47.     for(i = 0; i < 8; i++)
    48.     {
    49.         if(BanCo[x+a[i]][y+b[i]] == 0 && x+a[i] >= 0 && x+a[i] < KICHTHUOC
    50.         && y+b[i] >= 0 && y+b[i] < KICHTHUOC)
    51.         {
    52.             // Di nuoc thu n
    53.             BanCo[x+a[i]][y+b[i]] = n;
    54.  
    55.             if(n == KICHTHUOC*KICHTHUOC) // Dkien dung, di duoc nuoc cuoi
    56.             {
    57.                 innuocdi(BanCo);
    58.                 gotoxy(43, 4);
    59.                 printf(" Loi giai thu %d", ++SoLoiGiai);
    60.                 gotoxy(13, 25);
    61.                 printf("Nhan <ENTER> de tiep tuc tim loi giai ke. Nhan <ESC> de thoat");
    62.                 if(c = getch() == 27)
    63.                 exit(1);
    64.             }
    65.             else // Buoc de qui, goi di nuoc n+1
    66.             nuocdi(n+1, x+a[i], y+b[i]);
    67.  
    68.             // lan nguoc
    69.             BanCo[x+a[i]][y+b[i]] = 0;
    70.             innuocdi(BanCo);
    71.             gotoxy(43, 4);
    72.             printf("Dang tim loi giai thu %d", SoLoiGiai+1);
    73.             gotoxy(13, 25);
    74.             printf(" Xin vui long cho doi, nhan phim <Ctrl-Break> de thoat... ");
    75.         }
    76.     }
    77. }
    78.  
    79. void innuocdi(int BanCo[][KICHTHUOC])
    80. {
    81.     int i, j;
    82.     char c;
    83.     randomize();
    84.     textmode(C80);
    85.     textbackground(BLACK);
    86.     textcolor(1);
    87.     for(i = 0; i < KICHTHUOC; i++)
    88.     for(j = 0; j < KICHTHUOC; j++)
    89.     {
    90.         gotoxy(23+5*j, 8+2*i);
    91.         textcolor(1 + random(15));
    92.         if(BanCo[i][j] == 0 ? printf(" ") : cprintf("%2d", BanCo[i][j]));
    93.     }
    94. }
    95.  
    96. void vebanco()
    97. {
    98.     printf("\n\t\t\t CHUONG TRINH MA DI TUAN\n");
    99.     printf("\n\t\tKich thuoc ban co %dx%d", KICHTHUOC, KICHTHUOC);
    100.     printf("\n\n\t\t 1 2 3 4 5 6 7 8");
    101.     printf("\n\t\t ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿");
    102.     printf("\n\t\t 1 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    103.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    104.     printf("\n\t\t 2 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    105.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    106.     printf("\n\t\t 3 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    107.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    108.     printf("\n\t\t 4 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    109.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    110.     printf("\n\t\t 5 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    111.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    112.     printf("\n\t\t 6 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    113.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    114.     printf("\n\t\t 7 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    115.     printf("\n\t\t ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    116.     printf("\n\t\t 8 ³ ³ ³ ³ ³ ³ ³ ³ ³");
    117.     printf("\n\t\t ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
    118. }

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

    mình mới học về baktracking có ...3 hôm , chưa hiểu nhiều , thầy mình bảo rằng là nếu mới học nên học về bài quân xe ,về cơ bản cũng giống bài tám quân hậu tuy nhiên không phải xét đường chéo thành ra đọc dễ hiểu hơn , và dễ tiếp thu hơn , bạn nào chưa bao giờ học về backtracking mà mới tiếp cận có lẽ nên đọc bài này thì hay hơn là ,...tụng bài tám quân hậu , đó là ý kiến của mình thôi còn không biết các bạn thì nhue thế nào ? ??
    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...

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

    Tôi không hiểu tại sao khi dạy về kỹ thuật đệ quy, các giáo viên vn lại hay yêu cầu các bài toán "cao siêu" như vậy, khi làm được các bài toán này, hay cho dù là một sv trình bày hướng giải bài toán đó trước lớp, thì liệu rồi sau đó sv sẽ học được cái gì, 6 tháng sau các sv đó còn có thể nhớ được gì về nó. Khi tôi học về giải thuật đệ quy, thật may mắn khi tất cả ví dụ mà giảo viên của tôi đưa ra chỉ là bài toán n!, tuy nhiên thầy đã dạy tôi rất nhiều về giải thuật đó, thầy đã dạy tôi cách "suy nghĩ đệ quy", chứ không chỉ là tìm tòi cách giải cho một bài toán cụ thể. Điều quan trọng nhất trong giải thuật đệ quy là gì? Đó là bạn phải đưa ra được một định nghĩa đệ quy của bài toán, chứ không phải là bạn đưa ra được cài đặt của bài toán đó.

    Back tracking (tên thuật toán được dịch trong AI là suy diễn lùi) là một giải thuật đệ quy, nếu bạn học trong ngành công nghệ thông tin thì có 2 môn học sẽ đề cập đến nó là AI và Prolog. AI thông thường là một môn học bắt buộc cho ngành công nghệ thông tin trong các trường đại học, tuy tôi chỉ thực sự hiểu về nó khi học môn học prolog. Back tracking là thế nào, và khi nào thì bài toán của bạn bắt đầu thực hiện "back tracking", nếu bạn muốn thực sự hiểu về nó, có lẽ cũng như tôi, bạn hãy thử tìm hiểu ngôn ngữ prolog, một ngôn ngữ mà cơ chế hoạt gần như cốt lõi của nó chính là back tracking. Tìm hiểu prolog để hiểu được back tracking không phải là một điều khó. Bạn có thể tìm trên mạng về cuốn sách "Learn Prolog Now", trên mạng có phần tóm lược (free) của cuốn sách đó, và có lẽ từng đó cũng là quá đủ (tôi cũng chỉ được đọc bản tóm lược), tôi nhớ không lầm thì để hiểu được back tracking bạn chỉ cần học thật chậm, thật hiểu hết chương 2 (khoảng tầm 30 trang tiếng anh thì phải) là bạn có thể hiểu được cơ chế hoạt động của ngôn ngữ prolog là thế nào, cũng đồng nghĩa với bạn hiểu được backtracking. Các chương về sau của cuốn sách đó chủ yếu nói về các cách biểu diễn dữ liệu khác của prolog, và một số hướng suy nghĩ cho một số lớp bài toán cụ thể có khả năng biểu diễn dữ liệu dưới các dạng đó.

    Nếu bạn bước chân vào tìm hiểu ngôn ngữ prolog, thì hãy luôn nhớ một điều trong lúc học đó là hãy luôn suy nghĩ, suy nghĩ và suy nghĩ. Cái gì là chung nhất cho bài toán này, bài toán này có thể đại diện cho lớp bài toán nào. Chứ đừng chỉ học cách giải bài toán này trong prolog thế nào (dù làm được điều này nó cũng giúp bạn rất nhiều trong suy nghĩ rồi, vì lời giải prolog chủ yếu dựa vào hướng suy nghĩ hơn là cài đặt).

    Lời kết: dù gì đi nữa (học prolog hay không) để làm được một bài toán đệ quy, cuối cùng bạn vẫn phải đưa ra được định nghĩa đệ quy của bài toán đó. Học prolog chỉ là giúp bạn dễ dàng đưa ra các định nghĩa này hơn (vì bạn đã được tập đưa ra các định nghĩ đệ quy để giải quyết các vấn đề thế nào).

    Một ví dụ về bài toán tìm tất cả các hoán vị của n phần tử. Khi bạn học prolog nó sẽ được suy nghĩ thế nào? Quả thực bình thường để đưa ra một lời giải cho bài toán này không phải dễ, tuy nhiên khi học prolog bạn sẽ tập được một suy nghĩ hơi khác thường một chút. Đó là một hoán vị của n phần tử khi xóa đi một phần tử thì sẽ là một hoán vị của n - 1 phần tử (là tập thu được khi bạn xóa phần tử đó trong tập n phần tử ban đầu). Và chính suy nghĩ đó sẽ đưa ra được lời giải đệ quy cho bài toán hoán vị.

    Tôi đã từng implement một back tracking đơn giản (C#), thực tế đó là project AI của tôi, project đó tôi giáo viên của tôi yêu cầu về implement một ngôn ngữ tương tự như prolog, và tôi đã implement cả 2, prolog (đơn giản) và ngôn ngữ của thầy (do cả 2 chạy cùng một engine, tôi chỉ cần làm thêm phần dịch từ text sang object để engine hiểu - phần này tôi sử dụng một parser free trên mạng - GOLD Parser), trong bài đó back tracking là phần tôi implement cuối cùng nên viết không được tốt lắm (deadline), đêm nay tôi không ở nhà nên không up source code lên được, nếu anh em cần thì tôi sẽ up lên sau
    Đã được chỉnh sửa lần cuối bởi zxc : 04-08-2008 lúc 02:14 AM.

  6. #6
    Ngày gia nhập
    05 2010
    Bài viết
    1

    Mặc định Bài toán xếp 8 quân hậu trong lập trình C

    Mình có bài tám hậu và n hậu nhưng cần anh em giúp
    http://www.mediafire.com/?pmk71u1kb82436b
    Mình dùng đệ quy quay lui nhưng bài tập lớn không không có tìm kiếm đệ quy quay lui, ko biết có thể gọi thuật toán này là tìm kiến nhánh cận ko nhỉ? mong sự góp ý

  7. #7
    Ngày gia nhập
    02 2011
    Bài viết
    2

    Mặc định Đây là bài khử đệ quy 8 hậu, a e xem và cho ý kiến

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. int Test_Col[100],Test_Up[500],Test_Down[500], S[100],Hau[100];
    4. int count=0,n;
    5. /*ham kiem tra o hang r, cot c co chap nhan hay khong*/
    6. /* ham tra ve 0 neu chap nhan va tra ve 1 neu nguoc lai*/
    7. int Test(int r,int c)
    8.     {
    9.              int ok;
    10.             if(Test_Col[c]==0&&Test_Up[c+r]==0&&Test_Down[r-c+n]==0)
    11.              return ok=0;
    12.              else return ok=1;
    13.     }
    14. //Chen 1 con hau vao hang r, cot c
    15. void Insert(int r, int c)
    16.     {
    17.                  
    18.             Hau[r]=c;                                                                              
    19.             Test_Col[c]=1;
    20.             Test_Up[c+r]=1;
    21.             Test_Down[r-c+n]=1;
    22.      }
    23. //Lay lai 1 con hau o hang r, cot c
    24. void Remote(int r, int c)
    25.      {
    26.             Test_Col[c]=0;
    27.             Test_Up[c+r]=0;
    28.             Test_Down[r-c+n]=0;
    29.       }
    30. main()
    31.     {       printf("\n so luong quan hau");
    32.             scanf("%d",&n);
    33.             printf("====Tat ca cac cach xep\nMoi hang la mot cach====");
    34.             int col,row,i,j,k;
    35.             for( i=1;i<=n;i++)
    36.             Test_Col[i]=0; //khoi tao cho cot i con trong
    37.  
    38.             for(j=2;j<=2*n;j++)
    39.             Test_Up[j]=0; //khoi tao cho duong cheo tren con trong
    40.             for (k=1;k<=2*n-1;k++)
    41.             Test_Down[k]=0; //khoi tao cho duong cheo duoi con trong
    42.  
    43.             for (i=1;i<=n;i++)
    44.             Hau[i]=0;
    45.             for (i=0;i<n;i++)
    46.             S[i]=0; // trang thai cho ban co, neu S[i]=0 thi tu hang i->tro ve truoc ban co chua thay doi
    47.             row=1;
    48.       while(row>0)
    49.       {
    50. // Neu S[row-1]=0, Vi tri cua quan co cua hang row-1 chua thay doi
    51.  
    52.                   if(S[row-1]==0)                  
    53.                    {
    54.                         for(col=Hau[row]+1;col<=n;col++)
    55.                            {
    56.                                if(int ok=Test(row,col)==0)
    57.                                   {
    58.                                      Insert(row,col);
    59.                                      S[row]=1;
    60.                                      break;
    61.                                    }
    62.                            }
    63.                     }
    64.                   else
    65.                     {
    66.                        for(col=1;col<=n;col++)
    67.                            {
    68.                               if(int ok=Test(row,col)==0)
    69.                                  {
    70.                                     Insert(row,col);
    71.                                     S[row]=1;
    72.                                     S[row-1]=0;
    73.                                     break;
    74.                                  }
    75.                             }
    76.                        }
    77.                   if(row!=n&&col<=n) row++;
    78.                   else {
    79.                        if(row==n&&col<=n)
    80.                          {
    81.                            count++;
    82.                            printf("\n%3d.",count);
    83.                            for (i=1;i<=n;i++)
    84.                            printf("%3d",Hau[i]);
    85.                            Remote(row,Hau[row]);//lay lai o cua quan hau hang cuoi cung
    86.                           }
    87.                        row--;
    88.                   Remote(row,Hau[row]);
    89.                        }
    90.       }
    91.       printf("\nSo cach xep la %d",count);
    92.       printf("\nNhan phim bat ky de ket thuc!");
    93.       getch();
    94.   }

  8. #8
    Ngày gia nhập
    02 2012
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi zxc Xem bài viết
    Tôi không hiểu tại sao khi dạy về kỹ thuật đệ quy, các giáo viên vn lại hay yêu cầu các bài toán "cao siêu" như vậy, khi làm được các bài toán này, hay cho dù là một sv trình bày hướng giải bài toán đó trước lớp, thì liệu rồi sau đó sv sẽ học được cái gì, 6 tháng sau các sv đó còn có thể nhớ được gì về nó. Khi tôi học về giải thuật đệ quy, thật may mắn khi tất cả ví dụ mà giảo viên của tôi đưa ra chỉ là bài toán n!, tuy nhiên thầy đã dạy tôi rất nhiều về giải thuật đó, thầy đã dạy tôi cách "suy nghĩ đệ quy", chứ không chỉ là tìm tòi cách giải cho một bài toán cụ thể. Điều quan trọng nhất trong giải thuật đệ quy là gì? Đó là bạn phải đưa ra được một định nghĩa đệ quy của bài toán, chứ không phải là bạn đưa ra được cài đặt của bài toán đó.

    Back tracking (tên thuật toán được dịch trong AI là suy diễn lùi) là một giải thuật đệ quy, nếu bạn học trong ngành công nghệ thông tin thì có 2 môn học sẽ đề cập đến nó là AI và Prolog. AI thông thường là một môn học bắt buộc cho ngành công nghệ thông tin trong các trường đại học, tuy tôi chỉ thực sự hiểu về nó khi học môn học prolog. Back tracking là thế nào, và khi nào thì bài toán của bạn bắt đầu thực hiện "back tracking", nếu bạn muốn thực sự hiểu về nó, có lẽ cũng như tôi, bạn hãy thử tìm hiểu ngôn ngữ prolog, một ngôn ngữ mà cơ chế hoạt gần như cốt lõi của nó chính là back tracking. Tìm hiểu prolog để hiểu được back tracking không phải là một điều khó. Bạn có thể tìm trên mạng về cuốn sách "Learn Prolog Now", trên mạng có phần tóm lược (free) của cuốn sách đó, và có lẽ từng đó cũng là quá đủ (tôi cũng chỉ được đọc bản tóm lược), tôi nhớ không lầm thì để hiểu được back tracking bạn chỉ cần học thật chậm, thật hiểu hết chương 2 (khoảng tầm 30 trang tiếng anh thì phải) là bạn có thể hiểu được cơ chế hoạt động của ngôn ngữ prolog là thế nào, cũng đồng nghĩa với bạn hiểu được backtracking. Các chương về sau của cuốn sách đó chủ yếu nói về các cách biểu diễn dữ liệu khác của prolog, và một số hướng suy nghĩ cho một số lớp bài toán cụ thể có khả năng biểu diễn dữ liệu dưới các dạng đó.

    Nếu bạn bước chân vào tìm hiểu ngôn ngữ prolog, thì hãy luôn nhớ một điều trong lúc học đó là hãy luôn suy nghĩ, suy nghĩ và suy nghĩ. Cái gì là chung nhất cho bài toán này, bài toán này có thể đại diện cho lớp bài toán nào. Chứ đừng chỉ học cách giải bài toán này trong prolog thế nào (dù làm được điều này nó cũng giúp bạn rất nhiều trong suy nghĩ rồi, vì lời giải prolog chủ yếu dựa vào hướng suy nghĩ hơn là cài đặt).

    Lời kết: dù gì đi nữa (học prolog hay không) để làm được một bài toán đệ quy, cuối cùng bạn vẫn phải đưa ra được định nghĩa đệ quy của bài toán đó. Học prolog chỉ là giúp bạn dễ dàng đưa ra các định nghĩa này hơn (vì bạn đã được tập đưa ra các định nghĩ đệ quy để giải quyết các vấn đề thế nào).

    Một ví dụ về bài toán tìm tất cả các hoán vị của n phần tử. Khi bạn học prolog nó sẽ được suy nghĩ thế nào? Quả thực bình thường để đưa ra một lời giải cho bài toán này không phải dễ, tuy nhiên khi học prolog bạn sẽ tập được một suy nghĩ hơi khác thường một chút. Đó là một hoán vị của n phần tử khi xóa đi một phần tử thì sẽ là một hoán vị của n - 1 phần tử (là tập thu được khi bạn xóa phần tử đó trong tập n phần tử ban đầu). Và chính suy nghĩ đó sẽ đưa ra được lời giải đệ quy cho bài toán hoán vị.

    Tôi đã từng implement một back tracking đơn giản (C#), thực tế đó là project AI của tôi, project đó tôi giáo viên của tôi yêu cầu về implement một ngôn ngữ tương tự như prolog, và tôi đã implement cả 2, prolog (đơn giản) và ngôn ngữ của thầy (do cả 2 chạy cùng một engine, tôi chỉ cần làm thêm phần dịch từ text sang object để engine hiểu - phần này tôi sử dụng một parser free trên mạng - GOLD Parser), trong bài đó back tracking là phần tôi implement cuối cùng nên viết không được tốt lắm (deadline), đêm nay tôi không ở nhà nên không up source code lên được, nếu anh em cần thì tôi sẽ up lên sau
    thanks bạn mình cũng mới học chưa tìm ra được hướng đi cụ thể

  9. #9
    Ngày gia nhập
    05 2010
    Nơi ở
    Trên núi
    Bài viết
    24

    Trích dẫn Nguyên bản được gửi bởi PoPoPoPo Xem bài viết
    Đây là bài toán hay: cho bàn cờ 8*8 với 8 quân hậu, hãy xếp các quân hậu lên bàn cờ sao cho chúng không ăn được lẫn nhau.
    Bài này có mấy thuật toán sau có thể làm:
    1.Duyệt đệ quy
    2.Duyệt theo thuật toán quay lui.
    3.Duyệt theo thuật toán nhánh cận
    ...
    Sau đây là code theo thuật toán quay lui:
    C Code:
    1. //#include <stdio.h>
    2. #include <stdlib.h>
    3. //#include <conio.h>
    4.  
    5. #define KICHTHUOC 8                    // Kich thuoc cua ban co
    6. #define SODUONGCHEO (2*KICHTHUOC-1)    // So duong cheo cua ban co
    7. #define SOGIA (KICHTHUOC-1)            // so gia
    8. #define TRUE 1
    9. #define FALSE 0
    10.  
    11. // prototypes
    12. void hoanghau(int);
    13. void inloigiai(int loigiai[]);
    14.  
    15. int cottrong[KICHTHUOC];          // mang cac cot co the dat hoang hau
    16. int cheoxuoitrong[SODUONGCHEO];   // mang cac duong cheo xuoi co the dat hhau
    17. int cheonguoctrong[SODUONGCHEO];  // mang cac duong cheo nguoc co the dat hhau
    18.  
    19. int loigiai[KICHTHUOC];        /* mang loigiai cho biet cot dat cac hoang
    20.                                              hau tren ban co. Vi du cac phan tu cua mang
    21.                                              la: 7   3   0   2   5   1   6   4
    22.                                              cho biet hoanghau0 dat o cot 7, hoanghau1
    23.                                              dat o cot 3, ..., hoanghau7 o cot 4      */
    24.  
    25. int SoLoiGiai = 0;
    26.  
    27. void T_HAU(void)
    28. {
    29.    int i;
    30.  
    31.    /* Khoi dong tat ca cac cot duong cheo xuoi, duong cheo nguoc deu co the
    32.       dat hoang hau */
    33.    for(i = 0; i < KICHTHUOC; i++)
    34.       cottrong[i] = TRUE;
    35.    for(i = 0; i < SODUONGCHEO; i++)
    36.    {
    37.       cheoxuoitrong[i] = TRUE;
    38.       cheonguoctrong[i] = TRUE;
    39.    }
    40.  
    41.    // Goi ham de qui de bat dau dat HoangHau0 (hoang hau o hang 0)
    42.    hoanghau(0);
    43. }
    44.  
    45. // Ham hoanghau giup dat hoang hau i (i tu 0 den KICHTHUOC-1) tren hang i
    46. void hoanghau(int i)
    47. {
    48.    int j;
    49.    for(j = 0; j < KICHTHUOC; j++)
    50.       if(cottrong[j] && cheoxuoitrong[i-j+SOGIA] && cheonguoctrong[i+j])
    51.       {
    52.           // Dat hoang hau vao o (i, j) tren ban co
    53.           loigiai[i] = j;
    54.           cottrong[j] = FALSE;
    55.           cheoxuoitrong[i-j+SOGIA] = FALSE;
    56.           cheonguoctrong[i+j] = FALSE;
    57.  
    58.           if(i == KICHTHUOC-1)   // Dkien dung, dat duoc con hoang hau cuoi
    59.              inloigiai(loigiai);
    60.           else                   // Buoc de qui, goi dat hoang hau i+1
    61.              hoanghau(i + 1);
    62.  
    63.           // lan nguoc
    64.           cottrong[j] = TRUE;
    65.           cheoxuoitrong[i-j+SOGIA] = TRUE;
    66.           cheonguoctrong[i+j] = TRUE;
    67.       }
    68. }
    69.  
    70. void inloigiai(int *loigiai)
    71. {
    72.    int i, j;
    73.    char c;
    74.    randomize();
    75.    textmode(C80);
    76.    textbackground(BLACK);
    77.    clrscr();
    78.    textcolor(1 + random(15));
    79.    cprintf("\n                           CHUONG TRINH 8 HOANG HAU\n   ");
    80.    cprintf("\n Loi giai %d", ++SoLoiGiai);
    81.    printf("\n\n                      0     1    2    3    4    5    6    7");
    82.    printf("\n                    ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿");
    83.    printf("\n                   0³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    84.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    85.    printf("\n                   1³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    86.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    87.    printf("\n                   2³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    88.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    89.    printf("\n                   3³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    90.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    91.    printf("\n                   4³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    92.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    93.    printf("\n                   5³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    94.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    95.    printf("\n                   6³    ³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³");
    96.    printf("\n                    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
    97.    printf("\n                   7³²²²²³    ³²²²²³    ³²²²²³    ³²²²²³    ³");
    98.    printf("\n                    ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
    99.    for(i = 0; i < KICHTHUOC; i++)
    100.    {
    101.       gotoxy(24+5*loigiai[i], 8+2*i);
    102.       textcolor(1 + random(15));
    103.       cprintf("Q");
    104.    }
    105.    gotoxy(13, 25);
    106.    printf("Nhan phim <ESC> de thoat, nhan phim bat ky de tiep tuc ...");
    107.    c = getche();
    108.    if(c == 27)
    109.       //return;
    110.       exit(1);
    111. }
    Anh ơi cái phần làm bàn cờ có mấy ký tự đặc biệt làm sao mình biết ký tự nào ra hình nào vậy a, a có thể cho e biết thêm về các ký tự này và các ký tự đặc biệt khác không

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

    tuyet. rat hay ban a

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