Nội dung bài viết

    Xem thêm

    Lý thuyết Tin học 11 (Cánh diều) Bài 7: Lập trình giải bài toán tìm kiếm

    Tóm tắt lý thuyết Tin học lớp 11 Bài 7: Lập trình giải bài toán tìm kiếm hay, chi tiết sách Cánh diều sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt Tin học 11.

    1 1,459 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Lý thuyết Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm

    A. Lý thuyết Lập trình giải bài toán tìm kiếm

    1. Bài toán tìm kiếm

    a) Khái niệm bài toán tìm kiếm

    - Các ví dụ về bài toán tìm kiếm: tìm cuốn sách, tên người, tên hàng hoá trong danh sách, tìm bản ghi trong cơ sở dữ liệu.

    - Bài toán tìm kiếm là tìm mục dữ liệu đáp ứng yêu cầu hoặc khẳng định không có mục dữ liệu đáp ứng yêu cầu đó.

    Bài toán tìm kiếm trên Internet là một nhiệm vụ của máy tìm kiếm.

    b) Tìm kiếm tuần tự bằng hàm của Python

    - Python có phương thức index tìm kiếm phần tử x trong một dãy tuần tự và trả về chỉ số của lần xuất hiện đầu tiên.

    - Nếu không tìm thấy, phương thức index báo lỗi "ValueError".

    - Có thể hạn chế tìm kiếm trong đoạn con của dãy số bằng hai tham số tuỳ chọn lo, hi.

    - Cú pháp: dãy số.index(giá_trị, lo, hi)

    - Ví dụ: Với mảng a = [1, 2, 3, 4, 5, 6] như hình bên, câu lệnh print(a.index(3,1,4)) sẽ in ra màn hình kết quả là 2, cho biết vị trí của phần tử 3 trong đoạn [1, 4] ở mảng a.

    Lý thuyết Tin học 11 (Cánh diều) Bài 7: Lập trình giải bài toán tìm kiếm (ảnh 1)

    2. Thuật toán tìm kiếm tuần tự

    - Chi tiết dần từng bước thuật toán tìm kiếm tuần tự: Hình 1 mô tả liệt kê các bước thuật toán tìm kiếm tuần tự một số x.

    Lý thuyết Tin học 11 (Cánh diều) Bài 7: Lập trình giải bài toán tìm kiếm (ảnh 1)

    - Hình 2 là kết quả thay thế những cụm từ trên bằng mã giả.

    Lý thuyết Tin học 11 (Cánh diều) Bài 7: Lập trình giải bài toán tìm kiếm (ảnh 1)

    3. Thuật toán tìm kiếm nhị phân

    - Áp dụng thuật toán tìm kiếm nhị phân cho dãy số đã sắp thứ tự.

    - Chia đôi dần dãy số và loại bỏ nửa dãy không chứa x.

    - Phạm vi tìm kiếm giảm đi một nửa sau mỗi bước.

    - Kết thúc khi tìm thấy hoặc phạm vi tìm kiếm đã hết mà không thấy (Hình 3).

    Lý thuyết Tin học 11 (Cánh diều) Bài 7: Lập trình giải bài toán tìm kiếm (ảnh 1)

    - Hướng dẫn viết mã giả của thuật toán tìm kiếm nhị phân:

    + Các cụm từ cần làm chi tiết hơn bằng mã giả: “Phạm vi tìm kiếm là dãy ban đầu”; “Vẫn còn phạm vi tìm kiếm”; “Xác định phần tử a, ở giữa phạm vi tìm kiếm”, “Loại bỏ nửa dãy chắc chắn không chứa x”, “Phạm vi tìm kiếm là nửa dãy còn lại”, “Thông báo không tìm thấy x và kết thúc”.

    + Bổ sung thêm lo là chỉ số phần tử ở đầu trái đoạn con và hi là chỉ số phần tử ở đầu phải đoạn con.

    + Công thức tính chỉ số m của phần tử ở “giữa” đoạn con là (lo + hi)/2, kết quả đảm bảo là số nguyên.

    B. Bài tập Lập trình giải bài toán tìm kiếm

    Đang cập nhật…

    Xem thêm các bài lý thuyết Tin học 11 sách Cánh diều hay, chi tiết tại: 

    Lý thuyết Bài 6: Kiểm thử và sửa lỗi chương trình

    Lý thuyết Bài 8: Lập trình một số thuật toán sắp xếp

    Lý thuyết Bài 9: Lập trình thuật toán sắp xếp nhanh

    Lý thuyết Bài 10: Thiết kế và chương trình từ trên xuống và phương pháp Mô đun hóa

    Lý thuyết Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 1,459 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: