Bài toán xếp 8 quân hậu

Chia sẻ: Le Bang Ha | Ngày: | Loại File: PPT | Số trang:7

0
619
lượt xem
163
download

Bài toán xếp 8 quân hậu

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giới thiệu bài toán: Quân hậu trên bàn cờ Vua có thể ăn theo hàng, cột, đường chéo chứa nó. Tìm cách đặt 8 quân hậu trên bàn cờ sao cho không quân nào ăn được của quân nào

Chủ đề:
Lưu

Nội dung Text: Bài toán xếp 8 quân hậu

  1. Bài toán xếp 8 quân hậu 1.Giới  thiệu  bài  toán:  Quân  hậu  trên  bàn  cờ  Vua  có  thể  ăn  theo  hàng,  cột,  đường  chéo  chứa nó. Tìm cách đặt 8 quân hậu trên bàn cờ  sao  cho  không  quân  nào  ăn  được  của  quân  nào 2.Ý tưởng thuật toán: Một con hậu xếp ở một vị  trí bất kỳ trên bàn cờ thì để tìm được vị trí của  con hậu tiếp theo ta phải xét theo 3 hướng như  hình sau: 1
  2. Mô hình bài toán Các  con  hậu  tiếp  theo  phải  được  chọn  ở  các  vị  trí  không  nằm  trên  các  đường  dọc,  đường  ngang  và  đường  chéo  của  con  các  con  hậu  trước. 2
  3. Các bước giải quyết bài toán • Ta tìm vị trí để đặt cho con hậu thứ i, với con hậu  thứ  i  thì  ta  phải  xét  xem  trên  các  hướng  của  nó  sau đó tìm tiếp vị trí cho con hậu thứ i + 1. • Nếu  ở  bước  thứ  i  không  tìm  thấy  vị  trí  đặt  của  con hậu thì chúng ta phải quay lại xét đến vị trí  khác của con hậu thứ i – 1. • Trường hợp suy biến của bài toán là khi chúng ta  đã  đặt  cho  con  hậu  thứ  8  có  nghĩa  là  cả  8  con  hậu  đã  được  xếp  trên  bàn  cờ  và  thoả  mãn  điều  kiện là các con hậu không thể ăn được nhau.  3
  4. Bài toán tìm đường đi bằng chu trình  Hamilton Giới thiệu bài toán: Một người khách du lịch muốn  đi  thăm  n  thành  phố  được  đánh  số  từ  1  đến  n.  Mạng  lưới  giao  thông  giữa  n  thành  phố  này  là  2  chiều và được cho bởi ma trận A[i,j] trong đó A[i,j]  = 1 nếu có đường đi giữa thành phố i và thành phố  j,  A[i,j]  =  0  trong  trường  hợp  ngược  lại.  Thiết  lập  đường đi cho người khách thông báo tồn tại đường  đi hoặc không tồn tại đường đi. 4
  5. Mô hình bài toán •Chúng ta có file có n + 1 dòng như sau: – Dòng 1: Ghi số nguyên dương là n thành phố – Dòng i + 1: (1≤i≤n): ghi n số nguyên không âm  A[i,1]  A[i,2]…A[i,n]  cho  biết  có  đường  đi  hay  không giữa hai thành phố i và j (1≤j≤n). •Kết quả tồn tại hay không tồn tại đường đi. 5 Kết quả: 0 0 1 1 1 0 0 1 1 1  Chu trình Hamilton như  sau: 1 1 0 1 1 1 1 1 0 1 1  3  2  4  5  1 1 1 1 1 0 5
  6. Các bước giải quyết bài toán • Tìm hết tất cả mọi khả năng của đường đi  (Sau  khi  đi  qua  đường  đi  nào  thì  xoá  bỏ  đường đi đó) và kiểm tra xem đường đi này  có qua đủ n đỉnh của đồ thị hay không. 6
  7. Thủ tục mô tả thuật toán Procedure Hamilton(k : byte); var i : byte; Begin      if k = n + 1 then         inkq      else          for i := 1 to n do              if (a[c[k­1],i] > 0) and not(b[i]) then                 begin                      a[c[k­1],i] := 0;                      c[k] := i;                      b[i] := true;                      hamilton(k+1);                      a[c[k­1],i] := 1;                      c[k] := 0;                      b[i] := false;                 end; End; 7
Đồng bộ tài khoản