[Thuật toán Đệ quy] Bài toán xếp Hậu trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 1,265

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Trong bài này chúng ta cùng đến với 1 bài toán có thể nói là kinh điển cho thuật toán quay lui - đó là bài toán xếp hậu trong C++. Đây được xem là bài toán sử dụng thuật toán đệ quy khó hiểu nhất trong những bài toán sử dụng giải thuật đệ quy.

    [​IMG]

    xep hau trong c++

    Đặt vấn đề: xếp n quân hậu lên 1 bàn cờ kích thước n*n sao cho các quân hậu từng đôi một không ăn được nhau.

    Ý tưởng:
    • Theo hàng ngang, các quân hậu có thể ăn lẫn nhau, ta gọi quân hậu đặt ở hàng 1 là quân hậu 1... quân hậu hàng n là quân hậu n. Vậy sẽ có 1 mảng kiểm tra xem hàng thứ i có quân hậu i nào chưa cho ta tìm ra vị trí cột của những quân hậu.
    • Nếu ta định hướng Phải, Trái, Dưới, Trên theo hình trên 1 bàn cờ vuông thì ta nhận thấy rằng:
      • Một đường chéo theo hướng Phải & Trên - Trái & Dưới bất kỳ sẽ đi qua một số ô, các ô đó có tính chất: Hàng + Cột = C (Const). Với mỗi đường chéo Phải & Trên - Trái & Dưới ta có 1 hằng số C và với một hằng số C: 2 <= C <=2n xác định duy nhất 1 đường chéo Phải & Trên - Trái & Dưới vì vậy ta có thể dùng 1 mảng để kiểm tra đường chéo Phải & Trên - Trái & Dưới xem đã có quân hậu nào đặt chưa.
      • Một đường chéo theo hướng Phải & Dưới - Trái & Trên bất kỳ sẽ đi qua một số ô, các ô đó có tính chất: Hàng - Cột = C (Const). Với mỗi đường chéo Phải & Dưới - Trái & Trên ta có 1 hằng số C và với một hằng số C: 1 - n <= C <= n - 1 xác định duy nhất 1 đường chéo Phải & Dưới - Trái & Trên vì vậy ta có thể dùng 1 mảng để kiểm tra đường chéo Phải & Trên - Trái & Dưới xem đã có quân hậu nào đặt chưa.
    [​IMG]


    http://www.mediafire.com/?nh5g8be463brqnb

    Xây dựng chương trình:
    1. Ta có 3 mảng để đánh dấu:
    • Mảng a[1..n]. a=1 nếu như cột i còn tự do, a =0 nếu như cột i đã bị một quân hậu khống chế.
    • Mảng b[2..2n]. b =1 nếu như đường chéo Phải & Trên - Trái & Dưới thứ i còn tự do, b= 0 nếu như đường chéo đó đã bị một quân hậu khống chế.
    • Mảng c[1 - n..n - 1]. c = 1 nếu như đường chéo Phải & Dưới - Trái & Trên thứ i còn tự do, c = 0 nếu như đường chéo đó đã bị một quân hậu khống chế.
    • Ban đầu cả 3 mảng đánh dấu đều mang giá trị =1. (Các cột và đường chéo đều tự do)
    1. Thuật toán quay lui: Xét tất cả các cột, thử đặt quân hậu 1 vào một cột, với mỗi cách đặt như vậy, xét tất cả các cách đặt quân hậu 2 không bị quân hậu 1 ăn, lại thử 1 cách đặt và xét tiếp các cách đặt quân hậu 3...Mỗi cách đặt được đến quân hậu n cho ta 1 nghiệm
    2. Khi chọn vị trí cột j cho quân hậu thứ i, thì ta phải chọn ô(i, j) không bị các quân hậu đặt trước đó ăn, tức là phải chọn cột j còn tự do, đường chéo Phải & Trên - Trái & Dưới (i+j) còn tự do, đường chéo Phải & Dưới - Trái & Trên (i-j) còn tự do. Điều này có thể kiểm tra (aj = bi+j = ci-j = 1)
    3. Khi thử đặt được quân hậu thứ i vào cột j, nếu đó là quân hậu cuối cùng (i = n) thì ta có một nghiệm. Nếu không:
      1. Trước khi gọi đệ quy tìm cách đặt quân hậu thứ i + 1, ta đánh dấu cột và 2 đường chéo bị quân hậu vừa đặt khống chế (aj = bi+j = ci-j := 1) để các lần gọi đệ quy tiếp sau chọn cách đặt các quân hậu kế tiếp sẽ không chọn vào những ô nằm trên cột j và những đường chéo này nữa.
      2. Sau khi gọi đệ quy tìm cách đặt quân hậu thứ i + 1, có nghĩa là sắp tới ta lại thử một cách đặt khác cho quân hậu thứ i, ta bỏ đánh dấu cột và 2 đường chéo bị quân hậu vừa thử đặt khống chế (aj = bi+j = ci-j := 1) tức là cột và 2 đường chéo đó lại thành tự do, bởi khi đã đặt quân hậu i sang vị trí khác rồi thì cột và 2 đường chéo đó hoàn toàn có thể gán cho một quân hậu khác.
    Chương trình hoàn chỉnh:

    Mã:
    #include<stdio.h>
    int d=0;
    int n;
    int x[100], a[100], b[100], c[100];
    void start(){
        printf("nhap n= "); scanf("%d",&n);
        for (int i = 1; i <= n; i++) a[i] = 1;
        for (int i = 2; i <= 2*n; i++) b[i] = 1;
        for (int i = 1-n; i <= n-1; i++) c[i] = 1;
        }
    void prin(){
        printf("%d: ",d+1);
        for (int i = 1; i <= n; i++)
            printf("(%d, %d); ",i,x[i]);
            printf("n");
        d++;
        }
    void Try(int i){
        int  j;
        for ( j = 1; j <= n; j++){
            if (a[j] == 1 && b[i+j] == 1 && c[i-j] == 1){
                x[i] = j;
                if (i! = n) {
                    a[j] = 0;
                    b[i+j] = 0;
                    c[i-j] = 0;
                    Try(i+1);
                    a[j] = 1;
                    b[i+j] = 1;
                    c[i-j] = 1;
              
                    }
              
                else
                    prin();
            }
        }
        }
    int main(){
        start();
        Try(1);
        }
    
    Chúc mọi người thành công!!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN
    Last edited by a moderator: 18/11/15

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap