BÀI 14: THUẬT TOÁN TÌM KIỀM TUẦN TỰ | Tin Học 7 | Chủ đề 5: Giải quyết vấn đề với sự trợ giúp của máy tính. - Lớp 7 - Kết Nối Tri Thức Với Cuộc Sống

Trang 71

Sau bài học này em sẽ:
•    Giải thích được thuật toán tìm kiếm tuần tự.
•    Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm tuần tự trên một bộ dữ liệu vào có kích thước nhỏ.

THUẬT TOÁN TÌM KlẾM TUẨN TỰ

Trong cuộc sống, chúng ta thường xuyên phải tìm kiếm dữ liệu đề biết về đối tượng trong hàng chục, hàng trăm, hàng nghìn, thậm chí hàng triệu nội dung liên quan đến nó. Thuật toán tìm kiếm giúp chúng ta tìm được dữ liệu cần thiết để có được thông tin ta cần một cách hiệu quả.

Trong tình huống khởi động, công việc mà An cần làm có thể nêu thành bài toán tìm kiếm như sau:

• Đầu vào: danh sách khách hàng; họ tên khách hàng cần tìm.

• Đầu ra: địa chỉ của khách hàng cần tìm.

An thực hiện tìm kiếm lần lượt từ đầu đến cuối danh sách khách hàng. Cách tìm kiếm này gọi là tìm kiếm tuần tự. Với mỗi họ tên khách hàng trong danh sách, An kiểm tra xem có đúng họ tên khách hàng mà mẹ yêu cầu không, nếu đúng thì ghi ra địa chỉ và kết thúc công việc, còn không thì chuyển đến họ tên khách hàng tiếp theo. Nếu tìm hết danh sách mà vẫn không thấy thì thông báo là không tìm thấy và kết thúc. Như vậy, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp. Đây chính là cấu trúc lặp. Hai điều kiện cần kiểm tra để dừng vòng lặp là:

• Điều kiện thứ nhất: kiểm tra họ tên khách hàng có đúng là họ tên cần tìm không.

• Điều kiện thứ hai: kiểm tra đã hết danh sách chưa.

Các bước thực hiện tìm kiếm địa chỉ khách hàng của An được mô tả ở sơ đồ khối trong Hình 14.1.

Hoạt động 1: Tìm địa chỉ

Danh sách khách hàng được mẹ An ghi trong Bảng 14.1 như sau:

Bảng 14.1. Danh sách khách hàng

Em hãy kẻ Bảng 14.2 vào vở và điền các bước thực hiện thuật toán tìm kiếm tuần tự để tìm ra địa chỉ của khách hàng có họ tên là “Thanh Trúc".

Bảng 14.2. Các bước tìm địa chỉ khách hàng

Trang 73

Mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên:

Bước 1. Xét vị trí đầu tiên của danh sách.

Bước 2. Nếu giá trị của phần tử ở vị trí đang xét bằng giá trị cần tìm thì chuyển sang Bước 4, nếu không thì chuyền đến vị trí tiếp theo.

Bước 3. Kiểm tra đã hết danh sách chưa. Nếu đã hết danh sách thì chuyền sang Bước 5, nếu chưa thì lặp lại từ Bước 2.

Bước 4. Trả lời “Tìm thấy” và chỉ ra vị trí phần tử tìm được; Kết thúc.

Bước 5. Trả lời "không tìm thấy"; Kết thúc.

Thuật toán tìm kiếm tuần tự thực hiện tìm lần lượt từ đầu đến cuối danh sách, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.

LUYỆN TẬP

Cho danh sách tên các nước sau đây:

Bolivia, Albania, Canada, Việt Nam, Iceland, Bồ Đào Nha Bolivia, Albania, Scotland, Canada, Việt Nam, Iceland, Bồ Đào Nha, Greenland, Đức

Em hãy kẻ Bảng 14.3 vào vở và điền các bước thực hiện thuật toán tìm kiếm tuần tự để tìm tên nước Iceland trong danh sách trên (dòng 1 là ví dụ minh hoạ).

Bảng 14.3. Các bước tìm kiếm tuần tự

VẬN DỤNG

Em hãy lập danh sách những cuốn sách mà em có. Sau đó sử dụng thuật toán tìm kiếm tuần tự để tìm một cuốn sách trong danh sách đó.