Bài thuyết trình Tin học Lớp 7 - Bài 15: Thuật toán tìm kiếm nhị phân - Nguyễn Khánh Linh

Nội dung text: Bài thuyết trình Tin học Lớp 7 - Bài 15: Thuật toán tìm kiếm nhị phân - Nguyễn Khánh Linh

1. BÀI 15 : THUẬT TOÁN TÌM KIẾM NHỊ PHÂN slidesmania.com NHÓM 4
2. THÀNH VIÊN ὼ Nguyễn Đình Duy Nguyễn Khánh Linh ὼ Nguyễn Hữu Tuấn Dũng Đặng Thị Khánh Ly ὼ Chu Thị Hồng Hạnh Phùng Đắc Quyền ὼ Nguyễn Văn Huân Nguyễn Thị Kiều Trang ὼ Đặng Ngọc Huyền slidesmania.com
3. NỘI DUNG 1.THUẬT TOÁN TÌM KIẾM 2. SẮP XẾP VÀ TÌM KIẾM NHỊ PHÂN slidesmania.com
4. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN slidesmania.com
5. Thuật toán tìm kiếm nhị phân: ● Thực hiện trên danh sách đã được sắp xếp. Bắt đầu từ vị trí ở giữa danh sách. ● Tại mỗi bước, so sánh giá trị cần tìm với giá trị ở vị trí giữa danh sách, nếu lớn hơn thì tìm ở nửa sau của danh sách, nếu nhỏ hơn thì tìm ở nửa trước của danh sách, nếu bằng thì dừng lại. ● Chừng nào chưa tìm thấy và chưa hết thì còn tìm tiếp slidesmania.com
6. Mô tả 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à 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ị ở vị trí giữa thì kết luận và kết thúc. Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vùng 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 chỉ còn nửa sau của dãy. slidesmania.com Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho đến khi 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).
7. Mô tả bằng ngôn ngữ tự nhiên: slidesmania.com Lưu ý: “nửa trước” và “nửa sau” không gồm phần tử giữa.
8. SẮP XẾP VÀ TÌM KIẾM slidesmania.com
9. Tại sao cần sắp xếp ? Trong ví dụ ở mục 1, khách hàng tên Trúc được tìm thấy trong 3 bước theo thuật toán tìm kiếm nhị phân còn phải thực hiện 8 bước theo thuật tìm kiếm tuần tự slidesmania.com
10. Trong trường hợp mà tên khách hàng không có trong danh sách thì chúng ta cần: Thực hiện 9 bước lặp theo Thực hiên 4 bước thuật tìm kiếm lặp theo thuật tuần tự tìm kiếm nhị phân => Như vậy, thấy được thuật toán tìm slidesmania.com kiếm nhị phân nhanh hơn thuật tìm kiếm tuần tự.
11. Để thực hiện thuật toán nhị phần chúng ta cần Sắp xếp Lợi ích của việc sắp Chúng ta cần sắp xếp các dữ liệu theo bảng xếp chữ cái Danh sách được sắp xếp, tại mỗi bước lặp, thuật toán tìm kiếm nhị phần thu hẹp lại chỉ slidesmania.com còn phạm vị một nủa
12. THANKTHANK YOUYOU FORFOR WATCHINGWATCHING !! slidesmania.com