Trang chủ Lớp 11 Tin học lớp 11 SGK Tin học 11 - Cánh diều (?) Câu hỏi mục 4 NV1 Bài 7 (trang 117, 118, 119)...

(?) Câu hỏi mục 4 NV1 Bài 7 (trang 117, 118, 119) Tin học 11: Em hãy thực hiện các yêu cầu sau: Viết mã giả cho thuật toán tìm kiếm nhị phân

Giải (?) Câu hỏi mục 4 NV1 Bài 7. Lập trình giải bài toán tìm kiếm (trang 117, 118, 119) – SGK Tin học 11 Cánh diều. Tham khảo: Dựa vào kiến thức đã học.

Câu hỏi/Đề bài:

Em hãy thực hiện các yêu cầu sau:

1. Viết mã giả cho thuật toán tìm kiếm nhị phân.

2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.

3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Hướng dẫn:

Dựa vào kiến thức đã học.

Lời giải:

1) Bắt đầu: Phạm vi tìm kiếm là dãy ban đầu

Lặp khi Vẫn còn Phạm vi tìm kiếm:

Xác định phần tử am giữa Phạm vi tìm kiếm

Nếu x=am:

Thông báo tìm thấy x ở vị trí m và kết thúc

Ngược lại:

Loại bỏ nửa dãy chắc chắn không chứa x

Phạm vi tìm kiếm là nửa dãy còn lại

Hết nhánh

Hết lặp

Thông báo không tìm thấy x và kết thúc.

2) Số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân:

Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2 mũ k. Kết thúc khi 2 mũ k sấp xỉ n.

3) Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân O(n).