Với giải Câu F22 trang 39 SBT Tin học 7 Cánh diều chi tiết trong Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Tin học 7. Mời các bạn đón xem:
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
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
Trả lờ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 a1 đến a8. Lấy a4 là số có vị trí giữa dãy. Vì x = a4 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 a1 đến a8. Lấy a4 là số có vị trí giữa dãy.
Vì x > a4 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ừ a5 đến a8.
Chia đôi lần 2: lấy a6 là số có vị trí giữa dãy còn lại.
Vì x > a6 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ừ a7 đến a8.
Chia đôi lần 3: lấy a7 là số có vị trí giữa dãy còn lại.
Vì x < a7 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à a7.
Chỉ còn một phần tử, không chia đôi nữa, so sánh thấy x khác a7. Kết luận: Không tìm thấy.
Xem thêm các bài giải vở bài tập Tin học 7 Cánh diều hay, chi tiết khác:
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
2021 © All Rights Reserved.
