Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm nhị phân

Trả lời Câu hỏi 2 trang 93 Tin học 11 sách Kết nối tri thức hay, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

1 1,214 07/06/2023

Trang trước

Trang sau

Giải Tin học 11 Bài 19: Bài toán tìm kiếm

Câu hỏi 2 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

Lời giải:

Với dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67}, và sử dụng thuật toán tìm kiếm nhị phân, số lần duyệt cần thực hiện để tìm ra phần tử có giá trị bằng 34 là 2 lần.

Quy trình tìm kiếm nhị phân hoạt động bằng cách so sánh giá trị cần tìm với giá trị ở giữa dãy, và dựa vào kết quả của so sánh này để tiếp tục tìm kiếm trong nửa đầu dãy chứa giá trị cần tìm. Lần đầu tiên duyệt, ta so sánh giá trị cần tìm (34) với giá trị ở giữa dãy, tại vị trí (0 + 11)/2 = 5. Vì giá trị tại vị trí này là 14 và 34 > 14, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, ta so sánh giá trị cần tìm với giá trị ở giữa dãy, tại vị trí (5 + 11)/2 = 8. Vì giá trị tại vị trí này là 31 và 34 > 31, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, giá trị cần tìm là 34 và giá trị tại vị trí này cũng là 34, nên ta đã tìm thấy phần tử cần tìm.

Tổng cộng, số lần duyệt cần thực hiện là 2 lần để tìm ra phần tử có giá trị bằng 34 bằng thuật toán tìm kiếm nhị phân trong dãy A này.

Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

Khởi động trang 89 Tin học 11: Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống

Hoạt động 1 trang 89 Tin học 11: Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán:

Câu hỏi 1 trang 90 Tin học 11: Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.

Câu hỏi 2 trang 90 Tin học 11: Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.

Hoạt động 2 trang 90 Tin học 11: Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.

Câu hỏi 1 trang 91 Tin học 11: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

Câu hỏi 2 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

Câu hỏi 3 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.

Hoạt động 3 trang 91 Tin học 11: Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận

Câu hỏi 1 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?