Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài học.
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào tìm nhanh hơn tìm kiếm tuần tự không?
Câu trả lời:
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, chúng ta sẽ chia đôi dãy số để tìm kiếm nhanh hơn.
Câu hỏi: Có 8 thẻ, mỗi thẻ có ghi một số nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X chẳng hạn. Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho răng chỉ cần không quá ba lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?
Câu trả lời:
Em đồng ý với ý kiến của bạn Thanh An vì chúng ta chỉ cần chia đôi dần dãy số đã sắp thứ tự và lần lượt tìm kiếm trong phạm vi phù hợp để tìm ra kết quả mà chúng ta mong muốn thì chỉ cần 3 lần là có thể tìm ra kết quả.
Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên.
Gợi ý: Có thể trình bày thông tin mô tả dưới dạng bảng như trong bài học.
Câu trả lời:
Các bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên:
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
|
Xuất phát |
5 |
11 |
18 |
39 |
41 |
52 |
63 |
70 |
Bước 1 |
41 |
52 |
63 |
70 |
||||
Bước 2 |
41 |
52 |
||||||
Bước 3 |
Em hãy mô tả cách tra cứu, tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không?
Câu trả lời:
Cách tra cứu, tìm giải nghĩa một từ trong từ điển:
Cách tìm trên có thể gọi là áp dụng thuật toán tìm kiếm nhị phân.
Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.
Câu 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.
Câu trả lời:
Câu 1. Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:
Câu 2. Không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng thuật toán tìm kiếm nhị phân.