Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 2: Kĩ thuật quay lui

XIN CHÀO CÁC EM!

CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

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ới 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.

CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT

BÀI 2.

KĨ THUẬT QUAY LUI

NỘI DUNG BÀI HỌC

1

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

2

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

3

Kĩ thuật quay lui

BÀI TOÁN MUA ĐỒ TỔNG QUÁT

01

Cho n đồ dùng với mức giá tương ứng là P0, P1,…,Pn-1(đồng) và có mức độ yêu thích của Hồng tương ứng là S0, S1,…,Sn-1. Em hãy giúp Hồng chọn mua một số đồ dùng với tổng giá không vượt quá T(đồng) mà tổng mức độ yêu thích là lớn nhất.

BÀI TOÁN

Đọc thông tin và hoàn thành hoạt động sau đây:

Hoạt động 1

Cho 5 đồ dùng vói mức 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 đồ dùng nào để được tổng mức độ yêu thích là lớn nhất?

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

GỢI Ý

• 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.

VÍ DỤ

LIỆT KÊ DÃY BIT ĐỘ DÀI N BẰNG KĨ THUẬT ĐỆ QUY

02

Đọc thông tin và hoàn thành hoạt động sau đây:

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ình 1. Chương trình liệt kê dãy bit bằng kĩ thuật đệ quy và màn hình kết quả chạy chương trình với n = 3

Nếu n=0 thì dãy bit độ dài n là dãy rỗng.

TRẢ LỜI CÂU HỎI

Em hãy tìm hiểu sách chuyên đề và đưa ra cách xây dựng dãy nhị phân theo thuật toán đệ quy.

CÁC BƯỚC THỰC HIỆN

1

2

3

Hình 2. Qúa trình gọi đệ quy xây dựng dãy bit độ dài 3

Dãy trong hình chữ nhật là dãy bit trong quá trình xây dựng, số trong hình ô van là thứ tự gọi đệ quy trong quá trình xây dựng.

KĨ THUẬT QUAY LUI

03

Thảo luận cặp đôi, nghiên cứu cách xây dựng lời giải của bài toán có dạng:

CÁC BƯỚC GIẢI BÀI TOÁN

1

Bắt đầu từ lời giải rỗng [].

2

NẾU

Xây dựng xong lời giải thì lời giải sẽ được kiểm tra đánh giá và chọn nghiệm

><

 Quá trình sẽ dừng lại khi tất cả các khả năng lựa chọn của các thành phần của lời giải đều đã được xét.

• Khi cài đặt kĩ thuật quay lui, người ta sử dụng kĩ thuật để quy để xây dựng tất các các khả năng của lời giải, với mỗi khả năng kiểm tra đánh giá để chọn nghiệm.

Hình 3. Mô hình kĩ thuật quay lui

LUYỆN TẬP

Câu 1: Khi cài đặt kĩ thuật quay lui, người ta thường sử dụng kĩ thuật nào?

A. Kĩ thuật chia để trị.

B. Tìm kiếm nhị phân.

C. Kĩ thuật đệ quy.

D. Thuật toán sắp xếp trộn.

C. Kĩ thuật đệ quy.

Câu 2: Đây là mô tả của kĩ thuật gì?

A. Kĩ thuật quay lui.

B. Kĩ thuật duyệt.

C. Kĩ thuật chia để trị.

D. Tìm kiếm nhị phân.

A. Kĩ thuật quay lui.

Câu 3: Cách tính số lượng dãy bit nhị phân độ dài k, ta tính thế nào?

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