Page 1
Trường Đại học Bách khoa - ĐHQG TP.HCM
Khoa Khoa học và Kỹ thuật Máy tính
Version 1.0.
I. GIỚI THIỆU
Sau khi tắm mình trong ánh sáng mặt trời, 1 quả trứng khẽ rung mình và rồi sinh ra
con pokémon đầu tiên: Arceus trong vầng sáng chói lòa. Một sinh vật như con kì lân trắng
với chiếc vòng sáng trên lưng. Với bộ lông trắng như sao trời mái tóc dài vút bay, mỗi bước
chân nhẹ nhàng của nó được tô điểm thêm nhờ chiếc vòng vàng sáng chĩa 4 cạnh ra với
một sắc vàng rực rỡ. Arceus - vua của các loài pokémon.
Theo truyền thuyết, Arceus đc xem là Pokémon đã sáng tạo ra thế giới Pokémon và
mang lại sự sống cho chúng. Arceus mang trong mình 16 mảnh của nguồn sống (côn trùng,
bóng tối, rồng, điện, chiến đấu, bay, bóng ma, cỏ, đất, lửa, băng, độc tố, tâm linh, đá,
thép, nước). Trong giấc mơ của mình ngài mơ thấy một con Pokémon mèo màu hồng nhỏ
bé sẽ giúp mình sáng tạo sự sống cho muôn loài. Từ đó, Pokémon của những giấc mơ được
hình thành: Mew - vị thần sáng tạo. Mew chứa bộ gen gốc để từ đó tạo ra những vị thần
khai sinh ra thế giới Pokémon khác, Mew được xem là vị thủy tổ của Pokémon.
(Phóng tác từ nguồn wikipedia).
II. YÊU CẦU
Trong bài tập lớn này, sinh viên sẽ được cung cấp một file chứa dữ liệu nhập. Trong
đó bao gồm thông tin về đoạn bộ gen gốc của Mew để từ đó tạo ra các con Pokémon huyền
thoại khác. Nhóm sinh viên sẽ thực hiện những yêu cầu biến đổi gen được cho trong bài để
tạo ra một chuỗi chứa tên của các con Pokémon huyền thoại được sinh ra. Chi tiết mô tả dữ
liệu nhập, xuất và các công việc sinh viên phải làm được nêu trong các mục la mã dưới đây.
NHẬP MÔN LẬP TRÌNH
BÀI TẬP LỚN
ARCEUS VÀ HUYỀN THOẠI CÁC POKÉMON
Page 2
Trường Đại học Bách khoa - ĐHQG TP.HCM
Khoa Khoa học và Kỹ thuật Máy tính
III. DỮ LIỆU NHẬP - DỮ LIỆU XUẤT
Dữ liệu nhập của chương trình được chứa trong file nhập mang tên input.txt. File
này sẽ chứa thông tin như ví dụ sau:
aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi
Như vậy file nhập input.txt sẽ bao gồm một dòng duy nhất. Dòng này sẽ mô tả về bộ gen
gốc của Mew, từ bộ gen gốc này kết hợp với các phương pháp biến đổi gen sẽ tạo ra những
con Pokémon huyền thoại mới. Bộ gen gốc này là một chuỗi các ký tự chữ cái, chuỗi này sẽ
có tối đa 1000 ký tự. Trong bộ gen gốc sẽ bao gồm những đoạn gen. Chiều dài của một
đoạn gen là tổng số gen thông tin có trong đoạn gen.
Các định nghĩa:
TÊN
Ý NGHĨA
Gen
Là 1 ký tự chữ cái la tinh trong số 26 chữ cái
la tinh từ a đến z. Chữ hoa phân biệt với chữ
thường
Đoạn gen
Tập hợp các Gen. Những gen này phải đứng
kế nhau.
Gen mã hóa
Hai ký tự đầu tiên trong đoạn gen. Hai ký tự
này luôn luôn là 2 ký tự thường.
Gen thông tin
Ký tự thứ 3 trở đi trong đoạn gen. Ký tự thứ
3 trong đoạn gen của bộ gen gốc luôn luôn
là ký tự hoa.
Chiều dài đoạn gen
Tổng số gen thông tin của đoạn gen. Chiều
dài đoạn gen tối thiểu bằng 3.
Bộ gen gốc
Tập hợp các đoạn gen, mỗi đoạn gen ngăn
cách nhau bởi dấu gạch dưới “_”.
Ví dụ 1:
input.txt
aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi
Mô tả:
Bộ gen gốc là: aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi
Bộ gen gốc này bao gồm 5 đoạn gen, chiều dài của mỗi đoạn gen theo thứ tự từ trái sang
phải là: 8; 6; 8; 4; 6.
Dữ liệu xuất sẽ gồm có 2 dòng. Dòng thứ nhất là một chuỗi chứa gen đã được biến
đổi từ bộ gen gốc. Dòng thứ 2 sẽ là đoạn mã gen tuyệt chiêu của con Pokémon huyền thoại
được sinh ra (nếu có).
Page 3
Trường Đại học Bách khoa - ĐHQG TP.HCM
Khoa Khoa học và Kỹ thuật Máy tính
IV. CÁC QUY LUẬT BIẾN ĐỔI GEN
Arceus sẽ dựa trên bộ gen gốc từ Pokémon Mew và biến đổi nó thành những gen
mới, sau đó những gen mới này hình thành nên những quả trứng và nở thành những con
Pokémon huyền thoại mới. Tuy nhiên không phải lúc nào quá trình biến đổi gen cũng thành
công (nghĩa là không phải lúc nào gen mới cũng có thể tạo thành trứng để nở thành
Pokémon).
Sau mỗi lần một con Pokémon huyền thoại mới được sinh ra, Arceus sẽ tiếp tục thực hiện
giao nhiệm vụ xây dựng thế giới cho con Pokémon mới này bằng cách tạo cho nó một
quyền năng nào đó; quyền năng này được thể hiện bằng những tuyệt chiêu. Một con
Pokémon sẽ có ít nhất là một tuyệt chiêu.
Các phương pháp biến đổi gen phải tuân theo các luật biến đổi gen được cho trong bảng 1:
(Ưu tiên theo thứ tự từ trên xuống)
STT
1
2
Bảng 1: Các quy luật biến đổi gen
Kết thúc quá trình biến đổi gen từ bộ gen gốc sẽ tạo ra một bộ gen mới. Bộ gen mới này sẽ
hình thành được trứng Pokémon nếu như trong tất cả các đoạn gen từ bộ gen mới, có duy
nhất một đoạn gen có các gen thông tin trùng với đoạn gen của Pokémon huyền thoại (chi
tiết về các đoạn gen của Pokémon huyền thoại, xem bảng 2) hoặc trong trường hợp có
nhiều đoạn gen trùng với gen của Pokemon huyền thoại thì các đoạn gen này phải giống
nhau hoặc các đoạn gen chỉ được trùng với một gen Pokemon huyền thoại duy nhất thì
trứng Pokémon huyền thoại này được hình thành và nở ra một con Pokémon huyền thoại.
Ví dụ 2:
input.txt
aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi
Mô tả:
Bộ gen gốc là: aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi
Bộ gen gốc có 5 đoạn gen. Quá trình biến đổi gen bắt đầu từ đoạn gen đầu tiên:
aoArtecuna.
Đoạn gen này có gen mã hóa là “ao”, tức là trong cả bộ gen gốc, tất cả các gen thông tin
“a” sẽ thay thế bằng gen thông tin “o”. Như vậy sau lần biến đổi đầu tiên, bộ gen mới sẽ
như sau: aoArtecuno_ksZokrom_oeTornodos_kwHoAh_bbColobi
Những lần biến đổi gen tiếp theo cũng như thế, và sau 5 lần biến đổi gen (tương ứng với 5
Page 4
Trường Đại học Bách khoa - ĐHQG TP.HCM
Khoa Khoa học và Kỹ thuật Máy tính
gen mã hóa ở 5 đoạn gen) thì bộ gen mới sẽ như sau:
aoArtecune_ksZesrem_oeTernedes_kwHeAh_bbCelebi
Trong bộ gen mới không có đoạn gen nào chưa các gen thông tin trùng với gen của
Pokémon huyền thoại nên vì thế bộ gen mới không tạo thành trứng Pokémon.
Ví dụ 3:
input.txt
aoArtricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno
Mô tả:
Bộ gen gốc là: aoArtricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau:
aoArtricune_ksZesrem_oeTernedes_kwHeAh_bbSuicune
Trong bộ gen mới có đoạn gen thứ 5 chứa các gen thông tin: “Suicune” trùng với Pokémon
huyền thoại mang số thứ tự 16 trong bảng 2. Như vậy trứng Pokémon được hình thành và
nở ra Suicune.
Ví dụ 4:
input.txt
auArticuna_ksSaicane_oeTornadas_kwHaAh_bbSuicuno
Mô tả:
Bộ gen gốc là: auArticuna_ ksSaicane_oeTornadas_kwHaAh_bbSuicuno
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau:
auArticunu_ksSuicune_oeTernudus_kwHuAh_bbSuicune
Trong bộ gen mới có đoạn gen thứ 2 và thứ 5 chứa các gen thông tin: “Suicune” trùng với
Pokémon huyền thoại mang số thứ tự 16 trong bảng 2. Như vậy trứng Pokémon được hình
thành và nở ra Suicune.
Nếu như trong bộ gen mới có từ 2 đoạn gen trở lên mà có các gen thông tin trùng với đoạn
gen của từ hai Pokémon huyền thoại trở lên thì bộ gen mới này sẽ không hình thành được
trứng Pokémon.
Ví dụ 5:
input.txt
uuArtichmk_huZakrom_juTornadjs_koHaAh_mnSuicume
Mô tả:
Bộ gen gốc là: uuArtichmk_huZakrom_ juTornadjs_koHaAh_mnSuicume
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau:
uuArticuno_huZaoron_juTornadus_koHaAu_mnSuicune
Trong bộ gen mới có đoạn gen thứ nhất, thứ 3 và thứ 5 chứa các gen thông tin: “Articuno “,
“Tornadus “ và “Suicune” trùng với Pokémon huyền thoại mang số thứ tự 1; 19 và 16 trong
bảng 2. Như vậy trứng Pokémon không được hình thành.
Page 5
Trường Đại học Bách khoa - ĐHQG TP.HCM
Khoa Khoa học và Kỹ thuật Máy tính
Danh sách đoạn gen của Pokémon huyền thoại được cho trong bảng 2:
STT
ĐOẠN GEN POKÉMON HUYỀN THOẠI
HÌNH MINH HỌA
1
Articuno
2
Cobalion
3
Dialga
4
Entei
5
Giratina
6
Groudon
7
HoOh
8
Keldeo
9
Kyogre
10
Landorus