Nội dung bài viết

    Xem thêm

    Xét bài toán: Một hàng dọc gồm n bạn học sinh xếp theo thứ tự từ thấp đến cao, bạn thứ i

    Trả lời Câu Fcs29 trang 55 SBT Tin học 11 sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

    1 216 18/10/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải SBT Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm

    Câu Fcs29 trang 55 SBT Tin học 11: Xét bài toán: Một hàng dọc gồm n bạn học sinh xếp theo thứ tự từ thấp đến cao, bạn thứ i (0 <i≤n − 1) có chiều cao là h (cm). Em hãy viết chương trình, với độ phức tạp O(nlog,n), sử dụng thuật toán tìm kiếm nhị phân để tính số cách chọn một cặp học sinh trong hàng sao cho chênh lệch chiều cao của hai bạn ấy bằng đúng giá trị d (cm) cho trước.

    Dữ liệu: Nhập từ thiết bị vào chuẩn:

    • Dòng đầu tiên chứa một dãy số nguyên dương hạ, h,,,h với đảm bảo h<h,,, (0 ≤i≤n- 1).

    • Dòng thứ hai chứa một số nguyên dương d.

    Kết quả: Hiển thị ở thiết bị ra chuẩn một số nguyên là số lượng cặp chỉ số (i, j) để h − h = d (0<i<j<n-1).

    Xét bài toán Một hàng dọc gồm n bạn học sinh xếp theo thứ tự

    Lời giải:

    Với mỗi chỉ số j, tồn tại tối đa một chỉ số i để h[j] – h[i] = d. Điều kiện h[j] - h[i] = d tương đương với h[i] = h[j] – d. Đặt h[j] – d = x, em có thê quy về bài toán tìm kiếm giá trị x trên dãy h. Sử dụng một biến kiểu boolean để ghi nhận kết quả tìm kiếm cho mỗi chỉ số j, em có thể tính tổng số lượng chỉ số j mà tồn tại i thoả mãn h[j] – h[i] = d, cũng chính là số cặp cần tìm.

    Xét bài toán Một hàng dọc gồm n bạn học sinh xếp theo thứ tự

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

    Câu Fcs26 trang 55 SBT Tin học 11: Theo em, tại sao em không thể áp dụng thuật toán tìm kiếm nhị phân trên một dãy chưa được sắp xếp theo thứ tự?...

    Câu Fcs27 trang 55 SBT Tin học 11: Em hãy chỉ ra một trường hợp mà thuật toán tìm kiếm tuần tự cho ra kết quả nhanh hơn thuật toán tìm kiếm nhị phân....

    Câu Fcs28 trang 55 SBT Tin học 11: Trong tiết Vật lí, An thực hành đo hiệu điện thế trong đoạn mạch song song....

    Câu Fcs29 trang 55 SBT Tin học 11: Xét bài toán: Một hàng dọc gồm n bạn học sinh xếp theo thứ tự từ thấp đến cao, bạn thứ i (0 <i≤n − 1)...

    Câu Fcs30 trang 56 SBT Tin học 11: Bản đồ gene...

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

    Bài 8: Lập trình một số thuật toán sắp xếp

    Bài 9: Lập trình sắp xếp nhanh

    Bài 10, 11, 12, 13, 14: Thiết kế chương trình từ trên xuống và phương pháp mô đun hoá. Thực hành thiết kế và lập trình theo mô đun. Thực hành về thư viện các hàm tự định nghĩa

    Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

    Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh trong phần mềm GIMP

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

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

    Xem thêm
    1 216 18/10/2023
    Trang trước
    Chia sẻ
    Trang sau  

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