HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Nhiệm vụ 1. Tìm hiểu bài toán Bổ dưa và đếm số hạt dưa

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu sách CĐHT và trả lời câu hỏi Hoạt động 1 trang 24:

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.

- GV hướng dẫn HS phân tích ví dụ để đưa đến kết luận cách giải quyết bài toán thể hiện ý tưởng chia để trị, bao gồm ba bước: Chia, Trị và Kết hợp.

- GV kết luận về cách giải quyết bài toán trên thể hiện ý tưởng chia để trị.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung ý kiến.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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

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

- Việc cộng dồn số hạt của các miếng dưa ở lượt sau giúp Thanh An biết được số hạt của mỗi miếng dưa ở lượt trước và tổng số hạt của quả dưa. Ở đây, Thanh An bổ đôi từng miếng dưa giúp giải quyết mục tiêu thứ nhất là ước lượng hai nửa đều nhau. Tiếp theo, 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 và 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.

*Kết luận

- Cách giải quyết bài toán trên thể hiện ý tưởng chia để trị, bao gồm 3 bước:

1. Chia: Chia bài toán ban đầu (phức tạp) thành hai hoặc nhiều bài toán con. Tiếp tục chia mỗi bài toán con thành các bài toán con đơn giản hơn nữa và cứ như thế cho đến khi đạt được các bài toán con dù đơn giản mà chúng được giải quyết một cách dễ dàng.

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.

Nhiệm vụ 2. Tìm hiểu bài toán Tìm địa điểm du lịch

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu sách CĐHT và trả lời câu hỏi Hoạt động 2 trang 26:

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.

- GV hướng dẫn HS 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.

- Sau khi HS trả lời, GV kết luận về kĩ thuật thu hẹp dần phạm vi tìm kiếm.

- GV yêu cầu HS làm việc cá nhân và trả lời câu hỏi Thực hành (SCĐ – tr27)

Với bài toán tìm địa điểm du lịch, em hãy đảo thứ tự các tiêu chí, thay đổi một số tiêu chí tìm địa điểm du lịch và quan sát các kết quả trong gian để thu được kết quả cuối cùng.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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

- Việc giới hạn dần phạm vi tìm kiếm địa điểm như vậy giúp Thanh An 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í của mình đặt ra. Cách làm này thể hiện hai đặ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.

*Kết luận

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

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận theo cặp đôi và đặt vấ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ị.

- GV đặt câu hỏi: Ý tưởng của thuật toán là gì?

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu và trả lời Bài toán 1 và nội dung Thực hành.

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu và trả lời Bài toán 2 và nội dung Thực hành.

- GV cho HS thực hành trên máy và kiểm thử với các bộ dữ liệu mẫu và bộ dữ liệu tự tạo thêm.

- GV kết luận về thuật toán Tìm kiếm nhị phân.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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.

- Ý tưởng của thuật toán là 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.