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?
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?
Giải Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị - Kết nối tri thức
Vận dụng 1 trang 32 Chuyên đề Tin học 11: 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?
Lời giải:
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.
Lời giải bài tập Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị hay, chi tiết khác:
Khởi động trang 28 Chuyên đề Tin học 11: Trò chơi tìm bi giả ....
Câu hỏi 2 trang 30 Chuyên đề Tin học 11: Mô tả bước "kết hợp" của bài toán 9 viên bi trên ....