Câu hỏi:
25/09/2023 606
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.
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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Với dãy a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] và khoá r = 1, thuật toán tìm kiếm tuần tự chỉ mất một lượt so sánh để tìm ra x trong dãy a, còn thuật toán tìm kiếm nhị phân phải mất ba lần chia đôi dãy mới thu hẹp được phạm vi tìm kiếm về phần tử 1 ở vị trí ngoài cùng bên trái của a.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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ự?
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ự?
Xem đáp án »
11/07/2024
679
Câu 2:
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ự 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).
Xem đáp án »
11/07/2024
445
Câu 3:
Trong tiết Vật lí, An thực hành đo hiệu điện thế trong đoạn mạch song song. Theo lí thuyết, đáp án đo được phải bằng đúng x. An đã ghi lại kết quả của n lần đo, chính là dãy số a, a, @,,..., 0 - A2, An Kết quả được coi là chính xác nếu sai số tương đối không vượt quá 5%. An cần tính xem đã đo chính xác được bao nhiêu lần để xem thử dụng cụ thực hành của nhà trường còn tốt không? Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa số nguyên dương n và số thực dương x.
• Dòng tiếp theo chứa n số thực dương a, a, a,...., cho có tối đa hai chữ số ở phần thập phân).
(dữ liệu được
Kết quả: Hiển thị ở thiết bị ra chuẩn một số nguyên duy nhất là số lượng kết quả đo chính xác.
Trong tiết Vật lí, An thực hành đo hiệu điện thế trong đoạn mạch song song. Theo lí thuyết, đáp án đo được phải bằng đúng x. An đã ghi lại kết quả của n lần đo, chính là dãy số a, a, @,,..., 0 - A2, An Kết quả được coi là chính xác nếu sai số tương đối không vượt quá 5%. An cần tính xem đã đo chính xác được bao nhiêu lần để xem thử dụng cụ thực hành của nhà trường còn tốt không? Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa số nguyên dương n và số thực dương x.
• Dòng tiếp theo chứa n số thực dương a, a, a,...., cho có tối đa hai chữ số ở phần thập phân).
(dữ liệu được
Kết quả: Hiển thị ở thiết bị ra chuẩn một số nguyên duy nhất là số lượng kết quả đo chính xác.
Xem đáp án »
25/09/2023
242
Câu 4:
Bản đồ gene
Các nhà khoa học vừa phát hiện ra bản đồ gene của một loài sinh vật trên Trái Đất có nguồn gốc từ rất lâu về trước (niên đại được xác định dựa trên các dấu vết khảo cổ học). Chuỗi gene di truyền của nó được biểu diễn bởi xâu kí tự S (chỉ gồm các kí tự A..Z). Nhằm đánh giá, nghiên cứu nó, họ muốn xem thử nó có đặc tính T hay không. T cũng được biểu diễn dưới dạng một xâu kí tự (với các kí tự A..Z), tương ứng với một đoạn gene. Người ta cho rằng, loại sinh vật này có tính chất T nói trên nếu chuỗi biểu diễn của T là một chuỗi con của S. Tức là, nếu ta lấy ra các kí tự liên tiếp của S tại vị trí nào đó thì có được T. Em hãy lập trình giải quyết bài toán trên. Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa xâu S.
• Dòng thứ hai chứa xâu T.
Kết quả: Hiển thị ở thiết bị ra chuẩn các số nguyên là những vị trí mà ta tìm thấy được T ở trong S.
Bản đồ gene
Các nhà khoa học vừa phát hiện ra bản đồ gene của một loài sinh vật trên Trái Đất có nguồn gốc từ rất lâu về trước (niên đại được xác định dựa trên các dấu vết khảo cổ học). Chuỗi gene di truyền của nó được biểu diễn bởi xâu kí tự S (chỉ gồm các kí tự A..Z). Nhằm đánh giá, nghiên cứu nó, họ muốn xem thử nó có đặc tính T hay không. T cũng được biểu diễn dưới dạng một xâu kí tự (với các kí tự A..Z), tương ứng với một đoạn gene. Người ta cho rằng, loại sinh vật này có tính chất T nói trên nếu chuỗi biểu diễn của T là một chuỗi con của S. Tức là, nếu ta lấy ra các kí tự liên tiếp của S tại vị trí nào đó thì có được T. Em hãy lập trình giải quyết bài toán trên. Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa xâu S.
• Dòng thứ hai chứa xâu T.
Kết quả: Hiển thị ở thiết bị ra chuẩn các số nguyên là những vị trí mà ta tìm thấy được T ở trong S.
Xem đáp án »
11/07/2024
232
về câu hỏi!