1. Kiến thức trọng tâm
Thực hành bài toán tìm kiếm giúp học sinh vận dụng thuật toán tìm kiếm để giải quyết bài toán cụ thể trên máy tính. Nội dung thực hành gồm: phân tích yêu cầu, chọn thuật toán, cài đặt chương trình, chạy thử và kiểm tra kết quả. Việc thực hành rèn tư duy thuật toán và kĩ năng lập trình.
Khi thực hành, cần lưu ý điều kiện áp dụng của từng thuật toán. Dãy chưa sắp xếp chỉ dùng được tìm kiếm tuần tự; dãy đã sắp xếp có thể dùng tìm kiếm nhị phân để đạt hiệu quả cao hơn. Ngoài ra, cần xác định rõ đầu ra: chỉ cần biết giá trị có xuất hiện hay không, hay cần biết vị trí của nó.
Khi cài đặt, nên chia chương trình thành các bước: nhập dãy và giá trị cần tìm, thực hiện tìm kiếm, in kết quả. Sau đó, chạy thử với nhiều bộ dữ liệu: giá trị có trong dãy, không có trong dãy, dãy một phần tử, dãy rỗng.
2. Ví dụ minh họa
Ví dụ: viết chương trình tìm kiếm tuần tự trong dãy 5, 2, 8, 1, 9, tìm giá trị 8.
day = [5, 2, 8, 1, 9]
x = 8
vitri = -1
for i in range(len(day)):
if day[i] == x:
vitri = i
break
if vitri != -1:
print("Tìm thấy", x, "tại vị trí", vitri)
else:
print("Không tìm thấy", x)
Máy duyệt lần lượt: 5 khác 8, 2 khác 8, 8 bằng 8 nên dừng và in "Tìm thấy 8 tại vị trí 2". Nếu tìm 7, chương trình duyệt hết dãy mà không gặp nên in "Không tìm thấy 7".
3. Ghi nhớ
- Thực hành gồm: phân tích, chọn thuật toán, cài đặt, chạy thử.
- Dãy chưa sắp xếp dùng tìm kiếm tuần tự; dãy đã sắp xếp có thể dùng tìm kiếm nhị phân.
- Cần chạy thử với nhiều bộ dữ liệu, kể cả trường hợp đặc biệt như dãy rỗng.
- Kết quả tìm kiếm có thể là vị trí của giá trị hoặc thông báo không tìm thấy.