Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 1: Ý tưởng chia để trị

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

NGÀY HÔM NAY!

KHỞI ĐỘNG

Trong sách Tin học 7, em đã được học thuật toán tìm kiếm nhị phân. Thuật toán này là một kĩ thuật thu hẹp phạm vi tìm kiếm trong phương pháp chia để trị. Em hãy quan sát dãy 9 số được sắp xếp tăng dần sau:

4 7 8 20 21 22 36 77 81

Số 21 ở vị trí chính giữa của dãy, các số bên trái của số 21 luôn nhỏ hơn 21 và các số bên phải của số 21 luôn lớn hơn 21. Do đó nếu muốn tìm một số x nhỏ hơn 21 thì chỉ cần thu hẹp phạm vi tìm kiếm vào một nửa của dãy, theo em đó là nửa dãy bên trái hay nửa dãy bên phải của số 21?

CHUYÊN ĐỀ 2: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

BÀI 1.

Ý TƯỞNG VÀ KĨ THUẬT CHIA ĐỂ TRỊ

NỘI DUNG BÀI HỌC

1

Ý tưởng kĩ thuật chia để trị

2

Thuật toán Tìm kiếm nhị phân

PHẦN 1. Ý TƯỞNG KĨ THUẬT CHIA ĐỂ TRỊ

Hoạt động 1

Hai mô tả sau đây chỉ ra phương pháp hiệu quả giải quyết bài toán bổ và đếm số hạt dưa bằng ý tưởng kĩ thuật chia để trị. Em hãy tìm hiểu bài toán sau đây và rút ra ý tưởng chủ đạo của kĩ thuật chia để trị để giải quyết bài toán.

a. Bài toán Bổ dưa và đếm số hạt dưa

Hôm nay là sinh nhật của Thanh An, có tất cả 8 bạn tham dự. Thanh An có một quả dưa hấu muốn chia thành 8 miếng dưa đều nhau và muốn biết tổng số hạt của quả dưa này. Để các miếng dưa có thể đều nhau, Thanh An nghĩ ra cách bổ đôi theo từng lượt (Hình 1).

• Lượt 1: Bổ đôi quả dưa thành hai miếng (A/B).
• Lượt 2: Bổ đôi mỗi miếng (A) và (B) thành hai miếng (A.1/A.2) và (B.1/B.2).
• Lượt 3: Bổ đôi mỗi miếng (A.1), (A.2), (B.1), (B.2) thành hai miếng (A.1.1/A.1.2), (A.2.1/A.2.2), (B.1.1/B.1.2), (B.2.1/B.2.2).

Hình 1. Minh họa quá trình bổ các miếng dưa làm đôi

Cộng dồn số hạt của hai miếng dưa ở mỗi lượt bổ theo thứ tự 3, 2, 1

1

Cộng dồn số hạt của từng cặp miếng dưa (A.1.1) và (A.1.2), (A.2.1) và (A.2.2), (B.1.1) và (B.1.2), (B.2.1) và (B.2.2) để biết số hạt của các miếng (A.1), (A.2), (B.1), (B.2).

2

Cộng dồn số hạt của từng cặp miếng dưa (A.1) và (A.2), (B.1) và (B.2) để biết số hạt của các miếng (A) và (B).

3

Cộng dồn số hạt của hai miếng dưa (A) và (B) để biết tổng số hạt của quả dưa.

Cộng dồn số hạt của các miếng dưa ở lượt sau

Số hạt của mỗi miếng dưa ở lượt trước

Tổng số hạt của quả dưa.

Thanh An bổ đôi từng miếng dưa giúp ước lượng hai nửa đều nhau.

Thanh An cộng dồn số hạt mỗi miếng ngược theo thứ tự bổ giúp giải quyết mục tiêu thứ hai

Thứ ba là kiểm tra xem số hạt từng nửa chia có đều nhau hay không và đếm tổng số hạt trong quả dưa.

Ý TƯỞNG CHIA ĐỂ TRỊ

1. Chia:

• Chia bài toán ban đầu thành hai hoặc nhiều bài toán con.
• Chia mỗi bài toán con thành các bài toán con đơn giản hơn nữa

2. Trị:

• Giải quyết các bài toán con (một cách đệ quy), kết quả là các lời giải của các bài toán con.

3. Kết hợp:

• Kết hợp các lời giải của các bài toán con để có được lời giải của bài toán ban đầu.

Hoạt động 2

Trong các bài toán tìm kiếm trên một không gian xác định, thu hẹp dần phạm vi tìm kiếm là một kĩ thuật của ý tưởng chia để trị. Em hãy tìm hiểu bài toán sau đây và cho biết ý tưởng chia để trị được thể hiện trong kĩ thuật thu hẹp phạm vi tìm kiếm.

b. Bài toán Tìm địa điểm du lịch

Phân tích ví dụ để nhận thấy sau từng bước, không gian địa điểm cần tìm kiếm giảm đi rõ rệt.

Giới hạn dần phạm vi tìm kiếm địa điểm.

Ghép lần lượt từng địa điểm trên cả bản đồ vào các tiêu chí.

Giới hạn phạm vi tìm kiếm tìm ra địa điểm dễ dàng hơn nhiều so với việc ghép lần lượt từng địa điểm trên cả bản đồ vào các tiêu chí đặt ra.

ĐẶC ĐIỂM

1. Thu hẹp không gian tìm kiếm của bài toán để đưa về bài toán nhỏ hơn.

2. Giải quyết bài toán nhỏ bằng cách tiếp tục thu hẹp không gian tìm kiếm bài toán để đưa về bài toán nhỏ hơn cho đến khi đạt được giá trị cần tìm.

Thu hẹp dần phạm vi tìm kiếm là một kĩ thuật của chia để trị. Kĩ thuật này được áp dụng trong các bài toán có thể loại bỏ đi những phần không gian tìm kiếm mà chắc chắn nghiệm của bài toán không nằm trong đó để giảm bớt độ phức tạp tính toán của thuật toán.

KẾT LUẬN

PHẦN 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

• Tìm kiếm nhị phân là một thuật toán cơ bản trong kĩ thuật thu hẹp phạm vi tìm kiếm của phương pháp chia để trị.
• Thuật toán tìm kiếm nhị phân trên dãy số sắp xếp tăng dần.

Thảo luận nhóm đôi

Ý tưởng của thuật toán là gì?

Ý tưởng: tìm kiếm một phần tử bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.

Tìm kiếm nhị phân: là một thuật toán của chia để trị để thu hẹp phạm vi tìm kiếm. Tại mỗi bước lặp, phạm vi tìm kiếm vị giảm một nửa.

Nghiên cứu và trả lời Bài toán 1 và nội dung Thực hành:

Hình 4. Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân trên dãy số tăng dần

Hình 5. Chương trình tìm kiếm nhị phân trên dãy số tăng dần và màn hình kết quả chạy một số bộ dữ liệu thử nghiệm

Nghiên cứu và trả lời Bài toán 2 và nội dung Thực hành:

Hình 6. Chương trình tìm kiếm nhị phân trên dãy số tăng dần cho bài thực hành và màn hình kết quả chạy một số bộ dữ liệu thử nghiệm

LUYỆN TẬP

Câu 1: Giải quyết bài toán bằng ý tưởng chia để trị gồm những bước nào?

A. Chia, Trị, Kết hợp.

B. Chia, Trị.

C. Chia, Trị, Phân tích.

D. Chia, Trị, Thu hẹp phạm vi.

A. Chia, Trị, Kết hợp.

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