Giáo án và PPT Tin học 7 cánh diều Bài 2: Tìm kiếm nhị phân

BÀI 2: TÌM KIẾM NHỊ PHÂN

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS đọc tình huống mở đầu 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 tìm nhanh hơn tìm kiếm tuần tự không?

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu chia đôi dần để tìm kiếm một số trong dãy số đã sắp xếp thứ tự

Giáo viên đưa ra tình huống cho học sinh thảo luận nhóm và trả lời câu hỏi:

Có 8 thẻ, mỗi thẻ ghi một số Thứ nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X chẳng hạn. Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho rằng chỉ cần không quá 3 lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?

Sản phẩm dự kiến:

- Ý tưởng: chia đôi dần để tìm một số trong một dãy số

- Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm

- Giải thích:

          + Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy. Vì x > a₄ nên nửa đầu dãy chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a₅ đến a₈.

          + Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₅ đến a₈. Lấy a₆ là số có vị trí giữa dãy. Vì x < a₆ nên nửa sau chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một số a₅

=> Phạm vi tìm kiếm chỉ còn 1 số kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ 5

Hoạt động 2. Tìm hiểu thuật toán tìm kiếm nhị phân 

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

- Mô tả thuật toán:

- Chú ý: Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự

Hoạt động 3. Tìm hiểu phương pháp “chia để trị” với bài toán tìm kiếm 

Giáo viên đưa ra ví dụ về câu chuyện bó đũa, học sinh thảo luận nhóm và trả lời câu hỏi: “Để giải một bài toán lớn, người ta cần làm gì?”

Sản phẩm dự kiến:

- Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”

- Thuật 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 này cho đến khi nhận được kết quả.

HOẠT ĐỘNG LUYỆN TẬP

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?

A. Thuật toán tìm kiếm nhị phân áp dụng được cho dãy đã sắp xếp thứ tự và dãy không sắp xếp thứ tự .

B. Thuật toán tìm kiếm nhị phân áp dụng được cho mọi bài toán.

C. Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự.

D. Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy không sắp xếp thứ tự.

Câu 2: Tìm kiếm nhị phân là:

A. Tìm kiếm lần lượt từ đầu tới cuối dãy.

B. Tìm kiếm ở đầu dãy.

C. Tìm kiếm 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.

D. Tìm kiếm ở cuối dãy.

Câu 3: Điều kiện lặp trong bài toán tìm kiếm nhị phân là:

A. Kết quả= tìm thấy.

B. Phạm vi tìm kiếm dài hơn 1 và kết quả=chưa tìm thấy.

C. Xét hết dãy số

D. Cả A và C đều đúng

Câu 4: Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi:

A. Đã tìm kiếm hết dãy.

B.Đã tìm thấy kết quả mong muốn hoặc phạm vi tìm kiếm chỉ còn 1 số.

C. Đã tìm hết nửa dãy đầu.

D. Đã tìm hết nửa dãy sau.

Câu 5: Cho dãy số 2,4,6,8,9. Bài toán “Tìm vị trí của số 8 trong dãy”, có phạm vi tìm kiếm là:

A. Nửa dãy đầu.

B. Nửa dãy sau.

C. Tất cả dãy.

D. Không có phạm vi.

 Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: 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.