Ở trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu về đệ quy. Ngày hôm nay, chúng ta sẽ tiếp tục đi tìm hiểu về quay lui, một khái niệm gắn liền với đệ quy và được áp dụng rất nhiều trong các bài toán. Hiểu về quay lui sẽ giúp các bạn hiểu rõ logic của hàm đệ quy hơn. Show Nội dungĐể có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
Bài toán đặt raCho bàn cờ vua có kích thước n × n (4 ≤ n ≤ 10), các cột được đánh số từ 1 đến n theo chiều từ trái qua phải, các hàng được đánh số từ 1 đến n theo chiều từ trên xuống dưới. Hãy tìm cách đặt n quân hậu trên bàn cờ sao cho không có 2 quân hậu nào ở cùng một hàng, cột hay đường chéo. Ví dụ: Giải thích ví dụ: Output trong ví dụ trên là vị trí các quân hậu trong bàn cờ thoả mãn yêu cầu. Dưới đây là hình minh hoạ cho vị trí các quân hậu. Ý tưởng chungTrước hết, cần phải nói rằng: Có thể có rất nhiều cách đặt quân hậu trên bàn cờ thoả mãn yêu cầu đề bài. Trên thực tế, với n = 8 thì có 12 cách xếp các quân hậu thoả mãn. Bây giờ thì hãy quay lại với bài toán của chúng ta. Bài toán trên thực chất là một bài toán rất nổi tiếng trong Tin học đã được đặt ra vào những năm 1848. Trong các cách giải được đưa ra, cách phổ biến nhất đó chính là: Thử. Ta sẽ thử đặt 8 quân hậu vào các ô của bàn cờ sau đó kiểm tra xem liệu cách đặt đó có phù hợp hay không. Vậy thì chúng ta nên thử như thế nào đây?
Chi tiết về chuyện thử như thế nào hãy để ở phần sau. Bây giờ hãy xem xét một vấn đề: Chúng ta sẽ kiểm tra điều kiện không cùng cột và đường chéo như thế nào?
Triển khai ý tưởngChúng ta hiện tại sẽ có hai công việc chính:
Với việc kiểm tra tính hợp lệ, chúng ta chỉ cần dùng 3 mảng đánh dấu một chiều với mục tiêu như đã trình bày ở trên. Việc này là không khó khăn. Bây giờ, vấn đề chính sẽ là làm sao để đặt thử các quân hậu. Hãy thử hình dung luồng chạy của chương trình trong ví dụ ban đầu qua đoạn mã giả sau:
Nhìn vào quá trình vừa rồi, các bạn có thấy quen không? Nếu chưa nhận ra được, hãy nhìn vào mô hình bên dưới của lời giải trên. Các bạn đã nhận ra mô hình này là của thứ gì chưa? Đó chính là mô hình của đệ quy mà ở bài trước mà mình đã trình bày. Phương pháp được sử dụng ở đây gọi là quay lui. Thế thì chính xác quay lui là gì? Quay luiKhái niệmQuay lui là một thuật toán được thiết kế dựa trên đệ quy với ý tưởng: Tại mỗi bước, ta sẽ tìm một lời giải hợp lí cho bước đó rồi tiếp tục xét đến bước tiếp theo. Thực chất, trong cuộc sống, có rất nhiều hành động chúng ta đang áp dụng chiến thuật quay lui. Giả sử, chúng ta biết nhà một người bạn chắc chắn nằm ở một trong những ngõ của con đường này nhưng chúng ta không biết chính xác ngõ nào. Có phải khi đó, ta sẽ đi vào từng ngõ. Với ngõ đó, ta sẽ đến từng nhà, hỏi thăm xem liệu đó có phải nhà chúng ta cần tìm không. Nếu đi đến cuối ngõ mà vẫn không tìm thấy, ta sẽ “quay lui” về đường chính để đi tìm ở một ngõ khác. Ý tưởngSử dụng chiến lược quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Mô hình chungGiả thiết cấu hình cần liệt kê có dạng x1, x2, x3,…,xn. Khi đó thuật toán quay lui được thực hiện qua các bước sau:
Giải quyết bài toán ban đầuVậy chính xác, bài toán ban đầu sẽ được code như thế nào với tư tưởng quay lui. ` include<bits/stdc++.h>using namespace std; const int MaxN = 1 + 1e5; int n; bool mark[3][MaxN]; vector<int> res; void Try(int row){ }
int main(){ }
`Vậy thì độ phức tạp của chương trình trên sẽ là bao nhiêu? Ta thấy, bản chất cách làm của ta là đi xét tất cả các trường hợp nên hàm đệ quy ở phía trên sẽ được goi tối đann lần. Do đó, độ phức tạp chương trình làO(nn). Chia sẻ bản thânChắc hẳn sẽ có rất nhiều bạn sau khi học xong hai bài đệ quy và quay lui sẽ cảm thấy khá “lú” và khó hiểu. Việc này là hết sức bình thường. Cơ chế hoạt động của hai thuật toán này đòi hỏi các bạn phải có thời gian gắn bó với lập trình nhất định và có khả năng tư duy trừu tượng khá tốt để có thể hiểu được nó. Lời khuyên cho các bạn ở đây là gì? Hãy viết ra từng bước như những gì mình đã làm ở phần trên. Viết ra như vậy thì các bạn sẽ thấy rõ ràng việc chương trình của chúng ta sẽ chạy như thế nào. Bản thân bài toán mình giải ở trên cũng không phải là một bài toán dễ. Mình đã mất 2 ngày áp dụng phương pháp viết ra từng câu lệnh như mình nêu ở trên để hiểu được bài toán này. Do vậy, nếu các bạn nghe qua 1 lần chưa hiểu, các bạn có thể nghe lại nhiều lần. Sau khi cảm thấy bản thân mình hiểu, hãy thử tự code bằng chính khả năng của mình. Không chỉ với bài học này mà với tất cả các bài học, mình tin khi các bạn có thể tự code được có nghĩa là các bạn thực sự hiểu những gì mình trình bày. Một lưu ý nữa cho các bạn khi sử dụng đệ quy là nên đảm bảo ý tưởng đúng trước khi code do rất khó debug đệ quy với các bài toán phức tạp. Kết luận
Tải xuốngTài liệuNhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Quay lui dưới dạng file PDF trong link bên dưới. Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com Đừng quên like và share để ủng hộ Kteam và tác giả nhé! Thảo luậnNếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng. |