Nội dung bài viết

    Xem thêm

    Giải SBT Tin học 7 - Chân trời sáng tạo trang 62

    Với Giải SBT Tin học 7 trang 62 trong Bài 13: Thuật toán tìm kiếm Tin học lớp 7 Chân trời sáng tạo hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập Tin học 7.

    1 387 09/12/2022
    Trang trước
    Chia sẻ
    Trang sau  

    Giải SBT Tin học 7 - Chân trời sáng tạo trang 62

    Bài 2 trang 62 Sách bài tập Tin học 7: Hãy xác định trong các thao tác dưới đây, thao tác nào là của thuật toán tìm kiếm tuần tự, thao tác nào là của thuật toán tìm kiếm nhị phân bằng cách đánh dấu (✔) vào ô tương ứng.

    Lời giải:

    - Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

    - Thuật toán tìm kiếm nhị phân:

    + Áp dụng với dãy giá trị đã được sắp xếp.

    + Ở mỗi lần lặp, thực hiện:

    Bước 1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét.

    Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

    Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau.

    Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, không thì quay lại bước 1.

    ⇒ Bảng kết quả như sau:

    Bài 3 trang 62 Sách bài tập Tin học 7: Cho dãy số: 47, 35, 36, 11, 36, 46, 36, 63, 36, 18, 24. Để tìm số 36 trong dãy số này bằng thuật toán tìm kiếm tuần tự, ta cần thực hiện bao nhiêu lần lặp? 

    A. 3 lần. B. 5 lần. C. 7 lần. D. 9 lần. 

    Lời giải:

    Đáp án đúng là: A

    Số 36 đầu tiền nằm ở vị trí thứ 3 trong dãy nên khi tìm số 36 trong dãy số này bằng thuật toán tìm kiếm tuần tự, ta cần thực hiện 3 lần lặp.

    Bài 4 trang 62 Sách bài tập Tin học 7: Theo em, thuật toán tìm kiếm nào trong 2 thuật toán đã học là phù hợp nhất để tìm một số trong dãy số 14, 17, 21, 25, 30, 52, 66? Vì sao em không chọn thuật toán còn lại? 

    Hãy mô phỏng thuật toán phù hợp nhất đã chọn để tìm số 30 trong dãy số trên bằng cách điền thông tin mỗi lần lặp vào bảng dưới đây.

    Lần lặp

    Số của dãy được kiểm tra

    Đúng số cần tìm

    Đã kiểm tra hết số

    1

    …

    …

    …

    2

    …

    …

    …

    …

    …

    …

    …

    Lời giải:

    Sử dụng thuật toán tìm kiếm nhị phân là phù hợp nhất để tìm một số trong dãy số này vì đây là dãy số sắp xếp tăng dần, số lần lặp phải thực hiện ít hơn hẳn khi sử dụng thuật toán tìm kiếm tuần tự (ta sẽ thấy rõ khi dãy có nhiều phần tử và phần tử này cần tìm cách xa phần tử đầu tiên).

    Lần lặp

    Số của dãy được kiểm tra

    Đúng số cần tìm

    Đã kiểm tra hết số

    1

    25

    Sai

    Sai

    2

    52

    Sai

    Sai

    3

    30

    Đúng

    		  

    Bài 5 trang 62 Sách bài tập Tin học 7: Bạn em có một bộ 20 thẻ số, mỗi thẻ ghi một số khác nhau, được đặt úp trên bàn theo thứ tự giá trị các số tăng dần từ trái sang phải. Bạn đố em lật tìm được đúng một số trong 20 thẻ số đó chỉ với tối đa 5 lần lật. Em có thực hiện được không? Vì sao?

    Lời giải:

    Thực hiện được, vì: Áp dụng thuật toán tìm kiếm nhị phân.

    Theo công thức phần nguyên, ta xác định và lật thẻ ở giữa như sau (giả định trường hợp xấu nhất là lần lật cuối cùng mới đúng số cần tìm):

    - Lần 1: lật 1 thẻ trong 20 thẻ, ta lật thẻ thứ 10.

    - Lần 2: lật 1 thẻ trong 9 thẻ bên trái hoặc trong 10 thẻ bên phải thẻ thứ 10, ta lật thẻ thứ 5 hoặc lật thẻ thứ 15.

    Cứ tiếp tục chọn và lật như vậy thì đến lần 5, sẽ chỉ còn 1 số để lật và chắc chắn tìm được một số theo yêu cầu.

    Xem thêm lời giải sách bài tập Tin học lớp 7 Chân trời sáng tạo hay, chi tiết khác:

    Giải SBT Tin học 7 trang 61

    Tham khảo các loạt bài Tin học 7 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 387 09/12/2022
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: