01/10/2018, 09:45
Backtracking (quay lui) hoạt động như thế nào?
Mình có code liệt kê nhị phân như sau:
#include <iostream>
#include <iomanip>
using namespace std;
int n,a[100];
void result(){
for(int i = 1; i <= n; i++){
cout << setw(5) << a[i];
}
cout << endl;
}
void Try(int i){
for(int j = 0; j <= 1; j++){
a[i] = j;
if(i == n){
result();
} else{
Try(i+1);
}
}
}
int main(){
cin >> n;
Try(1);
return 0;
}
Giả sử với n = 3;
ỏ Try: khi i = 3; j = 1; thì vì sao nó có thể gọi tiếp i = 2 được Try(2)
Bài liên quan
Code này trông hư cấu quá :v ai lại code backtrack như thế này :v
Giả sử ta đang ở
i = 1, j = 1. Ta có thể đi đến trạng tháii = 2, j = 0hoặci = 2, j = 1. Khi ta đã xây dựng xong dãy với trạng thái (gần như ban đầu) lài = 2, j = 0, ta còn trạng tháii = 2, j = 1chưa được thử. Lập tức ta nhảy sang trạng tháii = 2, j = 1.Có 1 ví dụ của thầy Trần Đỗ Hùng rất hay và dễ hiểu, tuy nhiên hơi khó để tìm trên mạng.
Try(3) kết thúc thì nó trở ngược về hàm gọi nó ra là Try(2) thôi. Try(3) với try(2) có j = 0 sẽ khác try(3) nãy.
Mã try(3) với j = 1 thì kết thúc rồi mà.
làm sao nó có thể gọi ra Try(2) vậy chế
làm sao có thể đi với code như vậy
Ý bạn là sao?
Bạn tìm code khác dễ hiểu hơn code này đi.
mình chỉ thắc mắc với i = 3 và j = 1 thì nó thoát khỏi vòng for và đi ra khỏi hàm Try chứ nhỉ?
sao nó có thể đi tiếp với những cấu hình tiếp theo được
Hàm Try chỉ kết thúc khi nó duyệt hết tất cả các cấu hình có thể.
Tìm hiểu kỹ về đệ quy. Thì cái này dễ hiểu mà