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.
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).
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.
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 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 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
Xem thêm các chương trình khác:
- Soạn văn lớp 11 Cánh diều (hay nhất)
- Văn mẫu lớp 11 - Cánh diều
- Tóm tắt tác phẩm Ngữ văn 11 – Cánh diều
- Tác giả tác phẩm Ngữ văn 11 - Cánh diều
- Giải SBT Ngữ văn 11 – Cánh diều
- Bố cục tác phẩm Ngữ văn 11 – Cánh diều
- Giải Chuyên đề học tập Ngữ văn 11 – Cánh diều
- Nội dung chính tác phẩm Ngữ văn lớp 11 – Cánh diều
- Soạn văn 11 Cánh diều (ngắn nhất)
- Giải sgk Toán 11 – Cánh diều
- Giải Chuyên đề học tập Toán 11 – Cánh diều
- Lý thuyết Toán 11 - Cánh diều
- Giải sbt Toán 11 – Cánh diều
- Giải sgk Tiếng Anh 11 – ilearn Smart World
- Giải sbt Tiếng Anh 11 - ilearn Smart World
- Trọn bộ Từ vựng Tiếng Anh 11 ilearn Smart World đầy đủ nhất
- Giải sgk Vật lí 11 – Cánh diều
- Lý thuyết Vật lí 11 – Cánh diều
- Giải sbt Vật lí 11 – Cánh diều
- Giải Chuyên đề học tập Vật lí 11 – Cánh diều
- Giải sgk Hóa học 11 – Cánh diều
- Giải Chuyên đề học tập Hóa học 11 – Cánh diều
- Lý thuyết Hóa 11 - Cánh diều
- Giải sbt Hóa học 11 – Cánh diều
- Giải sgk Sinh học 11 – Cánh diều
- Lý thuyết Sinh học 11 – Cánh diều
- Giải Chuyên đề học tập Sinh học 11 – Cánh diều
- Giải sbt Sinh học 11 – Cánh diều
- Giải sgk Giáo dục Kinh tế và Pháp luật 11 – Cánh diều
- Giải Chuyên đề học tập Kinh tế pháp luật 11 – Cánh diều
- Lý thuyết Kinh tế pháp luật 11 – Cánh diều
- Giải sbt Kinh tế pháp luật 11 – Cánh diều
- Giải sgk Lịch sử 11 – Cánh diều
- Giải Chuyên đề học tập Lịch sử 11 – Cánh diều
- Lý thuyết Lịch sử 11 - Cánh diều
- Giải sbt Lịch sử 11 – Cánh diều
- Giải sgk Địa lí 11 – Cánh diều
- Giải Chuyên đề học tập Địa lí 11 – Cánh diều
- Lý thuyết Địa lí 11 - Cánh diều
- Giải sbt Địa lí 11 – Cánh diều
- Giải sgk Công nghệ 11 – Cánh diều
- Lý thuyết Công nghệ 11 - Cánh diều
- Giải sbt Công nghệ 11 – Cánh diều
- Giải sgk Giáo dục quốc phòng an ninh 11 – Cánh diều
- Lý thuyết Giáo dục quốc phòng 11 – Cánh diều
- Giải sbt Giáo dục quốc phòng 11 – Cánh diều
- Giải sgk Hoạt động trải nghiệm 11 – Cánh diều