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

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.

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.

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

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

- 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