Bài 19. Bài toán tìm kiếm trang 89
Khởi động
Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Mỗi người chơi mỗi lần chỉ được lật một thẻ để xem giá trị số in trên đó. Nếu giá trị số in trên thẻ bằng bằng số k cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối. 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?
Phương pháp giải:
Tra cứu trên internet, sách, báo,…kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Bạn An không chắc chắn xác định được thẻ nào in số K nếu An chỉ lật từng thẻ từ đầu đến cuối một cách tuần tự. Trong trường hợp xấu nhất, thẻ in số K có thể nằm ở vị trí cuối cùng của bộ thẻ, khiến An phải lật qua tất cả các thẻ trước đó trước khi tìm ra thẻ in số K. Tuy nhiên, có một cách khác để tìm ra thẻ in số K nhanh hơn, bạn An có thể làm theo các bước sau:
- Lật thẻ ở giữa bộ thẻ để xem giá trị số in trên đó.
- So sánh giá trị số in trên thẻ với số K:
- Nếu giá trị số in trên thẻ bằng số K, thì trò chơi kết thúc và thẻ đó chính là thẻ in số K.
- Nếu giá trị số in trên thẻ lớn hơn số K, thì thẻ in số K nằm ở một vị trí trước đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa đầu của bộ thẻ từ đầu đến vị trí thẻ vừa lật.
- Nếu giá trị số in trên thẻ nhỏ hơn số K, thì thẻ in số K nằm ở một vị trí sau đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa sau của bộ thẻ từ vị trí thẻ vừa lật đến cuối.
Lặp lại các bước trên cho đến khi tìm thấy thẻ in số K hoặc đã lật hết tất cả các thẻ trong bộ thẻ. Với cách làm như vậy, An sẽ tìm ra thẻ in số K trong số lượt lật thẻ ít hơn so với phương pháp tìm lần lượt, đặc biệt là khi số lượng thẻ là lớn.
? mục I HĐ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 Internet để đư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-hoc-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ố.
Phương pháp giải:
Vận dụng kiến thức mục 1 trang 89 SGK để trả lời câu hỏi.
Lời giải chi tiết:
- 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 Internet. Kết quả là các ảnh có hình 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 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ố. 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.
? mục I CH1
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ố.
Phương pháp giải:
Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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
? mục I CH2
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 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ú.
Phương pháp giải:
Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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ú.
? mục II HĐ2
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.
Phương pháp giải:
Vận dụng kiến thức mục 2 trang 90, 91 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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.
? mục II CH1
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?
Phương pháp giải:
Vận dụng kiến thức trong bài để trả lời câu hỏi.
Lời giải chi tiết:
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.
? mục II CH2
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?
Phương pháp giải:
Vận dụng kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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.
? mục II CH3
Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
Phương pháp giải:
Tra cứu trên internet, sách, báo,…kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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.
? mục III HĐ3
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.
Phương pháp giải:
Vận dụng kiến thức mục 3 trang 91 SGK để trả lời câu hỏi.
Lời giải chi tiết:
Thuậ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à ngược lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho đế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ế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 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.
? mục III CH1
Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. 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?
Phương pháp giải:
Vận dụng kiến thức mục 3 trang 91, 92, 93 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Để tìm phần tử có giá trị bằng 34 trong dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67} bằng thuật toán tìm kiếm tuần tự, ta sẽ duyệt qua từng phần tử của dãy cho đến khi tìm thấy phần tử cần tìm.
Vì phần tử 34 nằm ở vị trí thứ 11 trong dãy, nên số lần duyệt cần thực hiện để tìm ra phần tử này là 11 lần, bao gồm cả phần tử 34.
Vậy, cần duyệt qua 11 phần tử để tìm ra phần tử có giá trị bằng 34 trong dãy A.
? mục III CH2
Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. 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?
Phương pháp giải:
Vận dụng kiến thức mục 3 trang 91, 92, 93 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Với dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67}, và sử dụng thuật toán tìm kiếm nhị phân, số lần duyệt cần thực hiện để tìm ra phần tử có giá trị bằng 34 là 2 lần.
Quy trình tìm kiếm nhị phân hoạt động bằng cách so sánh giá trị cần tìm với giá trị ở giữa dãy, và dựa vào kết quả của so sánh này để tiếp tục tìm kiếm trong nửa đầu dãy chứa giá trị cần tìm. Lần đầu tiên duyệt, ta so sánh giá trị cần tìm (34) với giá trị ở giữa dãy, tại vị trí (0 + 11)/2 = 5. Vì giá trị tại vị trí này là 14 và 34 > 14, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, ta so sánh giá trị cần tìm với giá trị ở giữa dãy, tại vị trí (5 + 11)/2 = 8. Vì giá trị tại vị trí này là 31 và 34 > 31, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, giá trị cần tìm là 34 và giá trị tại vị trí này cũng là 34, nên ta đã tìm thấy phần tử cần tìm.
Tổng cộng, số lần duyệt cần thực hiện là 2 lần để tìm ra phần tử có giá trị bằng 34 bằng thuật toán tìm kiếm nhị phân trong dãy A này.
? mục III CH3
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?
Phương pháp giải:
Vận dụng kiến thức mục 3 trang 91, 92, 93 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Để tìm số lần lật thẻ nhiều nhất để tìm ra thẻ in số K trong dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67} với phương pháp lật thẻ từ đầu đến cuối và quyết định lật tiếp theo dựa trên số ghi trên thẻ so với số K, ta có thể giả sử trường hợp xấu nhất là K nằm ở đầu dãy hoặc ở cuối dãy.
Nếu K nằm ở đầu dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.
Nếu K nằm ở cuối dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến cuối dãy trước khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.
Vậy số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là 12 lần.
Luyện tập 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.
Phương pháp giải:
Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
def timTatCaGiaTri(a, x):
danhSach = []# Khởi tạo danh sách rỗng để lưu trữ các phần tử tìm thấy
for i in range(len(a)):
if a[i] == x:
danhSach.append(i)# Nếu phần tử được duyệt là phần tử cần tìm, thêm chỉ số của nó vào danh sách
return danhSach# Trả về danh sách chứa các chỉ số của các phần tử bằng giá trị cần tìm
Luyện tập 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.
Phương pháp giải:
Dựa vào kiến thức trong bài để trả lời câu hỏi.
Lời giải chi tiết:
def binary_search_reverse(arr, target):
def binary_search_reverse_helper(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_reverse_helper(arr, target, low, mid - 1)
else:
return binary_search_reverse_helper(arr, target, mid + 1, high)
return binary_search_reverse_helper(arr, target, 0, len(arr) - 1)
# Sử dụng ví dụ đầu vào để kiểm tra
arr = [10, 8, 6, 4, 2]
target = 6
# Gọi hàm tìm kiếm nhị phân với dãy sắp xếp giảm dần
result = binary_search_reverse(arr, target)
if result != -1:
print("Phần tử", target, "được tìm thấy tại vị trí", result)
else:
print("Phần tử", target, "không tồn tại trong dãy.")
Vận dụng 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.
Phương pháp giải:
Vận dụng kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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)
Vận dụng 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.
Phương pháp giải:
Vận dụng kiến thức trong bài để trả lời câu hỏi,
Lời giải chi tiết:
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.")