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

MỞ ĐẦU

Câu 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?

Trả lời:

Theo em, 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Ế

Câu 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ố.

Trả lời:

• Với 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ó hinh hoa hồng.
• Với 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.
• Với bài toán 3, miễn đữ liệu là đanh 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ố. Kết quả là danh sách 5 bạn có thành tích cao nhất tính theo điểm trung bình.

Câu 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ú.

Trả lời:

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

Kết quả: tên đường trên bản đồ dẫn từ nhà em đến trường học

2. Miền các trường trung học phổ thông em đang cư trú.

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

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

Hoạt động 2. Thuật toán tìm kiếm tuần tự

Câu 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.

Trả lời:

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

Câu 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?

Trả lời:

Trong trường hợp này, chúng ta 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]. Ta sẽ 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ó tổng cộng 11 phần tử, và trong trường hợp xấu nhất, phần tử cần tìm là phần tử cuối cùng của dãy. Vì vậy, 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.

Câu 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?

Trả lời:

Trong trường hợp tốt nhất, thuật toán tìm kiếm tuần tự sẽ tìm được ngay kết quả (phần tử cần tìm) 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.

Câu 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ụ.

Trả lời:

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, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.

Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 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, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.

Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.

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

Câu 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.

Trả lời:

• Thụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.
• Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết 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 sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

Câu 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?

Trả lời:

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

Câu 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.

Trả lời:

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

Câu 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.

Trả lời:

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

Câu 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.

Trả lời:

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)

Câu 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.

Trả lời:

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