Chương 7 – Thuật toán tìm kiếm(Tiếp**)

Thực hiện được các thao tác tìm kiếm dữ liệu một cách hiệu quả

7. Bài tập

Bài 1: Tìm số điện thoại

Cho một danh sách các số điện thoại di động của nhiều nhà mạng khác nhau. Hãy viết một hàm để hiển thị các số di động thuộc nhà mạng Viettel.

Bài 2: Game đoán số

Hãy xây dựng một ứng dụng game đoán số được mô tả như sau: Người chơi được phép bí mật chọn trước một số nằm trong khoảng từ 1 đến 100. Nhiệm vụ của ứng dụng sẽ là đoán xem người chơi đã chọn số nào trong khoảng đó.

Ứng dụng thực hiện việc này bằng cách hỏi người chơi và người chơi sẽ phải trả lời trung thực.

Câu hỏi sẽ có dạng: “Có phải số bạn chọn là X hay không? Nếu không phải thì hãy cho tôi biết là nó lớn hơn hay nhỏ hơn X?

Người chơi sẽ phải trả lời 1 trong 3 trường hợp:

• Số tôi chọn chính là X: trò chơi kết thúc
• Số tôi chọn nhỏ hơn X: ứng dụng tiếp tục hỏi câu tiếp theo
• Số tôi chọn lớn hơn X: ứng dụng tiếp tục hỏi câu tiếp theo

Gợi ý: Bản chất của trò chơi này đó là triển khai thuật toán tìm kiếm nhị phân.

Bài 3: Triển khai thuật toán tìm kiếm nhị phân bằng cách sử dụng hàm đệ quy

Hãy viết một hàm đệ quy để triển khai tìm kiếm nhị phân mà không sử dụng vòng lặp.

Gợi ý: Xem lại nội dung về Hàm đệ quy trong Chương 6.

8. Bài kiểm tra

Câu 1: Độ phức tạp tốt nhất của thuật toán tìm kiếm tuyến tính là?

1. O(n)
   1. O(logn)
   1. O(nlogn)
   1. O(1)

Câu 2: Độ phức tạp tệ nhất của thuật toán tìm kiếm nhị phân là gì?

1. O(logn)
   1. O(nlogn)
   1. O(1)
   1. O(n)

Câu 3: Với một mảng số nguyên đã được sắp xếp theo trật tự giảm dần thì thuật toán tìm kiếm nào có hiệu quả nhất?

1. Thuật toán tìm kiếm tuyến tính
   1. Thuật toán tìm kiếm nhị phân

Câu 4: Thuật toán tìm kiếm nào là tốt nhất cho một danh sách lớn

1. Tìm kiếm tuần tự
   1. Sử dụng vòng lặp for-in
   1. Tìm kiếm nhị phân

Câu 5: Trung bình, một thuật toán tìm kiếm tuần tự sẽ mất N / 2 số lần so sánh cho một danh sách kích thước N.

1. Đúng
2. Sai

Câu 6: Điều sau đây được là đúng đối với thuật toán tìm kiếm nhị phân?

1. Có thể áp dụng với dữ liệu đã được sắp xếp theo trật tự tăng dần
   1. Có thể áp dụng với dữ liệu đã được sắp xếp theo trật tự giảm dần
   1. Có thể áp dụng với dữ liệu chưa được sắp xếp

Đáp án: Câu 1: d, Câu 2: a, Câu 3: b, Câu 4: c, Câu 5: a, Câu 6: a và b

9. Tổng kết

• Tìm kiếm dữ liệu là một thao tác được thực hiện thường xuyên trong các ứng dụng
• Thuật toán tìm kiếm tuyến tính hoạt động dựa trên cơ chế duyệt qua lần lượt tất cả các phần tử
• Thuật toán tìm kiếm nhị phân hoạt động dựa trên cơ chế chia nhỏ tập dữ liệu
• Thuật toán tìm kiếm nhị phân chỉ có thể thực hiện được trên tập dữ liệu đã được sắp xếp
• Độ phức tạp của thuật toán là một đại lượng để đo tính hiệu quả của một thuật toán
• Độ phức tạp của thuật toán tìm kiếm nhị phân là nhỏ hơn so với độ phức tạp của thuật toán tìm kiếm tuyến tính