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

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 - Cánh diều

Câu F^cs30 trang 56 SBT Tin học 11: 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.

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.

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

• Câu F^cs26 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 F^cs27 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 F^cs28 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. Theo lí thuyết, đáp án đo được phải bằng đúng x ....

• Câu F^cs29 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 ....

Xem thêm các bà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:

• SBT Tin học 11 Bài 6: Kiểm thử và sửa lỗi chương trình

• SBT Tin học 11 Bài 8: Lập trình một số thuật toán sắp xếp

• SBT Tin học 11 Bài 9: Lập trình sắp xếp nhanh

• SBT Tin học 11 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

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

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải sgk Tin học 11 Cánh diều
• Giải Chuyên đề Tin học 11 Cánh diều
• Giải SBT Tin học 11 Cánh diều
• Giải lớp 11 Cánh diều (các môn học)
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)

---