Với giải sách bài tập Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm sách Cánh diều hay, chi tiết 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 trong SBT Tin học 11. Mời các bạn đón xem:
Sách bài tập Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm
Với một dãy chưa được sắp xếp theo thứ tự, ta không có đủ cơ sở để loại bỏ một nửa dãy số ra khỏi phạm vi tìm kiếm sau khi so sánh phần tử giữa với giá trị x cần tìm.
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.
• 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.
Lời giải:
Áp dụng tìm kiếm tuần tự, tuy nhiên điều kiện “bằng” cần phải tính.
Chương trình mẫu:
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.
Câu Fcs30 trang 56 SBT Tin học 11: Bản đồ gene
• 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.
Lời giải:
Áp dụng lát cắt danh sách, việc cài đặt khá đơn giản.
S = input ()
T = input ()
for i in range (len (S) - len (T) + 1):
if T == S[i: i+len (T)]:
print (i+1, end = " ")
Mở rộng: Trong thực tế, thuật toán trên chưa đủ hiệu quả, vì việc so sánh hai xấu có độ phức tạp là len(T). Vậy độ phức tạp của thuật toán trên là len(S) x len(T) trong trường hợp xấu nhất. Áp dụng tư tưởng làm mịn dần thuật toán, người ta đã phát minh ra các thuật toán so khớp xâu:
– Hash (thường gặp trong mật mã học – cryptography).
– KMP (tận dụng những kí tự đã được so sánh trước đó để không phải so sánh lại từ đầu).
- Z function.
Em có thể tìm đọc để tăng thêm niềm đam mê với thuật toán.
Xem thêm các bài giải SBT Tin học lớp 11 Cánh diều hay, chi tiết khác: