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:

Có thể 

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:

Bài toán 1:

Miền dữ liệu: tất cả các ảnh có trên các máy tính kết nối mạng Internet. 

Kết quả: các ảnh có hình hoa hồng.

Bài toán 2:

miền dữ liệu: các tệp văn bản có trên đĩa cứng máy tính. 

Kết quả: bai-hoc- 1.docx.

Bài toán 3: 

Miền đữ liệu: 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ố. 

Kết quả: 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.

Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.
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: đường đi từ nhà em đến trường 

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

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

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; thông báo không tìm thấy và trả về giá trị -1 nếu không, có thể duyệt từ đầu dãy hoặc 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:

Dãy A có 11 phần tử, tệ nhất thì phần tử cần tìm ở cuối dãy. 

• Cần thực hiện 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 thuật toán tìm được ngay kết quả 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:

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 phần tử đó nằm ở cuối hoặc 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:

• Thuật toán tìm kiếm nhị phâ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à ngược lại, tiếp tục đến khi tìm thấy hoặc đã duyệt hết.

• Tối ưu hơn ở các mảng có độ dài lớn và đã được sắp xếp. 

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

• 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?

• 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?

• 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. 10 phần tử 

2.  6 phần tử 

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, 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 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 [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 chươ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 (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.")