Bài giảng Tin học Lớp 7 - Bài 15: Thuật toán tìm kiếm nhị phân
Bạn đang xem tài liệu "Bài giảng Tin học Lớp 7 - Bài 15: Thuật toán tìm kiếm nhị phân", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
giao_an_tin_hoc_lop_7_bai_15_thuat_toan_tim_kiem_nhi_phan.pptx
Nội dung text: Bài giảng Tin học Lớp 7 - Bài 15: Thuật toán tìm kiếm nhị phân
- 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?
- BÀI 15 MỤC TIÊU - Giải thích được thuật toán tìm kiếm nhị phân. - Biểu diễn mô phỏng 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ỏ. - Giải thích được mối liên hệ giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa
- BÀI 15 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 2. SẮP XẾP VÀ TÌM KIẾM
- 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
- Khi danh sách khách hàng ngày càng nhiều, để thuận lợi cho việc tìm kiếm, An đã giúp mẹ soạn thảo danh sách khách hàng trên máy tính với tên khách hàng được sắp xếp theo thứ tự chữ cái. Giả sử An cần tìm địa chỉ của khách hàng tên là “Trúc” trong danh sách khách hàng như Hình 15.1.1
- Mai # Trúc Bài toán: An cần tìm địa chỉ của khách Trúc = Trúc Mai < Trúc hàng tên là “Trúc” trong danh sách khách hàng Các bước tìm kiếm Sắp xếp danh sách theo tên Bước 1: Xét vị trí giữa của danh sách Bước 2: Xét vị trí giữa của nửa sau của Mai danh sách Bước 3: Xét vị trí giữa của nửa sau còn lại của danh sách Trang Trúc Thuật toán nhị phân
- EmNếuEmTheo hãy hãykhông em so cho thực sánh thỏa biết hiện sốmãn thuật bước thuật điều toán lặp toán kiện tìmđể thựckiếmtìmđó hiệnkiếm thuậttuần tìm nhị tựtoán kiếm phảiphân, tìm tuầnthực danhkiếm tựhiện nhịsáchvới bao số kháchbướcnhiêuphân lặp hàng cóbước thực cần để hiệnh tìn thỏaiện được được của mãn kháchthuật hay điều toánhàng tìmkiện không? kiếmtên gì?“Trúc”? nhị phân?
- 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 được 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 vùng tìm kiếm không còn phần tử nào (Bước 1).
- L L LOVE G PIRCE TẠML BIỆT VÀ SHẸN GẶP LẠI T H L