Tin học 11 Cánh diều Chủ đề FCS Bài 7: Lập trình giải 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.

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

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

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

Nhiệm vụ 1. Em hãy thực hiện các yêu cầu sau:

a) Viết mã giả cho thuật toán tìm kiếm nhị phân.

b) Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.

c) Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Hướng dẫn: Sau lần chia đôi đầu tiên; phạm vi tìm kiếm còn lại \(\frac{n}{2}\) số sau khi chia đôi lần thứ hai, dãy còn lại \(\frac{n}{4}\) số; sau khi chia đôi lần thứ ba, dãy còn lại \(\frac{n}{8}\) số,... sau khi chia đôi lần k dãy còn lại \(\frac{n}{2^{k}}\) số. Kết thúc khi \(2^{k}~n\).

Nhiệm vụ 2. Em hãy thực hiện các yêu cầu sau:

a) Viết chương trình Python thực hiện tìm kiếm tuần tự.

b) Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).

c) Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của Python.

Nhiệm vụ 3. Viết hàm thực hiện tìm kiếm nhị phân nhận hai tham số đầu vào: dãy số a và giá trị x cần tìm.

Em hãy nêu ra một vài ví dụ về bài toàn tìm kiếm trong thực tế?

Hướng dẫn giải:

- Tìm kiếm sản phẩm trong cơ sở dữ liệu của một trang thương mại điện tử.

- Tìm kiếm thông tin liên hệ của một người trong danh sách khách hàng của một doanh nghiệp.

- Tìm kiếm một file hoặc thư mục trong hệ thống tệp của máy tính.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu y tế để tìm kiếm bệnh nhân cần điều trị.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu của một trang tuyển dụng để tìm kiếm ứng viên phù hợp.

Học xong bài này, em sẽ:

- Phát biểu được bài toán tìm kiếm.

- Viết được chương trình cho một số thuật toán tìm kiếm.

- Vận dụng được quy tắc thực hành xác định được độ phức tạp của một vài thuật toán tìm kiếm đơn giản.

3.1. Trắc nghiệm Bài 7 Chủ đề FCS SGK Tin học 11 Cánh diều

Như vậy là các em đã xem qua bài giảng Bài 7 Chủ đề FCS SGK Tin học 11 Cánh diều Khoa học máy tính. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Cánh diều Chủ đề FCS Bài 7.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Cánh diều Chủ đề FCS Bài 7 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 117 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 1 trang 120 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 2 trang 120 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 3 trang 120 SGK Tin học 11 Cánh diều - CD

Vận dụng trang 120 SGK Tin học 11 Cánh diều - CD

Câu hỏi 1 trang 120 SGK Tin học 11 Cánh diều - CD

Câu hỏi 2 trang 120 SGK Tin học 11 Cánh diều

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!