- bạn ơi,khi chúng ta giải bằng đệ quy quay lui thì ý tưởng tui từng nêu đó chính là ứng dụng của việc tạo ra dãy nhị phân có độ dài N.Vậy khi mảng có N số thì nó sẽ tạo ra 2^N dãy nhị phân.Dựa vào dãy nhị phân đó mình làm một hàm tính toán và cập nhật kỉ lục riêng.Khi đã có một dãy tối ưu thì mình dùng thêm một mảng btoiuu để lưu lại cấu hình tối ưu của b.Và tiếp tục duyệt để tìm tiếp.Sau cùng thoát ra mình có dãy nhị phân tối ưu đc lưu trong mảng btoiuu dực vào đó mà printf ra....
Cấu trúc chương trình như sau...
Code:
void back_tracking(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<=1;j++)
{
b[i] = j;
if (i==n)
{
// Ham kiem tra ki luc...
}
else
{
back_tracking(i+1);
}
}
b[i] = 0; //Tra ve cau hinh ban dau cho b[i];
}
}
- Nói chung thì cái này ban đầu thì khó hiểu lắm.Mình đã chia tay với các giải thuật kiểu này lâu rồi nên ko còn "Pro" để hướng dẫn bạn nhiều hơn đc.Sorry nhé!
- Còn về QHD thì bản chất của nó là "Khử đệ quy" thôi...Ví dụ:
+ Bài toán tính dãy FIBONACCI thì có hai cách làm:
*đệ quy:Fibo[n] = Fibo[n-1] + Fibo[n-2];
*Vòng lặp + mảng F: F[i] = F[i-1] + F[i-2] với F[0]=F[1]=1;
- trong đó thì vòng lặp chính là hình thức QHD đó.Nó nhanh hơn đệ quy nhưng hơi khó hiểu về mặt hình thức ( đối với các bài toán lớn hơn)..
- Còn về chi tiết thì xin mời bạn đọc giải thuật của Lê Minh Hoàng nhé !!Nó sẽ chỉ cho bạn...Một ebook hay đó