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

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI GIẢNG!

BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

NỘI DUNG BÀI HỌC

KHỞI ĐỘNG

KHÁM PHÁ

LUYỆN TẬP

VẬN DỤNG

1. KHỞI ĐỘNG

                   Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?

Để việc tìm kiếm của An được dễ dàng hơn, bạn có thể:

+ Sắp xếp danh sách để tìm dễ hơn.

+ Đưa danh sách vào phần mềm soạn thảo văn bản hoặc bảng tính và sử dụng chức năng tìm kiếm của phần mềm để tìm kiếm.

2. KHÁM PHÁ

• 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.
• Thuật toán tìm kiếm tuần tự 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
• Thuật toán tìm kiếm nhị phân chỉ thực hiện 4 bước.
• 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?
• 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.

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.

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

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.

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.

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.

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. Và tương tự ngược lại.

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

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.

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.

TRÒ CHƠI TÌM SỐ

• Chuẩn bị: Hai bạn chơi A, B và 10 tâm thẻ ghi 10 số khác nhau (các số đều nhỏ hơn 20).
• Ví dụ, 10 số trên các tấm thẻ là 2, 3, 5, 6, 8, 9, 11, 15, 16, 18. Giả sử A giữ 10 tấm thẻ và B là người tìm kiếm.
• Yêu cầu: Bạn sử dụng thuật toán tìm kiếm nhị phân để tìm một số nhỏ hơn 20 trong các tấm thẻ của bạn A.

TRÒ CHƠI TÌM SỐ

• Bước 1. A úp lần lượt 10 chiếc thẻ lên bàn theo thứ tự các số từ bé đến lớn.
• Bước 2. B cho A biết con số mình cần tìm.
• Bước 3. B chọn tấm thẻ ở vị trí giữa.
• Bước 4. A hé mở tấm thẻ và trả lời B bằng cách nói một trong ba cụm từ “bằng nhau”, “lớn hơn” hoặc “bé hơn” tùy thuộc vào kết quả.
• Bước 5. Tùy vào câu trả lời của A mà B chọn nửa dãy tiếp theo để tìm kiếm.
• Bước 6. Lặp lại các bước 3, 4, 5 cho đến khi B tìm thấy số cần tìm hoặc đã tìm hết dãy số.
• Bước 7. Hoán đổi vị trí của A và B trong lượt chơi tiếp theo.