Bài 13: Kĩ thuật duyệt quay lui - Chuyên đề Tin học 11 Kết nối tri thức

Câu 1

Trả lời câu hỏi khởi động trang 56 Chuyên đề Tin học 11 Kết nối tri thức

Chúng ta đã biết từ bài học trước, thiết lập các thuật toán duyệt sẽ phụ thuộc hoàn toàn vào mô hình và cấu trúc của miền dữ liệu cần tìm kiếm. Từ lâu các nhà khoa học đã nhìn thấy rất nhiều bài toán khó không tìm được cách duyệt hữu hiệu, điển hình nhất là bài toán tìm đường đi trong mê cung.

Hình 13.1. Mê cung

Trong trò chơi mê cung (xem hình) em cần tìm một đường đi xuất phát từ lối vào và ra khỏi mê cung tại lối ra. Em có đề xuất gì để giải bài toán này.

Lời giải chi tiết:

Đề xuất: Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Cứ như vậy cho đến khi ra được khỏi mê cung

Câu 2

Trả lời câu hỏi hoạt động 1 trang 57 Chuyên đề Tin học 11 Kết nối tri thức

Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.

Lời giải chi tiết:

Ý tưởng của thuật toán duyệt quay lui là luôn tìm cách đi tiếp theo. Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Thuật toán sẽ sử dụng kĩ thuật đệ quy khi gọi hàm cho bước đi tiếp theo.

Câu 3

Trả lời câu hỏi 1 trang 57 Chuyên đề Tin học 11 Kết nối tri thức

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không?

Lời giải chi tiết:

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm không dừng. Nếu đã đến đích thì thông báo tìm thấy thấy nghiệm tại dòng thứ 7, nếu chưa tìm thấy thì gọi đệ quy lại hàm gốc để đi tiếp tại dòng 10. Nếu không thể đi tiếp thì quay lui tại dòng 11, xóa dấu vết và quay lại vòng lặp 2.

Câu 4

Trả lời câu hỏi 2 trang 57 Chuyên đề Tin học 11 Kết nối tri thức

Lệnh gọi hàm chính của chương trình trên là gì?

Lời giải chi tiết:

Lệnh gọi hàm chính của chương trình trên là dòng số 2, lặp trên tập hợp các khả năng có thể đi tiếp

Câu 5

Trả lời câu hỏi 3 trang 57 Chuyên đề Tin học 11 Kết nối tri thức

Nếu yêu cầu bổ sung thêm 1 lệnh “Nếu thấy thì thông báo và dừng chương trình” thì lệnh này sẽ đặt ở đâu trong chương trình trên?

Lời giải chi tiết:

Lệnh “Nếu thấy thì thông báo và dừng chương trình” đặt ở trước dòng lệnh số 9.

Câu 6

Trả lời câu hỏi hoạt động 2 trang 57 Chuyên đề Tin học 11 Kết nối tri thức

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui

Lời giải chi tiết:

Mô hình thuật toán quay lui tổng quát quy định việc tìm trên các dãy số nguyên x₁, x₂,...x_k sử dụng lệnh gọi đệ quy để mô tả bước đi tiếp theo với k + 1, nếu không tìm được bước đi tiếp theo thì quay lui để tìm hướng đi khác.

Mô hình tổng quát duyệt quay lui sử dụng đệ quy như sau:

Câu 7

Trả lời câu hỏi 1 trang 59 Chuyên đề Tin học 11 Kết nối tri thức

Trạng thái "quay lui" của thuật toán trên nằm ở đâu?

Lời giải chi tiết:

Trong quá trình thực hiện thuật toán, khi tìm được một giải pháp không hợp lệ hoặc không có giải pháp, chương trình sẽ quay lui ngược trở về trạng thái trước đó và tiếp tục thử các giá trị khác cho các biến trạng thái. Khi quay lui, chương trình sẽ trả lại các giá trị đã được duyệt trước đó và trở về trạng thái trước đó để thử các giá trị khác. Quá trình quay lui này sẽ tiếp tục cho đến khi tìm được giải pháp hoặc đã thử tất cả các giá trị khả dĩ cho các biến trạng thái.

Câu 8

Trả lời câu hỏi 2 trang 59 Chuyên đề Tin học 11 Kết nối tri thức

Có cách nào đếm được tất cả các nghiệm từ thuật toán trên được không? Nếu có thì làm cách nào?

Lời giải chi tiết:

Có thể đếm tất cả các nghiệm từ thuật toán duyệt quay lui dùng đệ quy bằng cách sử dụng biến đếm và tăng giá trị của biến này mỗi khi tìm được một nghiệm hợp lệ. Khi kết thúc thuật toán, giá trị của biến đếm sẽ là số lượng nghiệm tìm được.

Câu 9

Trả lời câu hỏi hoạt động 3 trang 59 Chuyên đề Tin học 11 Kết nối tri thức

Cùng thực hiện, trao đổi, thảo luận thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui.

Lời giải chi tiết:

Để thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui, ta có thể sử dụng đệ quy để thêm lần lượt các số 0 và 1 vào dãy nhị phân.

Bước 1: Viết hàm để sinh dãy nhị phân độ dài n:

Bước 2: Gọi hàm generate_binary_sequence với độ dài của dãy nhị phân cần sinh:

Thu được kết quả:

Câu 10

Trả lời câu hỏi 1 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Trong chương trình 1, động tác “quay lui” nằm ở đâu?

Lời giải chi tiết:

Trong chương trình 1, động tác “quay lui” nằm ở dòng 7: genBinary (A, k+1)

Câu 11

Trả lời câu hỏi 2 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Giải thích ý nghĩa của lệnh A.pop() tại dòng 8 của chương trình 2. Vì sao lệnh này không có trong chương trình 1?

Lời giải chi tiết:

- Lệnh A.pop() tại dòng 8 của chương trình 2 nhằm xóa phần tử đã nhập từ bước trước khi quay lui

- Vì ở chương trình 1, dãy A được thiết lập từ trước có đủ n phần tử nên tại bước này chỉ là lệnh gán giá trị và không cần dùng lệnh pop()

- Ở Chương trình 2, dãy A ban đầu là dãy rộng, do đó A được bổ sung dần. Sau khi kết thúc lệnh gọi đệ quy ở dòng 7 cần gọi lệnh pop() ở dòng 8.

Luyện tập Câu 1

Trả lời câu hỏi Luyện tập 1 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Sửa các chương trình trên bổ sung thêm chức năng: sau khi in ra tất cả các xâu nhị phân thi thông báo tổng số nghiệm

Lời giải chi tiết:

Biến count được sử dụng để đếm số lượng xâu nhị phân được sinh ra, và được khởi tạo là 0. Khi một xâu nhị phân được in ra, giá trị của count sẽ được tăng lên 1. Cuối cùng, in ra giá trị của biến count để hiển thị tổng số nghiệm.

Ví dụ n= 3:

Luyện tập Câu 2

Trả lời câu hỏi Luyện tập 2 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Viết chương trình sinh tất cả các xâu (hoặc dãy) bao gồm n kí tự dạng “R”, “G” và "B"

Lời giải chi tiết:

Có thể sử dụng thuật toán quay lui như sau:

Ví dụ, nếu ta chạy đoạn code sau:

Kết quả sẽ là tất cả các xâu bao gồm 3 kí tự "R", "G" và "B":

Vận dụng Câu 1

Trả lời câu hỏi Vận dụng 1 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Viết chương trình sinh tất cả các số hex (hệ đếm 16) có 3 chỉ số

Lời giải chi tiết:

- Có thể sử dụng một hàm đệ quy, trong đó mỗi lần đệ quy, ta thêm một ký tự hex vào chuỗi kết quả và gọi đệ quy tiếp tục với số chỉ số còn lại.

Dưới đây là một ví dụ về cách thực hiện điều này bằng Python:

Ví dụ:

Kết quả:

Vận dụng Câu 2

Trả lời câu hỏi Vận dụng 2 trang 60 Chuyên đề Tin học 11 Kết nối tri thức

Viết chương trình sinh xâu nhị phân thực sự có độ dài n, tức là kết quả in ra phải là các xâu kí tự chứ không phải là danh sách (list) như trong các chương trình trên

Lời giải chi tiết:

Sử dụng phép cộng chuỗi để có kết quả là chuỗi xâu nhị phân cần tìm