01/10/2018, 12:15
Cần giải thích cơ chế hoạt động của lệnh Try(i+1, n) trong code đệ quy quay lui
#include<iostream>
#include<cmath>
// gia su co quan hau dat tai vi tri (x1,y1), ta muon dat them con hau ke tiep
// tai vi tri (x2,y2), lam the nao ?
using namespace std;
int a[8] ; // luu vet chuong trinh
bool OK(int x2, int y2 ){ // k tra vi tri (x2, y2) co dat dc queen ?
for(int i = 1; i< x2; i++ )
//a[i] == y2 => columns are same
//|i - x2| == |a[i] - y2| => in diagonals.
if(a[i] == y2|| abs(i-x2) == abs(a[i] - y2) ) return false;
return true;
}
void xuat(int n ){
for(int i=1; i<= n; i++ )
cout<<" " <<a[i];
cout<< endl;
}
void Try(int i, int n ){
for(int j = 1; j<= n; j++ )
if(OK(i,j)) // queen tai vi tri hang i dat vao cot thu j
{
a[i] = j;
if(i==n)
xuat(n);
Try(i+1,n);
}
}
int main(){
int n = 8;
Try(1,n);
return 0;
}
mn cho mình hỏi sao khi gọi hàm Try(i+1,n) thì nó in được như trong ảnh vậy.mình biết nó là quay lui nhưng vần không hiểu cơ chế của nó lắm.mn giải thích giúp mình được không ạ.
đây là bài 8 con hậu ạ.
thanks
Bài liên quan
Bạn tìm thuật toán 8 hậu trên google, hoặc học lại cơ bản về backtracking.
bạn cài visual studio xong bật debug lên nhé
Nên hiểu là tìm cấu hình đúng với yêu cầu. Lựa chọn ở bước này sẽ phụ thuộc vào những lựa chọn ở bước trước, chứ không đợi đến xong rồi mới thử (một số ít bài với dãy nhị phân có màn này).
Sau khi một hàm (callee) chạy thì nó rút stack và quay về hàm caller.
mình đã đọc backtracking nhưng thật sự là không hiểu nổi nên ms nhờ mọi nhười giải thích hộ ak.ai hiểu rõ giải thích hộ mình với
cho mình hỏi sao m sau khi debug trong hàm try.gọi tới hàm try(i+1,n)thì nó lại in được như trong ảnh vậy.mình thật sự đọc rất nhiều lần r nhưng vần không hiểu được.r sao m mình debug trong hàm try,nó chỉ chạy qua vòng for có đúng 1 lần nhưng nó lại có thể in được vậy.mình muốn hỏi 2 ý như thế thôi
Mình để breakpoint vào dòng 2 của
Try()thì nó vẫn chạy đủ i mà.không lệnh for trong hàm Try() ak #rogp10
Vòng for đó duyệt các ô (i, j) để tìm khả năng đặt con hậu ở hàng i.
Đọc lại về thuật toán N-hậu:
N Queen Problem | Backtracking-3 - GeeksforGeeks
We have discussed Knight’s tour and Rat in a Maze problems in Set 1 and Set 2 respectively. Let us discuss N Queen as another… Read More »