tailieunhanh - Kỳ thi chọn lọc học sinh giỏi quốc gia THPT năm 2012 Tin Học

Để thuận lợi hơn cho các bạn trong quá trình ôn tập, trong việc rèn luyện kỹ năng giải để thi, luyện thi vào trường chuyên, "Kỳ thi chọn lọc học sinh giỏi quốc gia THPT năm 2012 Tin Học" giúp các bạn thi học sinh giỏi có kiến thức vững vàng chuẩn bị cho các kỳ | Bộ GIÁO DỤC VÀ ĐÀO TẠO ĐÈ THI CHÍNH THỨC KỲ THI CHỌN HỌC SINH GIỎI QUÔC GIA THPT NÃM 2012 Môn TIN HỌC Thời gian 180 phút không kể thời gian giao đề Ngày thi thứ nhất 11 01 2012 Đề thi có 03 trang gồm 03 bài TỎNG QUAN NGÀY THI THỨ NHÁT Tên bài File chương trình File dữ liệu vào File kết quá Bài 1 Khoáng cách Hamming HAMMING HAMMING. INP Bài 2 Hành trình du lịch TRAVEL. Bài 3 Điều động MOVE. Dấu đirọc thay thể bỏ i PAS hoặc CPP cúa ngôn ngữ lập trình đưọc sủ dụng tương ủng là Pascal hoặc C . Hãy lập trình giải các bài toán sau Bài 1. 6 điểm Khoảng cách Hamming Các phân tử trong tế bào sinh học được cấu tạo từ 4 loại nuclêôtit cơ bản ký hiệu bởi các chữ cái A X T G. Mỗi gen di truyền được tạo thành bởi một chuồi các nuclêôtit với độ dài được tính bàng số lượng nucỉêôtit. Ví dụ AXXTTGAT là một gen có độ dài 8. Trong một chuyến đi khảo sát Giáo sư Altein phát hiện ra một gen ỉ ạ gồm n nuclêôtit được xếp trên một vòng tròn. Ngay lập tức Giáo sư Altein dự định tiến hành so sánh gen lạ này với một so gen mẫu đang lưu trữ nhằm tìm hiểu xem mẫu gen này có gần gũi với loại gen mẫu nào đã được biết. Trong sinh học để đo độ khác biệt giữa hai mẫu gen người ta thường tính khoảng cách Hamming giữa chúng. Khoảng cách Hamming giữa hai gen cùng độ dài được định nghĩa là sô lượng vị trí mà tại đó hai gen chứa các nuclêôtit khác nhau. Ví dụ hai gen AGGTT và TGATT cỏ khoảng cách Hamming bằng 2 do 2 nucỉêôtit ở các vị trí 1 và 3 của chúng ỉà khác nhau. Do các gen mầu được sử dụng đều có độ dài m Ọn à và có cấu trúc thẳng trong khi gen lạ lại có độ dài n vả có cấu trúc vòng nên Giáo sư Altein đã định nghĩa khoảng cách Hamming giữa một gen mẫu và gen lạ là số nhỏ nhất trong số các khoảng cách Hamming giữa gen mẫu và những đoạn gen gồm m nuclêôtit liên tiếp theo chiều kim đồng hồ trong gen lạ. Yêu cầu Cho k gen mẫu hãy xác định gen mẫu với khoảng cách Hamming đến gen lạ là nhỏ nhất và đưa ra khoảng cách tìm được. Dữ liệu Vào từ file văn .