Cho dãy số {5, 11, 18, 39, 41, 52, 63, 70}. Hãy trình bày diễn biến từng bước của thuật toán

Giải sách bài tập Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

Câu F22 trang 39 SBT Tin học 7: Cho dãy số {5, 11, 18, 39, 41, 52, 63, 70}. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm nhị phân để tìm kiếm x trong dãy.

1) x = 39

2) x = 60

Lời giải:

1) Số phải tìm là x = 39:

Chia đôi lần 1: Phạm vi tìm kiếm là dãy a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy. Vì x = a₄ nên đã tìm thấy x = 39 tại vị trí thứ tư.

2) Số phải tìm là x = 60:

Chia đôi lần 1: Phạm vi tìm kiếm là dãy a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy.

Vì x > a₄ nên có nửa đầu dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi cần tìm tiếp theo là dãy con từ a₅ đến a₈.

Chia đôi lần 2: lấy a₆ là số có vị trí giữa dãy còn lại.

Vì x > a₆ nên nửa đầu dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a₇ đến a₈.

Chia đôi lần 3: lấy a₇ là số có vị trí giữa dãy còn lại.

Vì x < a₇ nên nửa sau dãy (có nền màu xám nhạt) chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con một phần tử là a₇.

Chỉ còn một phần tử, không chia đôi nữa, so sánh thấy x khác a₇. Kết luận: Không tìm thấy.

Lời giải Sách bài tập Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp Cánh diều hay khác:

• Câu F19 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm tuần tự áp dụng cho dãy số ....

• Câu F20 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} ....

• Câu F21 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán sắp xếp nổi bọt áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} ....

Xem thêm các bài giải sách bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác:

• SBT Tin học 7 Bài 15: Thực hành tổng hợp tạo bài trình chiếu

• SBT Tin học 7 Bài 1: Tìm kiếm tuần tự

• SBT Tin học 7 Bài 2: Tìm kiếm nhị phân

• SBT Tin học 7 Bài 3: Sắp xếp chọn

• SBT Tin học 7 Bài 4: Sắp xếp nổi bọt

Xem thêm các tài liệu học tốt lớp 7 hay khác:

• Giải sgk Tin học 7 Cánh diều
• Giải SBT Tin học 7 Cánh diều
• Giải lớp 7 Cánh diều (các môn học)
• Giải lớp 7 Chân trời sáng tạo (các môn học)
• Giải lớp 7 Kết nối tri thức (các môn học)

---