Câu hỏi mở đầu trang 89

Đề bài: 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 có chắc chắn tìm được thẻ số K không? Có. Vì An lật lần lượt tất cả các thẻ nên nếu thẻ số K có trong bộ, An chắc chắn tìm được.
• Cách nhanh hơn: Vì các thẻ đã được xếp theo thứ tự tăng dần, ta có thể lật thẻ ở giữa trước, so sánh giá trị với K:
  • Nếu bằng K → tìm thấy.
  • Nếu K nhỏ hơn → tiếp tục tìm ở nửa bên trái.
  • Nếu K lớn hơn → tiếp tục tìm ở nửa bên phải.

→ Cách này sẽ nhanh hơn nhiều so với lật lần lượt từng thẻ.

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

Hoạt động 1 trang 89

Đề bài: 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. Tìm hình ảnh các cây hoa hồng đẹp trên Internet.

Bài toán 2. Tìm tệp văn bản có tên bai-hoc-1.docx trên máy tính.

Bài toán 3. Tìm 5 học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.

Lời giải:

→ Ba bài toán có miền dữ liệu khác nhau và tiêu chí tìm kiếm khác nhau, nên thuật toán tìm kiếm cũng sẽ khác nhau.

Câu hỏi củng cố mục 1 trang 90

Đề bà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ố.

Lời giải:

• Miền dữ liệu: bản đồ số gồm các con đường, ngã ba, ngã tư, các địa điểm,…
• Nghiệm có thể: một hoặc nhiều đường đi từ nhà đến trường (đường ngắn nhất, ít tắc nhất, đường quen thuộc,…).

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:

• Miền dữ liệu: danh sách toàn bộ các trường trung học phổ thông trong quận (huyện) hoặc thành phố.
• Nghiệm có thể: danh sách các trường có địa chỉ thuộc quận (huyện) em đang cư trú, kèm tên và địa chỉ cụ thể.

2. Tìm kiếm tuần tự

Hoạt động 2 trang 90

Đề bài: 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.

Lời giải:

Các bước tìm kiếm tuần tự:

→ Phần tử cần tìm có chỉ số i = 5.

Thuật toán tìm kiếm tuần tự (tổng quát): Duyệt lần lượt các phần tử của dãy từ đầu đến cuối. Nếu tìm thấy phần tử bằng K thì trả về chỉ số; nếu duyệt hết dãy mà không thấy thì trả về –1.

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

Câu hỏi củng cố mục 2 trang 91

Đề bài:

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:

Ta duyệt lần lượt từ đầu dãy:

→ Đến chỉ số i = 7 mới tìm thấy 47. Vậy cần 8 lần duyệt.

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:

Khi phần tử cần tìm nằm ngay ở đầu dãy (chỉ số 0) → chỉ cần 1 bước đã tìm thấy.

3. Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.

Lời giải:

Khi phần tử cần tìm nằm ở cuối dãy hoặc không có trong dãy → cần duyệt hết n bước (n là số phần tử).

Ví dụ: A = [1, 2, 3, 4, 5], K = 5 → cần duyệt cả 5 phần tử mới tìm thấy. Hoặc K = 10 (không có trong dãy) → cũng cần duyệt cả 5 phần tử rồi trả về –1.

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

Hoạt động 3 trang 91

Đề bài: 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.

Lời giải:

Ý tưởng chính:

• Dãy đã sắp xếp tăng dần → khi so sánh K với một phần tử ở giữa dãy, ta có thể loại bỏ ngay một nửa dãy không cần xét.
• Sau mỗi bước, phạm vi tìm kiếm giảm đi một nửa, nên số bước cần thực hiện ít hơn nhiều so với tìm kiếm tuần tự.

Các bước của thuật toán tìm kiếm nhị phân:

• Đặt hai chỉ số left = 0 và right = n – 1 (n là số phần tử của dãy).
• Tính mid = (left + right) // 2 (chỉ số phần tử ở giữa).
• So sánh K với A[mid]:
  • Nếu K = A[mid] → tìm thấy, trả về chỉ số mid.
  • Nếu K < A[mid] → tìm tiếp ở nửa bên trái, cập nhật right = mid – 1.
  • Nếu K > A[mid] → tìm tiếp ở nửa bên phải, cập nhật left = mid + 1.
• Lặp lại đến khi tìm thấy hoặc khi left > right (phạm vi rỗng → không có trong dãy).

Thuật toán bằng Python:

def BinarySearch(A, K):
    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

Câu hỏi củng cố mục 3 trang 93

Đề bài: Cho dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67].

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?

Lời giải:

Dãy A có 12 phần tử, chỉ số từ 0 đến 11. Số 34 nằm ở chỉ số 10.

→ Cần duyệt lần lượt từ chỉ số 0 đến chỉ số 10, tức là 11 phần tử.

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?

Lời giải:

Ban đầu: left = 0, right = 11.

→ Chỉ cần duyệt 3 phần tử là tìm được (so với 11 phần tử của tìm kiếm tuần tự).

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:

Đây chính là cách tìm kiếm nhị phân. Với dãy A có 12 phần tử, sau mỗi lần lật, phạm vi tìm kiếm giảm đi một nửa:

• Lần 1: còn 12 thẻ → chia đôi còn 6.
• Lần 2: còn 6 thẻ → chia đôi còn 3.
• Lần 3: còn 3 thẻ → chia đôi còn 1.
• Lần 4: còn 1 thẻ → kiểm tra là hết.

→ Số lần nhiều nhất Minh phải lật là 4 lần.

Luyện tập

Luyện tập trang 93

Đề bài:

1. Em hãy 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, biết dãy đó có nhiều phần tử bằng giá trị cần tìm.

Lời giải:

Ý tưởng: thay vì trả về ngay khi tìm thấy, ta lưu lại chỉ số vào một danh sách và tiếp tục duyệt đến hết dãy.

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

Giải thích:

• Tạo danh sách rỗng ket_qua để lưu các chỉ số tìm được.
• Duyệt hết dãy, mỗi khi gặp phần tử bằng K thì thêm chỉ số vào ket_qua.
• Trả về ket_qua (nếu không tìm thấy phần tử nào, danh sách sẽ rỗng).

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.

Lời giải:

Ý tưởng: dãy giảm dần nên các phần tử lớn nằm bên trái, các phần tử nhỏ nằm bên phải. Cách xử lý ngược lại so với dãy tăng dần:

• Nếu K < A[mid] → K nhỏ hơn nên nằm bên phải, cập nhật left = mid + 1.
• Nếu K > A[mid] → K lớn hơn nên nằm bên trái, cập nhật right = mid – 1.

def BinarySearchGiam(A, K):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] < K:
            right = mid - 1     # K lớn hơn → tìm nửa bên trái
        else:
            left = mid + 1      # K nhỏ hơn → tìm nửa bên phải
    return -1

Vận dụng

Vận dụng trang 93

Đề bài:

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.

Lời giải:

Vì có thể có nhiều học sinh cùng tên Hoàn, ta duyệt toàn bộ danh sách và lưu tất cả các chỉ số tìm được.

def TimHoan(A):
    ket_qua = []
    for i in range(len(A)):
        if A[i] == "Hoàn":
            ket_qua.append(i)
    return ket_qua

Giải thích:

• Duyệt lần lượt từng học sinh trong danh sách.
• Nếu tên bằng “Hoàn” thì thêm chỉ số vào danh sách kết quả.
• Trả về danh sách các chỉ số của các bạn tên Hoàn.

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.

Lời giải:

Vì danh sách đã sắp xếp theo bảng chữ cái, ta có thể dùng tìm kiếm nhị phân. Trong Python, có thể so sánh trực tiếp các chuỗi bằng các phép ==, <, > (thứ tự chuỗi theo bảng chữ cái).

def TimMinh(A):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == "Minh":
            return mid
        elif A[mid] < "Minh":
            left = mid + 1
        else:
            right = mid - 1
    return -1

Giải thích:

• Thuật toán giống với BinarySearch cho dãy tăng dần, chỉ khác là so sánh chuỗi thay vì số.
• Nếu tìm thấy, hàm trả về chỉ số của bạn tên Minh; nếu không thấy, trả về –1.

Lưu ý: Nếu trong lớp có nhiều bạn cùng tên Minh, hàm này chỉ trả về chỉ số một trong số đó. Muốn tìm tất cả, sau khi tìm thấy một vị trí, ta có thể kiểm tra tiếp các phần tử bên cạnh (vì các tên giống nhau sẽ nằm liền nhau trong dãy đã sắp xếp).

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa