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 11 Cánh Diều Bài 7: Lập trình giải bài toán tìm kiếm theo chương trình Sách mới ngắn gọn nhất. Tổng hợp lý thuyết Tin học 11 trọn bộ chi tiết, đầy đủ.

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

- Soạn Tin học 11 Cánh Diều Bài 7

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.

>>> Xem toàn bộ: 

- Lý thuyết Tin học 11 Cánh Diều

- Soạn Tin 11 Cánh Diều

- Sơ đồ tư duy Tin học 11 Cánh Diều

- Trắc nghiệm Tin 11 Cánh Diều

-------------------------------------------

Trên đây Toploigiai đã cùng các bạn Tóm tắt 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 theo chương trình Sách mới ngắn gọn nhất. Mời các bạn hãy click ngay vào trang chủ Top lời giải để tham khảo và chuẩn bị bài cho năm học mới Lớp 11 nhé. Chúc các bạn học tốt.