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 bài tập trang 65 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

Câu 19.1

Khi nào thì thuật toán tìm kiếm tuần tự trên một danh sách tốn nhiều thời gian nhất?

Trả lời:

Thuật toán tìm kiếm tuần tự trên một danh sách tốn nhiều thời gian nhất khi phần tử cần tìm là không tồn tại trong danh sách. Trong trường hợp này, thuật toán sẽ phải duyệt qua tất cả các phần tử của danh sách trước khi kết luận rằng phần tử không tồn tại.

Câu 19.2

Có ý kiến cho rằng: Thiết kế các thuật toán tìm kiếm phụ thuộc rất nhiều vào cấu trúc dữ liệu của miền cần tìm kiếm. Điều đó đúng hay sai?

Trả lời:

Điều này đúng. Thiết kế các thuật toán tìm kiếm thực sự phụ thuộc vào cấu trúc dữ liệu của miền cần tìm kiếm. Không có một thuật toán tìm kiếm duy nhất phù hợp cho tất cả các loại dữ liệu và cấu trúc dữ liệu khác nhau.

Câu 19.3

Cho ma trận số A bậc m x n. Viết chương trình thực hiện việc tìm kiếm tuần tự trên ma trận A. Giả sử K là giá trị cần tìm kiếm. Nếu tìm thấy sẽ trả về cặp chỉ số phần tử (i, j) có giá trị K, tức là A[i][j] = K, nếu không thấy sẽ trả về (-1,-1).

Trả lời:

def LinearSearchMatrix(A,K):
    n = len(A[0])
    for i in range (n):
        for j in range (n):
            if A[i][j] == K:
                return (i, j)
    return (-1,-1)

Câu 19.4

Em được giao nhiệm vụ tìm hiểu trong năm vừa qua ngày nào lạnh nhất. Hỏi miền dữ liệu tìm kiếm của bài toán này là gì?

Trả lời:

Miền dữ liệu tìm kiếm của bài toán này là: Dãy số liệu nhiệt độ trung bình trong các ngày của năm qua. Dựa vào dữ liệu nhiệt độ này, có thể thực hiện tìm kiếm để xác định ngày có nhiệt độ trung bình thấp nhất, và đó sẽ là ngày lạnh nhất trong năm đó.

Câu 19.5

Giả sử dữ liệu tên và điểm thi môn Tin học của các bạn lớp em được cho dưới dạng sau, ví dụ:

[(“Hà“, 7.5), (“Bình”, 8), (“Quang”, 9.2), (“An”, 10)]

Viết chương trình thực hiện các việc sau:

– Nhập một điểm số từ bàn phim. Sau đó tìm kiếm xem trong lớp có bạn nào có điểm thi bằng điềm đã nhập không. Nếu có thì chỉ cần thông báo một bạn, ví dụ: Tìm thấy bạn An.

– Nếu không thấy thì thông báo: Không tìm thấy.

Trả lời:

A = [("Hà", 7.5), ("Binh", 8), ("Quang", 9.2), ("An", 10)]

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

diem = float(input("Nhập một điểm số: "))
k = Timkiem(A, diem)
if k >= 0:
    print("Tìm thấy bạn", A[k][0])
else:
    print("Không tìm thấy")

Câu 19.6

Viết thuật toán và chương trình tìm kiếm tuần tự mở rộng như sau: Cho trước dãy A và giá trị K. Cần tìm tất cả các phần tử trong A có giá trị bằng K. Kết quả trả về là một list chỉ số của các phần tử bằng K. Ngược lại, nếu không tìm thấy thì trả về list rỗng.

Ví dụ A: = [1,0,3,2,5,1,8], K = 1 thì kết quả trả về là list [0, 5].

Trả lời:

def ExtLinearSearch (A,K):
    kq = []
    for i in range(len(A)):
        if A[i] == K:
            kq.append(i)
    return kq

Câu 19.7

Với thuật toán tìm kiếm nhị phân, khi nào thì tìm kiếm nhanh nhất, cần ít phép so sánh nhất?

Trả lời:

Thuật toán tìm kiếm nhị phân là nhanh nhất và yêu cầu ít phép so sánh nhất khi giá trị phần tử có chỉ số mid bằng K, khi đó chỉ cần 1 phép so sánh.

Câu 19.8

Với thuật toán tìm kiếm nhị phân, khi nào thì việc tìm kiếm sẽ chậm nhất, cần nhiều phép so sánh nhất?

Trả lời:

Thuật toán tìm kiếm nhị phân, khi việc tìm kiếm sẽ chậm nhất, cần nhiều phép so sánh nhất là khi phần tử cần tìm là không tồn tại trong danh sách. Trong trường hợp này, thuật toán sẽ phải thực hiện tất cả các phép so sánh để đến cuối danh sách mà không tìm thấy phần tử cần tìm.

Câu 19.9

Viết chương trình cải tiến thuật toán tìm kiếm nhị phân trong sách giáo khoa (sách giáo khoa) đề việc tìm kiếm nhanh hơn nếu K nằm ngoài vùng giá trị của dãy A.

Trả lời:

def BinarySearch(A, K):
    if K < A[0] or K > A[len(A) - 1]:  
        return -1
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] < K:  
            left = mid + 1
        else:
            right = mid - 1
    return -1