Giáo án chuyên đề Khoa học máy tính 11 cánh diều CĐ 2 Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy

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

- Bài toán: Sau giờ chào cờ, trường của Thanh An tổ chức hoạt động kết nối ở sân trường. Lớp của Thanh An được xếp thành một hàng theo chiều cao tăng dần. Lớp của Hải Bình được xếp thành một hàng theo chiều cao giảm dần. Sau đó, nhập hai lớp này thành một hàng bằng cách bạn đầu tiên của lớp Hải Bình đứng vào sau bạn cuối cùng của lớp Thanh An và tạo thành một hàng như Hình 1. Thầy giáo phụ trách yêu cầu đưa ra được cách tìm bạn có chiều cao lớn nhất trong hàng mà sử dụng ít phép so sánh nhất.

- GV tổ chức hoạt động giúp HS hiểu được thuật toán tìm kiếm nhị phân để giải bài toán này.

- GV gọi lên bảng 10 HS, trong đó 4 HS đầu xếp thành hàng theo chiều cao tăng dần và 6 HS còn lại xếp thành hàng nối tiếp 4 HS đầu nhưng theo chiều cao giảm dần. Gọi chiều cao 10 bạn là A₀, A₁,…,A₉.

GV thực hiện từng bước thuật toán tìm kiếm nhị phân trên dãy 10 bạn này để tìm ra bạn có nhiều cao lớn nhất giả sử như sau:

Bước 1: Lấy bạn ở giữa dãy có chiều cao A₄, so sánh chiều cao A₄ > A₅, do đó bạn cao nhất sẽ nằm bên trái bạn thứ 5.

Bước 2: Lấy bạn ở giữa dãy hiện tại có chiều cao A₂, so sánh chiều cao A₂ < A₃, do đó bạn cao nhất sẽ nằm bên phải bạn thứ 2.

Bước 3: So sánh chiều cao hai bạn còn lại A₃ và A₄, bạn nào có chiều cao lớn hơn thì bạn đó là bạn có chiều cao lớn nhất trong dãy cần tìm.

- Sau khi tìm hiểu về Bài toán Tìm phần tử lớn nhất trong mảng có phần đầu sắp xếp tăng dần và phần sau sắp xếp giảm dần¸GV yêu cầu HS thảo luận theo cặp đôi và thực hiện các nhiệm vụ sau:

Yêu cầu: Cho dãy A gồm n phần tử có giá trị đôi một khác nhau A₀, A₁,…,A_n-1 sao cho tồn tại k(0 < k < n – 1) để A₀ < A₁ < … < A_k và A_k > A_k+1 >…> A_n-1. Em hãy viết chương trình tìm phần tử số k sao cho lần so sánh là ít nhất.

Thực hành 1: Mô tả chi tiết cách giải bài toán trên dùng phương pháp tìm kiếm nhị phân.

Thực hành 2: Viết chương trình dùng đệ quy: Nhập vào giá trị n và n giá trị A₀, A₁,…,A_n-1 có dạng phần đầu giá trị tăng dần và phần sau giá trị giảm dần, hãy hiển thị phần tử có giá trị lớn nhất của dãy A.

Thực hành 3: Viết chương trình tìm kiếm tuần tự cho bài toán trên. Với mỗi bộ dữ liệu thử nghiệm, em hãy so sánh số lần lặp của chương trình tìm kiếm tuần tự (dùng vòng lặp) với số lần gọi đệ quy của chương trình ở phần Thực hành 2 (dùng đệ quy). Từ đó, với nhiều bộ dữ liệu thử nghiệm, em sẽ nhận thấy phương pháp tìm kiếm nhị phân có số lần lặp ít hơn nhiều so với phương pháp tìm kiếm tuần tự.

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

- Ở các nhiệm vụ, HS đọc sách CĐHT, chạy chương trình và trả lời câu hỏi.

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

- HS báo cáo kết quả chạy chương trình và trả lời câu hỏi nhiệm vụ.

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

- GV nhận xét kết quả chạy chương trình và trả lời câu hỏi của HS.

- GV tổng quát lại kiến thức trọng tâm và lưu ý HS những lỗi sai.

Bài toán Tìm phần tử lớn nhất trong mảng có phần đầu sắp xếp tăng dần và phần sau sắp xếp giảm dần

Thực hành 1

Phần tử lớn nhất là phần tử tại vị trí j thỏa mãn một trong ba điều kiện sau:

j = 0 và A[0] > A[i]

j = n – 1 và A[n – 2] < A[n – 1]

j > 1 và A[j – 1] < A[j] < A[j + 1]

Hướng dẫn: Đưa việc xét điều kiện 1 và 2 ở trên vào đầu chương trình. Nếu 2 điều kiện đầu không xảy ra, áp dụng chia để trị để xác định điều kiện 3 theo các bước sau:

Bước 1 (Chia): Xác định vị trí k ở giữa.

Bước 2 (Trị): Xác định dãy bên trái hay bên phải của A_k chứa phần tử có giá trị lớn nhất trong dãy, quay trở lại Bước 1 tiếp tục tìm trên dãy mới đó. Quá trình kết thúc khi xác định được phần tử có giá trị lớn nhất.

Thực hành 2:

HS tự lập trình giải bài toán dựa vào chương trình tìm kiếm nhị phân bằng đệ quy, thay đổi các điều kiện so sánh cho phù hợp với bài toán này.

Thực hành 3:

- Chương trình tìm kiếm tuần tự: Sử dụng vòng lặp tuần tự duyệt qua các phần tử của mảng A để tìm ra phần tử có giá trị lớn nhất. Dùng một biến đếm đặt trong vòng lặp để đếm số lần lặp.

- Chương trình tìm kiếm nhị phân bằng đệ quy: Sử dụng một biến đếm đặt đầu hàm đệ quy để đếm số lần gọi hàm này.

- So sánh kết quả của hai biến đếm sau khi thực hiện hai chương trình trên nhiều bộ dữ liệu khác nhau với vị trí của phần tử có giá trị lớn nhất thay đổi và đưa ra nhận xét vị trí của phần tử lớn nhất có tác động thế nào đến giá trị hai biến đếm tính được.