Với giải Bài 4 Tin học lớp 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:

Giải bài tập Tin học lớp 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

Bài 4. Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3.

a. Tìm x = 5.

b. Tìm x = 6.

Hướng dẫn

a. Tìm x = 5.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₁₀. Lấy a₅ là số có vị trí giữa dãy; Vì x < a₅ nên nửa đầu dãy chắc chắn không chứa x = 5, tiếp theo 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 từ a₆ đến a₁₀.

Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₆ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x = a₈ nên kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ tám.

b. Tìm x = 6.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₁₀. Lấy a₅ là số có vị trí giữa dãy; Vì x < a₅ nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo 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 từ a₆ đến a₁₀.

Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₆ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x > a₈ nên nửa sau dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa đầu của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a₅ đến a₇.

Chia đôi lần 3: Phạm vi tìm kiếm là dãy từ a₅ đến a₇. Lấy a₆ là số có vị trí giữa dãy. Vì  x < a₆ nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa sau của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là a₇.

Phạm vi tìm kiếm chỉ còn một số nhưng không tìm thấy x. Kết thúc thuật toán với kết quả: Không có x trong dãy.

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

Bài 1. Cho dãy số ban đầu như sau:...

Bài 2. Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp chọn để sắp xếp dãy số theo chiều không tăng....

Bài 3. Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng....