Giải chi tiết chuyên đề Tin học Khoa học máy tính 11 Cánh diều mới bài 2: Kỹ thuật quay lui

Khởi động: Trong bài học trước, các em đã tìm hiểu bài toán Chọn mua đồ dùng học tập với các tình huống mua một đồ dùng hoặc hai đồ dùng. Nếu bài toán không cố định số lượng đồ dùng cần mua mà có thể mua một số đồ dùng với tổng giá không vượt quá T (đồng) và tổng mức độ yêu thích của các đồ dùng đó là lớn nhất, em hãy trình bày ý tưởng giải quyết bài toán.

Hướng dẫn trả lời: 

Đề giải quyết bài toán mua đồ bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bit tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích để chọn phương án tối ưu.

1. Bài toán Mua đồ tổng quát

Hoạt động 1: Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1. Nếu T= 20 (nghìn đồng) thì Hồng cần chọn mua những đồ dùng nào để tổng mức độ yêu thích là lớn nhất?

Bảng 1. Thông tin về các đồ dùng

Hướng dẫn trả lời: 

Lời giải bài toán này có thể biểu diễn bằng 1 dãy bit độ dài n (n là số lượng đồ vật), trong đó bit thứ i (0 ≤ i ≤ n - 1) bằng 1 hoặc 0 tương ứng là vật thứ i được chọn hoặc không chọn

Ví dụ: dãy bit (1, 0, 0, 1, 0) tương ứng với cách chọn đồ dùng số 0 và 3 với tổng giá là 10 +9 = 19 (nghìn đồng) và mức độ yêu thích là 7 + 6 = 13; dãy bit (1, 1, 0, 0, 1) tương ứng với cách chọn đồ dùng số 0, 1 và 4 có tổng giá là 10 + 5 + 5 = 20 (nghìn đồng) và mức độ yêu thích là 7 + 2 + 3 = 12.

Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bit tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích đề chọn phương án tối ưu.

Ở đây, với T = 20, Hồng cần chọn mua đồ dùng số 0 và 3 với tổng giá 10 + 9 = 19 để có mức độ yêu thích lớn nhất là 7 + 6 =13

2. Liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy

Hoạt động 2: Em hãy tìm hiểu chương trình liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy trong Hình 1 và chạy thử nghiệm chương trình. Cho biết số lượng dãy bit nhị phân độ dài 3, 5, 10 tương ứng là bao nhiêu.

Hướng dẫn trả lời: 

Dãy bit độ dài n có dạng X = ($x_{0}, x_{1}...x_{n-1}$), trong đó xi bằng 0 hoặc 1 (0 ≤ i ≤ n-1) có thể mô tả theo cách đệ quy như sau:

- Nếu n > 0 thì phần tử đầu tiên của dãy bằng 0 hoặc 1 và n - 1 phần tử sau là dãy bit độ dài n – 1.

- Ngược lại, nếu n = 0 thì dãy bit độ dài n là dãy rỗng

Việc xây dựng các dãy nhị phân theo thuật toán đệ quy như sau:
1. Bắt đầu từ X rỗng, lệnh x = [] và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu phần tử 0.

2. Thành phần i (0 ≤ i ≤ n-1) sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in range(2): Với mỗi giá trị của v, thành phần i được ghi nhận vào x$_{i}$ của X bằng lệnh x.append(v), lệnh này đẩy v vào cuối X. Sau đó tiếp tục gọi để quy để xây dựng các thành phần còn lại (từ thành phần x$_{i+1}$... đến thành phần x$_{n-1}$).

3. Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ nhị phân thành phần cuối cùng của X bằng lệnh x.pop(). Việc quay lui cũng được diễn ra khi đang xây dựng thành phần x$_{i}$ mà x$_{i}$ đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phân x$_{i}$ sẽ bị loại khỏi X và lùi về để xét khả năng tiếp theo cho thành phần x$_{i-1}$

3. Kĩ thuật quay lui

Luyện tập: Em hãy tìm hiểu, soạn thảo chương trình giải bài toán Mua đồ đồ tổng quát trong Hình 4 bằng kĩ thuật quay lui và chạy thử nghiệm với các bộ dữ liệu trong Bảng 2.

Hướng dẫn trả lời: 

Nhập chương trình sau và đọc kết quả xuất ra màn hình.

Vận dụng: Hồng có n tệp dữ liệu được đánh số từ 0 đến n - 1 và có kích thước tương ứng là $s_{0}, s_{}..... S_{n-1}$ (Mb). Hồng muốn tìm cách lưu trữ được nhiều tệp dữ liệu nhất bằng hai đĩa ô cứng, mỗi ô có dung lượng D(Mb). Em hãy lập trình giúp Hồng giải quyết bài toán trên, chương trình sẽ nhập vào số nguyên 2 và dãy số $S_{0}, S_{1}, ...S_{n-1}$, sau đó đưa ra phương án lưu trữ là một dãy số $X_{0}, X_{1}, ...X_{n-1}$. trong đó X$_{i}$ (0 ≤ i ≤ n-1) nhận một trong ba giá trị 0 (không được lưu trữ). 1 (lưu trên ô cứng thứ nhất) hoặc 2 (lưu trên ô cứng thứ hai). Xem Hình 5 mô tả quá trình xây dựng các dãy X. Chạy thử nghiệm với các bộ dữ liệu trong Bảng 3.

Bảng 3: Một số bộ dữ liệu thử nghiệm cho bài toán Mua đồ tổng quát

Hướng dẫn trả lời: 

n = int(input("Nhap n:"))

if ( n<2 or n % 2 == 0or n % 3 == 0 or n % 5 == 0):

print("không phải số nguyên tố ")

else:print("là số nguyên tố")

Câu hỏi tự kiểm tra: Trong những câu sau đây, câu nào đúng khi nói về kĩ thuật quay lui?

a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.

b) Khi cài đặt kĩ thuật quay lui, bắt buộc phải sử dụng kĩ thuật đệ quy.

c) Kĩ thuật quay lui là một kĩ thuật theo ý tưởng của kĩ thuật duyệt.

Hướng dẫn trả lời: 

Trong những câu sau đây, câu sau đúng khi nói về kĩ thuật quay lui:

a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.