Bài 19. Bài toán tìm kiếm

Chủ đề 6. Kĩ thuật lập trình – Bài 19. Bài toán tìm kiếm – sách giáo khoa trang 89 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 19. Bài toán tìm kiếm

Khởi động

Trò chơi lật thẻ

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ẻ. 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ẻ lật lên 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?

Lời giải:

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ẻ một từ đầu đến cuối. Tuy nhiên, có một cách tối ưu hơn để xác định thẻ in số K nhanh hơn.

Cách tối ưu là sử dụng thuật toán tìm kiếm nhị phân. Trong trường hợp này, bạn có một dãy số được sắp xếp (số trên các thẻ) và bạn muốn tìm một số cụ thể (số K). Thuật toán tìm kiếm nhị phân cho phép bạn tìm kiếm một số trong một dãy số được sắp xếp mà không cần phải xem từng số một.

1. Bài toán tìm kiếm trên thực tế

Hoạt động 1: Bài toán tìm kiếm

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

–  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 dữ 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 hỏi

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

Lời giả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ến tuần tự

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

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.

Cho dãy số A = [1, 4, 7, 8, 3, 9, 10] và cần tìm kiếm phần tử có giá trị bằng 9.

Có thể thực hiện tìm kiếm tuần tự như sau:

Bước 1. i = 0: A[0] = 1 không bằng 9.

Bước 2. i = 1: A[1] = 4 không bằng 9.

Bước 3. i = 2: A[2] = 7 không bằng 9.

Bước 4. i = 3: A[3] = 8 không bằng 9.

Bước 5. i = 4: A[4] = 3 không bằng 9.

Bước 6. i = 5. A[5] = 9 là phần tử cần tìm.

Như vậy phần tử cần tìm có chỉ số 5.

Các bước thực hiện như trên chính là các bước của thuật toán tìm kiếm tuần 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.

Thuật toán tìm kiếm tuần tự có thể viết như sau:

def LinearSeach(A, k):
    for i in range(len(A)):
        if A[i] == k:
            return i
    return -1

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?

Lời giải:

Trong trường hợp bạn sử dụng thuật toán tìm kiếm tuần tự để tìm phần tử có giá trị bằng 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86], bạn cần duyệt qua từng phần tử của dãy cho đến khi tìm thấy giá trị mong muốn hoặc duyệt qua tất cả các phần tử của dãy nếu không tìm thấy.

Trong trường hợp này, bạn cần thực hiện 8 lần duyệt.

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?

Lời giải:

Thuật toán tìm kiếm tuần tự sẽ tìm được kết quả ngay lập tức (trong ít bước nhất) khi phần tử cần tìm nằm ở vị trí đầu tiên của dãy. Khi phần tử đó nằm ở vị trí đầu tiên, bạn chỉ cần một lần duyệt đầu tiên để tìm thấy nó.

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

Lời giả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. Do đó, hiệu suất của thuật toán này là O(n), với “n” là số lượng phần tử trong dãy.

3. Tìm kiếm nhị phân

Hoạt động 3: Thuật toán tìm kiếm nhị phân

Câu 1. Cho trước một đâ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.

Lời giải:

• 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ế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 hỏi

Cho dãy A= [0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87]

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

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

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

Lời giải:

1. Với thuật toán tìm kiếm tuần tự: Để tìm phần tử có giá trị bằng 34, cần duyệt 11 phần tử để tìm ra phần tử có giá trị 34.

2. 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à 3 lần.

3. Minh bắt đầu bằng cách lật thẻ ở giữa, tức là số 17. Sau đó, tuỳ vào kết quả, Minh sẽ tiếp tục lật thẻ ở phía bên trái hoặc phía bên phải để tiếp tục tìm kiếm. Dựa vào kết quả của mỗi lần lật, Minh lật tiếp theo ở vị trí phù hợp để thu hẹp phạm vi tìm kiếm. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật là 4 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.

Lời giải:

Để chỉnh sửa thuật toán tìm kiế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, có thể sử dụng một vòng lặp để duyệt qua từng phần tử trong dãy và kiểm tra xem phần tử đó có bằng giá trị cần tìm hay không. Nếu có, bạn có thể lưu trữ vị trí của phần tử đó và in ra sau cùng.

def find_all_occurrences(arr, target):
    indices = []  # Danh sách để lưu trữ vị trí của các phần tử bằng giá trị cần tìm

    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)

    return indices

# Dãy đã cho
A = [0, 4, 8, 10, 12, 14, 17, 18, 20, 31, 34, 87]
target_value = 12

# Tìm tất cả các vị trí của phần tử có giá trị bằng target_value
occurrences = find_all_occurrences(A, target_value)

if occurrences:
    print(f"Các phần tử có giá trị {target_value} nằm ở vị trí {occurrences}")
else:
    print(f"Không tìm thấy phần tử nào có giá trị {target_value}")

Khi bạn chạy mã này với target_value là 12 và dãy A đã cho, nó sẽ trả về [4], đại diện cho việc phần tử có giá trị 12 nằm ở vị trí thứ 4 trong dãy.

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.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Tránh tràn số nguyên

        if arr[mid] == target:
            return mid  # Trả về vị trí của phần tử cần tìm
        elif arr[mid] < target:
            right = mid - 1  # Tìm kiếm trong nửa bên trái của mảng
        else:
            left = mid + 1  # Tìm kiếm trong nửa bên phải của mảng

    return -1  # Trả về -1 nếu phần tử không tồn tại trong mảng

# Dãy đã sắp xếp giảm dần
A = [87, 34, 31, 20, 18, 17, 14, 12, 10, 8, 4, 0]
target_value = 12

result = binary_search(A, target_value)

if result != -1:
    print(f"Phần tử {target_value} được tìm thấy tại vị trí {result}.")
else:
    print(f"Phần tử {target_value} không tồn tại trong dãy.")

Trong ví dụ này, chúng ta sử dụng biến left và right để theo dõi phạm vi tìm kiếm, sau đó sử dụng một vòng lặp while để thực hiện thuật toán tìm kiếm nhị phân. Điều quan trọng là phải duyệt mảng đã sắp xếp giảm dần, nên khi so sánh chúng ta cần điều chỉnh điểm bắt đầu và kết thúc của phạm vi tìm kiếm.

Kết quả chương trình:

Phần tử 12 được tìm thấy tại vị trí 7.

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.

def search_for_name(names, target_name):
    found_names = []  # Danh sách các tên được tìm thấy

    for i, name in enumerate(names):
        if name == target_name:
            found_names.append((i, name))  # Lưu vị trí và tên vào danh sách

    return found_names

# Danh sách tên học sinh
student_names = ["An", "Bình", "Cường", "Hoàn", "Đạt", "Hoàn", "Huy", "Hoàng", "Trang"]

target_name = "Hoàn"

found_results = search_for_name(student_names, target_name)

if len(found_results) > 0:
    print(f"Các học sinh có tên {target_name} được tìm thấy tại các vị trí sau:")
    for result in found_results:
        print(f"Vị trí: {result[0]}, Tên: {result[1]}")
else:
    print(f"Không có học sinh nào có tên {target_name}.")

Tạo một hàm search_for_name để tìm kiếm các tên “Hoàn” trong danh sách tên học sinh. Hàm này duyệt qua danh sách và nếu tìm thấy tên “Hoàn,” nó sẽ lưu vị trí và tên vào danh sách found_names. Sau đó, chúng ta kiểm tra xem danh sách found_names có chứa các kết quả không và hiển thị chúng ra màn hình.

Kết quả chương trình:

Các học sinh có tên Hoàn được tìm thấy tại các vị trí sau:
Vị trí: 3, Tên: Hoàn
Vị trí: 5, Tên: Hoàn

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.

def binary_search(names, target_name):
    left = 0
    right = len(names) - 1
    found_names = []  # Danh sách các tên được tìm thấy

    while left <= right:
        mid = (left + right) // 2  # Tìm phần tử ở giữa danh sách
        mid_name = names[mid]

        if mid_name == target_name:
            found_names.append((mid, mid_name))  # Lưu vị trí và tên vào danh sách
            # Tiếp tục tìm kiếm ở bên trái và bên phải của phần tử này
            left = mid + 1
            right = mid - 1
        elif mid_name < target_name:
            left = mid + 1
        else:
            right = mid - 1

    return found_names

# Danh sách tên học sinh đã sắp xếp theo thứ tự bảng chữ cái
student_names = ["An", "Bình", "Cường", "Hoàn", "Minh", "Minh", "Trang", "Trang", "Trí", "Vân"]

target_name = "Minh"

found_results = binary_search(student_names, target_name)

if len(found_results) > 0:
    print(f"Các học sinh có tên {target_name} được tìm thấy tại các vị trí sau:")
    for result in found_results:
        print(f"Vị trí: {result[0]}, Tên: {result[1]}")
else:
    print(f"Không có học sinh nào có tên {target_name}.")

Thuật toán này bắt đầu tại giữa danh sách và so sánh tên ở vị trí giữa với tên cần tìm. Nếu tìm thấy tên, chúng ta lưu vị trí và tên vào danh sách found_names và tiếp tục tìm kiếm ở cả hai phía của vị trí này. Nếu tên không nằm ở vị trí giữa, chúng ta xác định xem nó ở bên trái hay bên phải và thu hẹp phạm vi tìm kiếm. Sau khi tìm kiếm hoàn thành, chúng ta hiển thị kết quả.

Kết quả chương trình:

Các học sinh có tên Minh được tìm thấy tại các vị trí sau:
Vị trí: 4, Tên: Minh

Xem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

Tường Nguyễn