Giải SBT Tin học 11 KNTT Bài 20. Thực hành bài toán tìm kiếm có đáp án

Đáp án đúng là: B. Thuật toán tìm kiếm nhị phân được thực hiện như sau:

Bước 1: Kiểm tra số chính giữa là số “12”, lớn hơn 10 nên số cần tìm nằm ở nửa trái của dãy. Dãy cần tìm kiếm tiếp là [1, 3, 10].

Bước 2: Kiểm tra số chính giữa của dãy thu gọn là số “3”, nhỏ hơn 10 nên số cần tìm nằm ở nửa phải của dãy. Dãy cần tìm kiếm tiếp là [10].

Bước 3: Kiểm tra số chính giữa của dãy thu gọn là số “10”, bằng 10. Kết luận tìm ra số cần tìm và kết thúc chương trình.

Như vậy, có 3 phép so sánh cần thực hiện.

Chúng ta có thể áp dụng ý tưởng của thuật toán tìm kiếm tuần tự để tìm ra số lớn nhất trong dãy số. Chúng ta lần lượt duyệt từng phần tử trong dãy số và so sánh phần tử này với phần tử lớn nhất hiện tại (phần tử lớn nhất trong các phần tử đã duyệt). Chương trình tìm kiếm phần tử lớn nhất có thể được viết như sau:

Để giải bài toán này, trước hết chúng ta sử dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí mà phần tử cần tìm xuất hiện trong dãy (vị trí này có thể là vị trí đầu tiên, thứ hai hoặc vị trí cuối cùng mà phần tử cần tìm xuất hiện). Sau đó, chúng ta so sánh phần tử vừa tìm được với các phần tử ngay trước nó để tìm ra vị trí đầu tiên phần tử cần tìm xuất hiện.