tailieunhanh - Bài giảng môn Tin 7 bài 2 sách Cánh diều: Tìm kiếm nhị phân

"Bài giảng môn Tin 7 bài 2 sách Cánh diều: Tìm kiếm nhị phân" có nội dung về: chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự; Thuật toán tìm kiếm nhị phân; Phương pháp chia để trị với bài toán tìm kiếm; .Mời quý thầy cô cùng các em tham khảo chi tiết giáo án tại đây nhé. | BÀI 2 TÌM KIẾM NHỊ PHÂN MỞ ĐẦU 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 Có 8 thẻ mỗi thẻ ghi một số 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 Câu trả lời Đồng ý với ý kiến của bạn Thanh An vì chúng ta chỉ cần chia đôi dần dãy số đã sắp thứ tự và lần lượt tìm kiếm trong phạm vi phù hợp để tìm ra kết quả mà chúng ta mong muốn thì chỉ cần 3 lần là có thể tìm ra kết quả. 1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự Ý tưởng chia đôi dần để tìm một số trong một dãy số Ví dụ 1 Tìm x 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm Minh họa các bước a1 a2 a3 a4 a5 a6 a7 a8 Xuất phát 6 12 18 42 44 55 67 94 Bước 1 42 44 55 67 94 Bước 2 44 55 Bươc 3 44 Mô phỏng thuật toán tìm kiếm nhị phân x 44 a1 a2 a3 a4 a5 a6 a7 a8 a 6 12 18 42 44 44 55 67 94 i 1 2 3 4 5 6 7 8 L ượt thứ nhất agiữa là a4 42 42 44 vùng tìm kiếm thu hẹp trong phạm vi là a5 L ượt thứ ba agiữa là a5 44 44 44 x Vậy số cần tìm là i 5. Ví dụ 2 Tìm x 21 trong dãy 10 phần tử đã sắp xếp thứ tự không giảm A 2 4 5 6 9 21 22 30 31 33 i 1 2 3 4 5 6 7 8 9 10 L ượt thứ nhất agiữa là a5 9 9 21 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7 L ượt thứ ba agiữa là a6 21 21 21 Vậy số cần tìm là i 6. 2. 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 Bước 1. 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 vị trí tìm