Bài thuyết trình Tin học Lớp 7 - Bài: Thuật toán tìm kiếm nhị phân - Cao Ngọc Chi

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

1. GIỚI THIỆU THÀNH VIÊN: + nhóm trưởng: Cao Ngọc Chi + Phó nhóm: Đỗ Bá Bách + Thư kí: Nguyễn Hải Linh + Phụ trách powerpoint: Phạm Văn Đức + Nguyễn Văn Thái + Nguyễn Tuấn Thắng + Chu Thái Sơn + Nguyễn Trung Quân + Nguyễn Quốc Bảo + Nguyễn Tuấn Đản
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Thế nào là thuật toán tìm kiếm nhị phân?
3. MỤC LỤC Thuật toán tìm kiếm Cách mô tả thuật toán 01 nhị phân là gì? 02 tìm kiếm nhị phân bằng ngôn ngữ tự nhiên Mối quan hệ giữa sắp Tổng kết 03 xếp và tìm kiếm 04
4. WHOA! Một bài học thật thú vị!!!
5. 01 Thuật toán tìm kiếm nhị phân
6. GiỚI THIỆU Tìm kiếm nhị phân còn gọi là tìm kiếm nửa khoảng, là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp
7. Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Nếu hai giá trị không bằng nhau, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó. Nếu phép tìm kiếm kết thúc khi nửa còn lại trống thì giá trị cần tìm không có trong mảng.
8. => Kết luận Thuật toán tìm kiếm nhị phân được thực hiện trên danh sách được sắp xếp từ nhỏ đến lớn. Bắt đầu từ giữa danh sách
9. 02 Các bước mô tả thuật toán tìm kiếm nhị phân
10. MÔ TẢ THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Bước 1 Bước 2 Bước 3 Nếu vùng tìm kiếm không Xác định vị trí giữa của Nếu giá trị cần tìm bằng tìm thấy phần tử nào thì vùng tìm kiếm: nửa trước giá trị của vị trí giữa thì kết luận không tìm thấy và nửa sau vị trí giữa kết luận và kết thúc và thuật toán kết thúc Bước 4 Bước 5 Nếu giá trị cần tìm nhỏ hơn ( lớn hơn) giá trị vị trí Lặp lại từ bước 1-4 để tìm giữa thì vùng tìm kiếm chỉ được phần tử cần tìm còn nửa trước( nửa sau) của dãy
11. LƯU Ý Tại mỗi bước lặp so sánh giá trị Cần tìm một giá trị của vị trí nằm giữa danh sách nếu bằng thì dừng lại, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu lớn hơn thì trong nửa sau của danh sách Chừng nào chưa tìm thấy và vùng tìm kiếm còn phần tử thì còn tìm tiếp
12. 03 MỐI QUAN HỆ GIỮA SẮP XẾP VÀ TÌM KIẾM
13. A PICTURE ALWAYS REINFORCES THE CONCEPT Images reveal large amounts of data, so remember: use an image instead of a long text. Your audience will appreciate it
14. MỐI QUAN HỆ GIỮA 2 THUẬT TOÁN *TÌM HIỂU SỰ KHÁC NHAU GIỮA THUẬT TUẦN TỰ NHỊ PHÂN TOÁN TÌM KIẾM TUẦN TỰ & THUẬT Thực hiện từ đầu tới Thực hiện trên danh TOÁN TÌM KIẾM NHỊ cuối danh sách, chừng sách đã được sắp xếp PHÂN nào chưa tìm thấy và theo thứ tự từ nhỏ đến chưa tìm hết thì còn tìm lớn. Bắt đầu từ vị trí ở tiếp giữa danh sách
15. MỐI QUAN HỆ GIỮA SẮP XẾP VÀ TÌM KIẾM Sắp xếp giúp cho việc tìm kiếm được thực hiện nhanh hơn Khi lập danh sách, chúng ta MỐI QUAN HỆ nên sắp xếp theo một trình tự để có Thuật toán tìm thể dễ tìm hơn kiếm nhị phân nhanh hơn thuật toán tìm kiếm tuần tự
16. 04 TỔNG KẾT
17. TỔNG KẾT Các bước mô tả Thuật toán tìm thuật toán tìm kiếm nhị phân là gì kiếm nhị phân Mối quan hệ giữa sắp xếp và tìm kiếm
18. ÁP DỤNG ĐỜI SỐNG Chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân để tìm được người khách hàng đang nợ tiền, tìm được số điện thoại của người quen,