BÀI 19 - BÀI TOÁN TÌM KIẾM

MỞ ĐẦU

CH 1: Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?

Đáp án chuẩn:   

An có thể xác định được theo quy luật tìm kiếm tuần tự.

1. BÀI TOÁN TÌM KIẾM TRÊN THỰC TẾ

CH 1: Với các bài toán tìm kiếm sau, hãy thảo luận về miễn dữ liệu và khả năng các kết quả có thể tìm được của bài toán:

Bài toán 1. Em cần tìm hình ảnh các cây hoa hồng đẹp trên Intemet để đưa vào bài trình bày về cách trồng hoa.

Bài toán 2. Em cần tìm một tệp văn bản có tên bai-noc-1.docx trên máy tính của em nhưng đã lâu rồi chưa sử dụng lại.

Bài toán 3. Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học của thành phố.

Đáp án chuẩn:

• Bài toán 1: miền dữ liệu là tất cả các ảnh có trên các máy tính kết nối mạng Intemet. Kết quả là các ảnh có hình hoa hồng.

• Bài toán 2: miền dữ liệu là các tệp văn bản có trên đĩa cứng máy tính của em. Kết quả là tệp có tên bai-hoc-1.docx.

• Bài toán 3: miền dữ liệu là danh sách học sinh và điểm các bài dự thi của kì thi Olympic Tin học thành phố. 

CH 2: Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.

1. Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.

2. Bài toán tìm tất cả các trường trung học phổ thông (tên trường, địa chỉ) ở quận (huyện) em đang cư trú.

Đáp án chuẩn:

1. Miền là đường đi từ nhà em đến trường học. Kết quả: tên đường.

2. Miền các trường trung học phổ thông em đang cư trú. Kết quả: tên trường.

2. TÌM KIẾM TUẦN TỰ

HĐ 2. Thuật toán tìm kiếm tuần tự

CH 1: Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.

Đáp án chuẩn:

Thuật toán tìm kiếm tuần tự: Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phần tử bằng K; ngược lại, thông báo không tìm thấy và trả về giá trị -1. Thuật toán có thê duyệt từ đâu dãy hoặc từ cuối dãy.

Câu hỏi

CH 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

Đáp án chuẩn:

Cần tìm phần tử có giá trị là 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thực hiện duyệt từng phần tử trong dãy này để tìm kiếm phần tử có giá trị là 47. Dãy A có 11 phần tử, trong trường hợp xấu nhất, ta cần duyệt qua toàn bộ dãy A để tìm thấy phần tử có giá trị là 47. Vậy, số lần duyệt cần thực hiện là 7 lần.

CH 2: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

Đáp án chuẩn:

Thuật toán tìm kiếm tuần tự sẽ tìm được ngay kết quả sau khi duyệt qua ít bước nhất có thể. Điều này xảy ra khi phần tử cần tìm nằm ở vị trí đầu tiên của dãy.

CH 3: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần nhiều bước nhất? Cho ví dụ.

Đáp án chuẩn:

Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm. Ví dụ: Giả sử chúng ta cần tìm phần tử 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, thuật toán sẽ phải duyệt qua toàn bộ để xác nhận phần tử này không có trong dãy.

3. TÌM KIẾM NHỊ PHÂN

CH 1: Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dãy các phần từ đã sắp xếp.

Đáp án chuẩn:

Thuật toán tìm kiếm nhị phân tối ưu hơn tìm kiếm tuyến tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

CH 2: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}

1. Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?
2. Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?
3. Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

Đáp án chuẩn:

1. Với thuật toán tìm kiếm tuần tự, cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34
2.  Với thuật toán tìm kiếm nhị phân, cần duyệt 6 phần tử để tìm ra phân tử có giá trị bằng 34
3. Nếu số bé hơn K lật 10 lần, số lớn hơn K lật 1 lần.

LUYỆN TẬP

CH 1: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.

Đáp án chuẩn:

1. Không dừng ngay khi tìm thấy số đầu tiên bằng x mà vẫn tiếp tục kiểm tra đến cuối dãy.

2. Không cần có biến Kết quả để đánh dấu đã Tìm thấy hay Chưa tìm thấy. Tất cả các thao tác kiểm tra Kết quả đều xóa bỏ. Không còn bước 3.

3. Thêm biến đếm, bắt đầu với đếm =0, mỗi khi thấy số đang xét = x thì tăng đếm lên 1 đơn vị.

CH 2: Viết chương trình của thuật toán tìm kiếm nhị phân với dầy sắp xếp giảm dần.

Đáp án chuẩn:

def binary_search(arr, x):

   left = 0

   right = len(arr) - 1

   while left <= right:

       mid = (left + right) // 2

       if arr[mid] == x:

           return mid

       elif arr[mid] < x:

           right = mid - 1

       else:

           left = mid + 1

   return -1

# Sử dụng hàm để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]

arr = [9, 8, 6, 5, 3, 1]

x = 5

result = binary_search(arr, x)

if result != -1:

   print("Element is present at index", str(result))

else:

   print("Element is not present in array")

VẬN DỤNG

CH 1: Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.

Đáp án chuẩn:

def sequential_search(names, target):

 found = []

 for name in names:

  if name == target:

   found.append(name)

 return found

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Gọi hàm tìm kiếm tuần tự

found_names = sequential_search(class_names, target_name)

if len(found_names) > 0:

 print("Các học sinh có tên là", target_name, "là:", found_names)

else:

 print("Không tìm thấy học sinh nào có tên là", target_name)

CH 2: Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.

Đáp án chuẩn:

def binary_search(names, target):

 low = 0

 high = len(names) - 1

 while low <= high:

  mid = (low + high) // 2

  mid_name = names[mid]

  if mid_name == target:

   return mid

  elif mid_name < target:

   low = mid + 1

  else:

   high = mid - 1

return -1

# Danh sách tên học sinh trong lớp (đã được sắp xếp theo thứ tự bảng chữ cái)

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Trung"]

# Tên học sinh cần tìm

target_name = "Minh"

# Gọi hàm tìm kiếm nhị phân

result = binary_search(class_names, target_name)

if result != -1:

 print("Học sinh có tên là", target_name, "được tìm thấy tại vị trí", result)

else:

 print("Học sinh có tên là", target_name, "không tồn tại trong danh sách.")