Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là chia để trị không?

Xem lời giải

Câu hỏi trong đề: Giải SGK Chuyên đề Tin học 11 Bài 6. Ý tưởng và kĩ thuật chia để trị !!

Giao bài

Quảng cáo

Trả lời:

Giải bởi Vietjack

Không, phương án không đệ quy của thuật toán tìm kiếm nhị phân không phải là chia để trị.

Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một phần tử trong một mảng đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần) bằng cách chia mảng thành hai phần và so sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, ta tìm kiếm trong nửa đầu tiên của mảng. Ngược lại, nếu giá trị cần tìm lớn hơn phần tử ở giữa, ta tìm kiếm trong nửa sau của mảng. Tiếp tục lặp lại quá trình này cho đến khi tìm thấy phần tử cần tìm hoặc không tìm thấy phần tử đó trong mảng.

Phương án chia để trị là một kỹ thuật giải quyết bài toán bằng cách chia bài toán thành các bài toán con, giải quyết các bài toán con đó đệ quy và kết hợp kết quả của các bài toán con để giải quyết bài toán ban đầu. Phương án chia để trị thường được sử dụng cho các bài toán mà có thể chia thành các bài toán con độc lập với nhau, ví dụ như thuật toán sắp xếp chia để trị Merge Sort.

Đang tải chế độ Học...

Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay

ĐẶC QUYỀN VIP

Đăng ký VIP để học và luyện thi không giới hạn

Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.

Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
Đăng ký ngay

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right

Xem đáp án

Lời giải

Khi left = right, nghĩa là chỉ còn một phần tử để xét. Ta so sánh giá trị của phần tử đó với giá trị cần tìm x.

Nếu phần tử đó bằng x thì ta trả về vị trí của phần tử đó (left hoặc right).

Nếu phần tử đó khác x thì ta trả về giá trị -1 để thể hiện không tìm thấy phần tử x trong dãy.

Câu 2

Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau

Hãy thiết kế lại thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.

Xem đáp án

Lời giải

Thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n có thể được thiết kế bằng kĩ thuật chia để trị theo các bước sau:

1. Nếu n bằng 0 hoặc 1, trả về n.

2. Đặt a bằng căn bậc hai của n.

3. Nếu a bằng n, trả về a.

4. Ngược lại, tìm số nguyên lớn nhất không vượt quá căn bậc hai của n/2 và số nguyên lớn nhất không vượt quá căn bậc hai của n - 1. So sánh hai số này và trả về số lớn hơn.

Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước, người (ảnh 2)

Câu 3