Giáo án tin học 7 kết nối bài 15: Thuật toán tìm kiếm nhị phân (2 tiết)

HOẠT ĐỘNG CỦA GV – HS

DỰ KIẾN SẢN PHẨM

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

Hoạt động 1. Sắp xếp và tìm kiếm

- GV tổ chức HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 1.Thuật toán tìm kiếm nhị phân và thực hiện Hoạt động 1. Sắp xếp và tìm kiếm:

+ Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước lặp để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước lặp thực hiện của thuật toán tìm kiếm tuần tự với số bước lặp thực hiện của thuật toán tìm kiếm nhị phân.

+ Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thỏa mãn điều kiện gì? Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?

* Thuật toán tìm kiếm tuần tự

- GV đặt câu hỏi cho HS: Từ tình huống khởi động, em hãy nêu cách làm của An? Nêu rõ các bước làm.

* Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên

- GV tổ chức cho HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.73 và thực hiện nhiệm vụ: Em hãy trình bày các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên.

- GV chốt kiến thức:

* Câu hỏi/SGK tr.76

- GV tổ chức cho HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.76:

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu mục Thuật toán tìm kiếm nhị phân và thực hiện Hoạt động 1.

- HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.76 và thực hiện nhiệm vụ.

- HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.76.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời câu hỏi và hoàn thành bài tập.

- GV mời đại diện HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV chuyển sang nội dung mới.

1. Thuật toán tìm kiếm tuần tự

* Hoạt động 1. Sắp xếp và tìm kiếm

- Thuật toán tìm kiếm tuần tự phải thực hiện 8 bước để tìm khách hàng tên “Trúc” trong danh sách ở hình 15.1, trong khi thuật toán tìm kiếm nhị phân chỉ thực hiện 4 bước. Như vật thuật toán tìm kiếm nhị phân nhanh hơn.

- Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách tên khách hàng cần được sắp xếp. Nếu không được sắp xếp, thuật toán tìm kiếm nhị phân không thể thu hẹp phạm vi tìm kiếm vì giá trị cần tìm có thể ở vị trí bất kì trong danh sách.

* Thuật toán tìm kiếm tuần tự

- Danh sách khách hàng nhiều → sắp xếp theo thứ tự chữ cái tên khách hàng trên máy tính.

- An so sánh giá trị cần tìm với giá trị ở giữa danh sách

+ Giá trị cần tìm ở giữa danh sách → dừng lại.

+ Lớn (nhỏ) hơn thì tìm ở nửa sau (đầu) của danh sách

- Lặp lại quá trình đến khi tìm thấy hoặc hết danh sách.

à Thuật toán tìm kiếm thu hẹp danh sách tìm kiếm chỉ còn một nửa, gọi là tìm kiếm nhị phân.

- Các bước để An tìm khách hàng tên “Trúc” theo thuật toán tìm kiếm nhị phân:

+ Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5.

+ Bước 2. Xét vị trí ở giữa của nửa sau của đây là vị trí số 7

+ Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó là vị trí số 8.

Vì sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc.

* Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên

- Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.

- Bước 2. Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

- Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa” và kết thúc.

- Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) vùng tìm kiếm mới thu hẹp lại, chỉ còn nửa sau của dãy.

- Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc tìm kiếm không còn phần tử nào (Bước 1).

Lưu ý: “nửa trước” và “nửa sau” không gồm phần tử giữa.

* Câu hỏi/SGK tr.76

- Bước 1. Vị trí giữa vùng tìm kiếm là 5. So sánh “Hòa” và “Mai”. Vì H đừng trước M trong bảng chữ cái nên vùng tìm kiếm là nửa trước của dãy (từ vị trí 1 đến vị trí 4).

- Bước 2. Vị trí giữa vùng tìm kiếm là 2. So sánh “Hòa” và “Bình”. Vì H đứng sau B trong bảng chữ cái nên vùng tìm kiếm là nửa sau của dãy (từ vị trí 3 đến vị trí 4).

- Bước 3. Vị trí giữa của vùng tìm kiếm là 3. So sánh ta thấy giá trị ở vị trí giữa đúng là “Hòa” là giá trị cần tìm. Thuật toán kết thúc.