Giáo án Tin học Lớp 7 - Cánh diều - Chủ đề F - Bài 2: Tìm kiếm nhị phân - Trường THCS Bình Lục

CHỦ ĐỀ F: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH
MỘT SỐ THUẬT TOÁN SẮP XẾP VÀ TÌM KIẾM CƠ BẢN
BÀI 2. TÌM KIẾM NHỊ PHÂN
Tin học Lớp 7
Thời gian thực hiện: 1 tiết
I. Mục tiêu
1. Về kiến thức: 
- Mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu đầu vào có kích thước nhỏ.
- Biết được khi dãy có thứ tự thì phải tìm kiếm nhị phân.
- Biết được ý nghĩa của việc chia bài toán thành các bài toán nhỏ hơn.
2. Về năng lực:
2.1. Năng lực chung
- Năng lực tự chủ và tự học: HS có khả năng tự đọc SGK, kết hợp với gợi ý và dẫn dắt của GV để trả lời các câu hỏi.
- Năng lực giải quyết vấn đề và sáng tạo: HS đưa ra thêm một số ví dụ về các tìm kiếm nhị phân 
- Năng lực giao tiếp và hợp tác: HS có khả năng hoạt động nhóm để hoàn thành các nhiệm vụ học tập. 
2.2. Năng lực Tin học
- Sử dụng và quản lí các phương tiện công nghệ thông tin và truyền thông; Giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông; Hợp tác trong môi trường số.
3. Về phẩm chất: 
- Chăm chỉ: miệt mài, chú ý lắng nghe, đọc, làm bài tập, vận dụng kiến thức vào thực tiễn.
-Trung thực: Sẵn sàng chia sẻ sản phẩm của mình cho các bạn góp ý, đánh giá. 
-Trách nhiệm: Trách nhiệm của học sinh khi thực hiện hoạt động nhóm, báo cáo kết quả hoạt động.
II. Thiết bị dạy học và học liệu
- GV: SGK, kế hoạch DH. 
- HS: Sách giáo khoa, bảng nhóm, tìm hiểu nội dung bài mới, học bài cũ.
III. Tiến trình dạy học
1. Hoạt động 1: Khởi động (5’)
a) Mục tiêu: HS nêu được bài toán tìm kiếm trong thực tiễn và nhu cầu tìm hiểu thuật toán tìm kiếm. Tạo tâm thế hứng thú cho học sinh và từng bước làm quen bài học.
b) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ: Gv cho dãy gồm 8 thẻ số như VD sgk, yêu cầu hs tìm ra số 44 trong dãy số đó.Cho HS lên bảng lật tìm thẻ có chứa số 44
- Thực hiện nhiệm vụ: HS thực hiện theo yêu cầu bằng cách đã học tìm kiếm tuần tự hoặc ngẫu nhiên.
- Báo cáo, thảo luận: GV gọi HS trong nhóm trả lời, HS nhóm khác nhận xét, bổ sung.
- Kết luận, nhận định: GV đánh giá kết quả của HS, trên cơ sở đó dẫn dắt HS vào bài học mới.
 + GV chiếu tình huống SGK và yêu cầu một HS đọc.
+ GV yêu cầu HS thảo luận theo cặp đôi và trả lời câu hỏi: "Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào nhanh hơn tìm kiếm tuần tự không? ". 
 GV dẫn dắt vào bài: Em sẽ phải tìm lần lượt từ các số trong dãy, hoặc lật ngẫu nhiên để tìm ra số cần tìm. Ngoài các cách tìm trên còn một cách khác tìm ra một số trong dãy đó là thuật toán tìm kiếm nhị phân.
Để mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu vào có kích thước nhỏ, chúng ta cùng tìm hiểu trong bài học ngày hôm nay 
– Bài 2: Tìm kiếm nhị phân.
2. Hoạt động 2: Hình thành kiến thức (20’)
Hoạt động 2.1: Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự
a) Mục tiêu: 
- Giải thích được thuật toán tìm kiếm nhị phân.
b) Nội dung: GV giới thiệu ý tưởng xây dựng thuật toán tìm kiếm nhị phân như SGK. Yêu cầu học sinh thực hiện phần câu hỏi trong SGK theo nhóm
GV yêu cầu HS đọc nội dung Ví dụ trong phần 1 trong SGK. Trả lời câu hỏi : Em hãy nêu các bước thực hiện thuật toán tìm hiếm nhị phân trong ví dụ .
c) Sản phẩm: Kết quả trả lời của học sinh
d) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ : : GV yêu cầu HS đọc nội dung ý tưởng xây dựng thuật toán tìm kiếm nhị phân trong SGK rồi trả lời câu hỏi: Em có đồng ý với ý kiến của bạn Thanh An không? Vì sao?
 GV yêu cầu HS đọc nội dung Ví dụ trong phần 1 trong SGK theo nhóm bàn và trả lời: Nêu ý tưởng các bước thực hiện để tìm ra số cần tìm?.
- Thực hiện nhiệm vụ: Các nhóm thực hiện.
- Báo cáo, thảo luận: GV gọi HS trong nhóm trả lời, HS nhóm khác nhận xét, bổ sung.
- Kết luận, nhận định: GV đánh giá kết quả của HS, chốt lại kiến thức
Ghi nhớ: Thuật toán tìm kiếm nhị phân là thực hiện chia đôi hiều lần dãy số để tìm kiếm chừng nào tìm thấy thì kết thúc thuật toán, chừng nào chưa tìm thấy thì tiếp tục chia đôi để tìm đến khi phạm vi tìm kiếm chỉ còn một số thì kết thúc thuật toán với kết quả.
Hoạt động 2.2: Thuật toán tìm kiếm nhị phân.
a) Mục tiêu: 
Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu vào có kích thước nhỏ. 
b) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ: 
+ GV nêu ý tưởng thuật toán tìm kiếm nhị phân: là thuật toán tìm kiếm x trong dãy đã sắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm, nếu số ở giữa dãy không phải số cần tìm thì chuyển sang nửa đầu của dãy hoặc nửa sau của dãy số. Cứ thế cho đến khi tìm thấy hoặc đã xét hết dãy.
+ GV yêu cầu HS thảo luận nhóm với câu hỏi sau.
Câu hỏi. Với dãy số đã cho ở ví dụ trên trong mục 1, em hãy thực hiện thuật toán được mô tả ở hình bên.
- Thực hiện nhiệm vụ:
Dựa vào thuật toán được mô tả như hình trên hãy mô tả thuật toán tìm kiếm nhị phân áp dụng vào ví dụ ở mục 1. 
Bước1: Phạm vi tìm kiếm là dãy số: 6;12;18;42;44; 55; 67; 94
Bước 2: Lặp khi vẫn còn phạm vi tìm kiếm
a) Xác định phần tử am ở giữa phạm vi tìm kiếm là 42
b) Ta có am = 42 < 44
 Loại bỏ nửa dãy trước chắc chắn không chứa x
 Phạm vi tìm kiếm = nửa dãy bên phải số 42.
Lật phần tử giữa dãy là số 55 > 44. Xét tiếp các số bên trái số 55 chỉ còn số 44. Thông báo tìm thấy x = 44 ở vị trí 5
 Kết thúc thuật toán
- Báo cáo, thảo luận: GV gọi HS trong nhóm trả lời, HS nhóm khác nhận xét, bổ sung.
- Kết luận, nhận định: GV đánh giá kết quả của HS, chốt lại kiến thức
Bước1: Phạm vi tìm kiếm là dãy ban đầu
Bước 2: Lặp khi vẫn còn phạm vi tìm kiếm
a) Xác định phần tử am ở giữa phạm vi tìm kiếm
b) Nếu x = am
 Thông báo tìm thấy x ở vị trí m
 Kết thúc thuật toán
Trái lại:
 Loại bỏ nửa dãy chắc chắn không chứa x
 Phạm vi tìm kiếm = nửa dãy còn lại
Hết nhánh
Hết lặp
Bước 3: (đã hết dãy số mà không thấy x). Thông báo không có x trong dãy
Hoạt động 2.3: Phương pháp “chia để trị” với bài toán tìm kiếm.
a) Mục tiêu: 
- Biết được ý nghĩa của việc chia bài toán thành các bài toán nhỏ hơn.
b) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ: 
+ GV gọi học sinh đọc phần 3 trong SGK: 
 Học sinh thảo luận theo nhóm bàn trả lời câu hỏi: SGK Cho dãy số: 5; 11; 18; 39; 41; 52; 63; 70; Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm x = 60 trong dãy trên.
- Thực hiện nhiệm vụ: Các nhóm thảo luận và trả lời câu hỏi ra bảng nhóm.
- Báo cáo, thảo luận: GV gọi HS trong nhóm trả lời, HS nhóm khác nhận xét, bổ sung.
- Kết luận, nhận định: GV đánh giá kết quả của HS, chốt lại kiến thức
Bài toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách làm này cho đến khi nhận được kết quả.
3. Hoạt động 3: Luyện tập (10’) 
a) Mục tiêu: HS vận dụng được kiến thức về thuật toán tìm kiếm nhị phân để mô phỏng lại các bước tìm kiếm.
b) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ: 
+ GV chiếu nội dung bài luyện tập:
Câu hỏi. 
Em hãy mô tả cách tra cứu tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không? 
- Thực hiện nhiệm vụ: 
+ Hs lắng nghe và trả lời cá nhân theo yêu cầu vào vở.
+ Gv hướng dẫn, quan sát trong quá trình học sinh làm bài
- Báo cáo, thảo luận: Hs làm bài cá nhân vào vở.
- Kết luận, nhận định: Gv nhận xét bài học sinh, chỉ ra một số lưu ý, các lỗi HS hay mắc phải khi làm bảng mô phỏng.
Lời giải: Cách tra cứu, tìm giải nghĩa một từ trong từ điển:
Bước 1: Xác định từ cần tìm là gì. Ví dụ, chúng ta muốn tìm từ "hat".
Bước 2: Chia đôi cuốn từ điển thành 2 phần bằng nhau, chọn 1 từ bất kì nằm ở giữa cuốn từ điển. Ví dụ, chọn từ "mother". Vì cuốn từ điển sắp xếp theo bảng chữ cái nên chứ h sẽ đứng trước chữ m nên tiếp theo ta chỉ cần tìm trong nửa đầu của cuốn từ điển.
Bước 3: Ta lại tiếp tục chia đổi nửa đầu cuốn từ điển và thực hiện tương tự như bước 2. Chọn một từ nằm ở giữa, ví dụ là từ "go". Vì chữ g đứng trước chữ h nên phạm vi tìm kiếm sẽ từ chữ "go" cho đến chữ "mother".
Bước 4: Chúng ta tiếp tục chia đôi phạm vi từ chữ "go" cho đến chữ "mother" và thực hiện tương tự bước 3 cho đến khi ta tìm được từ "hat" thì ta kết thúc việc tìm kiếm.
4. Hoạt động 4: Vận dụng (10’)
a) Mục tiêu: HS vận dụng được kiến thức về tìm kiếm nhị phân để thực hiện tìm kiếm theo yêu cầu
b) Tổ chức thực hiện:
* Chuyển giao nhiệm vụ: Gv nêu yêu cầu
Nhóm 1 + 2: Câu hỏi 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân
Nhóm 3 + 4: Câu hỏi 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.
- Thực hiện nhiệm vụ: 
+ Hs lắng nghe và thực hiện theo nhóm.
+ Gv quan sát và hướng dẫn trong quá trình HS thực hành.
- Báo cáo, thảo luận: GV gọi HS trong nhóm trả lời, HS nhóm khác nhận xét, bổ sung.
- Kết luận, nhận định: GV đánh giá kết quả của HS, nhận xét bài và chốt lại kiến thức.
Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.
Câu trả lời:
Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:
Gọi số cần tìm kiếm là x, gọi dãy số đã sắp thứ tự là a1 cho đến an.
Bước 1: Chia dãy thành 2 phần bằng nhau và so sánh giá trị cần tìm với giá trị nằm giữa 2 phần đó (gọi là an/2). Có thể xảy ra hai trường hợp:
Nếu giá trị cần tìm lớn hơn (x > an/2), ta xét nửa sau của dãy (từ an/2 đến an).
Nếu giá trị cần tìm nhỏ hơn (x < an/2), thực hiện xét nửa trước của dãy (từ a1 đến an/2).
Bước 2: Sau đó, ta xét lại phạm vi tìm kiếm phù hợp. Nếu x = an/2, ta xác định được vị trí của số cần tìm và kết thúc tìm kiếm.
Bước 3: Tiếp tục thực hiện 2 bước trên cho đến khi tìm được giá trị cần tìm. Nếu không tìm được x ta suy ra trong dãy không tồn tại số có giá trị như đề bài yêu cầu.
Câu 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.
Câu trả lời:
Không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng thuật toán tìm kiếm nhị phân.