Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 14: Thực hành kĩ thuật duyệt quay lui

CHÀO MỪNG CÁC EM ĐẾN VỚI

TIẾT HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Theo em kĩ thuật duyệt quay lui thường được áp dụng cho những loại bài toán nào? Em có thể nêu ra một vài ví dụ không?

BÀI 14. 

NHIỆM VỤ 1

Phân tử ADN gồm chuỗi các nucleotit thuộc bốn dạng A, T, G và X. Viết chương trình in ra tất cả các dạng mạch đơn của một đoạn phân tử ADN với chiều dài gồm n các nucleotit, trong đó n được người dùng nhập từ bàn phím. Lưu ý do sự bùng nổ của tổ hợp, chỉ nên kiểm thử chương trình với số n nhỏ hơn 10.

• Bài toán là dạng tổng quát của bài toán sinh các dãy nhị phân mà chúng ta đã biết. Điểm khác biệt là cần sinh tổ hợp của 4 phần tử "A", "T", "G", "X". Chúng ta định nghĩa dictDNA là xâu nhị phân "ATGX" lưu các kí tự từ điển DNA.
• Chúng ta sẽ thiết lập hàm sinh các dãy nucleotit này theo kĩ thuật quay lui, kết quả lưu trong dãy A. Dãy A ban đầu được khởi tạo bao gồm n kí tự rỗng. Hàm sinh dãy nucleotit là genDNASection(A,k) có tính năng sinh các phần tử tại vị trí thứ k.

PHÂN TÍCH

• Tại dòng 13, khởi tạo mảng biểu diễn chuỗi AND gồm n kí tự rỗng, rồi gọi hàm đệ quy ở dòng 14.
• Trong hàm genDNASection, tham số k thể hiện vị trí nucleotit đã được thiết lập.
• Nếu k bằng chiều dài n thì đã hoàn thành 1 nghiệm bài toán (là chuỗi AND gồm n nucleotit) nên chương trình sẽ in ra ở dòng 4.
• Nếu k < n thì lần lượt gán phần tử thứ k cùng A với 4 loại nucleotit (ATGX) và gọi đệ quy hàm genDNASection để sinh phần tử tiếp theo.

NHIỆM VỤ 2

Một câu trong các ngôn ngữ tự nhiên được xây dựng bằng cách sắp xếp các từ vựng lại với nhau. Xét trường hợp đơn giản: cho một tập hợp từ vựng, hãy viết chương trình sinh ra các câu văn gồm tất cả các từ đó, mỗi từ chỉ xuất hiện một lần.

Chúng ta có thể giải quyết bài toán sinh ra các câu văn ở trên bằng cách bắt đầu với một câu gồm tất cả các từ đã cho trong từ điển, sau đó thực hiện duyệt quay lui để hoán vị tất cả các vị trí của các từ.

PHÂN TÍCH

LUYỆN TẬP

Bài 1.

Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi là cần in ra kết quả là các xâu kí tự chỉ bao gồm các kí tự “A”, “T”, “G”, “X”.

Bài 2.

Trong Nhiệm vụ 2, động tác "quay lui" nằm ở đâu? Việc hoán vị được thực hiện như thế nào?

HƯỚNG DẪN THỰC HIỆN

1

Để in ra kết quả chỉ gồm các xâu kí tự “A”, “T”, “G”, “X”, chúng ta cần sửa đoạn in kết quả tại dòng 4 của chương trình 1.

2

Trong Nhiệm vụ 2, động tác quay lui nằm ở dòng 11 vì dòng 11 nhằm khôi phục trạng thái danh sách các từ đã được lựa chọn (biến words) trước khi thực hiện dòng 9, sau đó thử nghiệm bằng việc thêm một từ khác chưa có trong danh sách từ đã lựa chọn.

VẬN DỤNG

--------------- Còn tiếp ---------------