01/10/2018, 17:44

Tại sao gọi BackTracking(i+1) vs BackTracking(++i) lại cho kết quả khác nhau?

Trong thuật toán quay lui BackTracking để liệt kê, ++i và i+1 đều có ý nghĩa quay lui đến phần tử cần cấu hình tiếp theo. Nhưng tại sao kết quả lại khác nhau? Ai đã từng gặp vấn đề này chưa ạ? Mình nghĩ mãi chưa hiểu vì sao

rogp10 viết 20:00 ngày 01/10/2018

Caller thực hiện ở mức i => callee thực hiện mức i+1, vậy ++i là không đúng về mặt khái niệm, và ++ vào thì cũng phải -- thôi.

Tâm Ninja viết 19:56 ngày 01/10/2018

(i + 1) không làm thay đổi giá trị của i. Còn (++i) thì có.

Vấn đề mà bạn gặp phải là hãy đặt một câu hỏi thông minh hơn. Kết quả là gì, khác nhau ra sao, triển khai như thế nào?..

Nguyễn Văn Thịnh viết 19:49 ngày 01/10/2018

(i + 1) không làm thay đổi giá trị của i. Còn (++i) thì có.

Vậy tại sao khi quay lui để liệt kê dãy nhị phân độ dài n phải kiểm tra điều kiện nếu i ==n hay chưa? Tức là giá trị của i đã thay đổi rồi đúng không bạn? Trong trường hợp dưới đây thì liệt kê ra đầy đủ các cấu hình, tuy nhiên thay i+1 bới ++i thì lại thiếu cấu hình,

#include<iostream>
#define MAX 1000000

using namespace std;
int n;
int a[MAX];
void TRY(int i){
for(int j =0 ; j<=1;j++){
	a[i] = j;
	if(i == n){
		for(int v = 1; v <= n ;v++){
			cout<<a[v]<<" ";
		}	
		cout<<endl;
	}else{
		TRY(i+1);
	}
}

}
int main(){
	cin>>n;
	TRY(1);	
	return 0;
}

rogp10 viết 19:53 ngày 01/10/2018

Thay đổi biến chạy của vòng lặp không phải là chuyện đùa, nhất là thay đổi ngay trong thân vòng lặp for.

Trương Tấn Phát viết 19:54 ngày 01/10/2018

Đấy, khác đấy!
Giữa i+1 (i không đổi) và++i (i thay đổi) trong vòng lặp.
Đối với ++i thì lặp lần đầu thì chưa có gì, lặp lần sau thì giá trị i tăng 1 (nếu i != n, else được chạy)