User Tag List

+ Trả lời chủ đề
Hiện kết quả từ 1 tới 3 của 3

Chủ đề: Một bài toán nhờ các anh chị hướng dẫn!

  1. #1
    Crystal_Eyes
    Guest

    Mặc định Một bài toán nhờ các anh chị hướng dẫn!

    Em mới học xong TP, có bài toán Bát Hậu mà em vãn chưa giải được! Mọi người ơi, ai có thuật giải bài này giúp em với!

  2. #2
    HUT's Student Avatar của BlueGene
    Tham gia ngày
    Nov 2003
    Bài gửi
    303

    Mặc định

    Giải thuật bài này có trong cuốn "Cấu trúc DL và giải thuật" của Đỗ Xuân Lôi. Chú mua về đi, có ích lắm

    INPUT:
    - Bàn cờ vua 8x8;
    - Quân hậu là quân có thể ăn bất kỳ quân nào trên cùng 1 hàng, cột, hay đường chéo;
    - Có tất cả 8 con hậu.

    OUTPUT:
    Các bảng vuông đại diện cho bàn cờ, đánh dấu vi trí của 8 con hậu sao cho không có con hậu nào ăn quân hậu khác, nghĩa là: mỗi hàng, mỗi cột, mỗi đường chéo chỉ có một quân hậu.

    Giải thuật:
    Bài này dùng giải thuật ĐỆ QUY QUAY LUI (back tracking) dựa trên phương án thử và sai: Thủ tục chính đặt tên là Try(i);
    Procedure Try(i: integer);
    If i>8 then In KẾT QUẢ
    Else
    for j:= 1 to 8 do
    if (a[j]=0) and b[i+j]=0 and c[i-j]=0 then
    begin
    x[i]:=j;
    a[j]:=1;
    b[i+j]:=1;
    c[i-j]:=1;
    Try(i+1);
    c[i-j]:=0;
    b[i+j]:=0;
    a[j]:=0;
    end;
    end;

    - (i, j) là vị trí của 1 quân hậu; a[i]= 0 nghĩa là không có quân hậu nào chiếm hàng i; b[i+j]=0 nghĩa là không có quân hậu nào chiếm được đường chéo i+j; còn c[i-j]=0 ... đường chéo i-j. Như vậy là dk để lựa chọn i được chấp nhận là (a[j]=0) and b[i+j]=0 and c[i-j]=0); Gán chúng =1 nghĩa là đặt quân hậu.
    Và như vậy các mảng nguyên a, b, c có chỉ số chạy như sau:
    a[1..8], b[2..16], c[-7..7]; (cái này dễ hiểu mà
    - Ban đầu khởi tạo a, b , c là các mảng gồm toàn phần tử 0;
    Có thể dùng Repeat để khử đệ quy
    Sharing Knowledge is Power.

  3. #3
    HUT's Student Avatar của BlueGene
    Tham gia ngày
    Nov 2003
    Bài gửi
    303

    Mặc định

    a`, còn x[1..8] là mảng chứa phương án tìm được, sẽ được đưa ra màn hình trong phần In KẾT QUẢ

+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Từ khóa (Tag) của chủ đề này

Quyền viết bài

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


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube