Bài tập lớn môn Nhập môn lập trình - Đề tài: Arceus và huyền thoại các Pokémon

thứ 3 trở đi trong đoạn gen. Ký tự thứ 
 Gen thông tin 3 trong đoạn gen của bộ gen gốc luôn luôn 
 là ký tự hoa. 
 Tổng số gen thông tin của đoạn gen. Chiều 
 Chiều dài đoạn gen 
 dài đoạn gen tối thiểu bằng 3. 
 Tập hợp các đoạn gen, mỗi đoạn gen ngăn 
 Bộ gen gốc 
 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 2 
 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 QUY LUẬT 
 Quá trình biến đổi gen trên bộ gen gốc được thực hiện 
 1 tuần tự từng ký tự một từ trái sang phải cho đến khi kết 
 thúc bộ gen gốc. 
 Gen mã hóa trong mỗi đoạn gen sẽ là phương pháp biến 
 đổi gen. Gen mã hóa là xy nghĩa là gen thông tin x được 
 2 
 thay thế bởi gen thông tin y trong tất cả các đoạn gen từ 
 bộ gen gốc. 
 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 3 
 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 4 
 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 
 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 
11 Lugia 
12 Moltres 
13 Palkia 
14 Raikou 
15 Rayquaza 
16 Suicune 
17 Terrakion 
18 Thundurus 
19 Tornadus 
20 Virizion 
21 Xerneas 
 Page 6 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
 22 Yveltal 
 23 Zapdos 
 Bảng 2: Các đoạn gen Pokémon huyền thoại 
Sau khi trứng Pokémon nở ra được con Pokémon huyền thoại, Arceus sẽ tiếp tục tạo ra 
tuyệt chiêu cho nó. Đoạn mã gen của tuyệt chiêu sẽ được sắp xếp theo quy luật như sau: 
lấy đoạn gen của Pokémon huyền thoại tạo thành đoạn mã gen đầu tiên, tiếp sau đó sẽ là 
các gen thông tin trong các đoạn gen từ bộ gen mới của con Pokémon huyền thoại đó (bỏ 
đi các đoạn gen từ bộ gen mới mà chứa đoạn gen của Pokémon huyền thoại), các gen 
thông tin này được sắp xếp theo thứ tự đoạn gen nào có chiều dài ngắn hơn được sắp xếp 
trước, nếu 2 đoạn gen có cùng chiều dài thì sắp xếp gen thông tin của đoạn gen nào trước 
theo thứ tự bảng chữ cái (tính theo gen thông tin). 
Ví dụ 6: 
input.txt output.txt 
aoArricuna_ksZakrom_oeTornadas_kwHaAh aoArricune_ksZesrem_oeTernedes_kwHeAh
_bbSuicuno _bbSuicune 
 SuicuneHeAhZewremArricuneTernedes 
Mô tả: 
Bộ gen gốc là: aoArricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno 
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau: 
aoArricune_ksZesrem_oeTernedes_kwHeAh_bbSuicune 
Trứng Pokémon được hình thành và nở ra Suicune. 
Đoạn mã gen tuyệt chiêu của Suicune được tạo thành như sau: 
_ Lấy đoạn gen “Suicune” làm đoạn mã gen đầu tiên. 
_ Trong bộ gen mới của Suicune có 4 đoạn gen không chứa “Suicune”: aoArricune, 
ksZewrem, oeTernedes và kwHeAh. Chiều dài của mỗi đoạn gen theo thứ tự là: 8; 6; 8; 4. 
Thứ tự các gen gen thông tin được sắp xếp là: HeAh, Zewrem, Arricune, Ternedes. 
Như vậy, đoạn mã gen tuyệt chiêu của Suicune là: SuicuneHeAhZewremArricuneTernedes 
Output của test case này là: 
aoArricune_ksZewrem_oeTernedes_kwHeAh_bbSuicune 
SuicuneHeAhZewremArricuneTernedes 
 Page 7 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
Ví dụ 7: 
input.txt output.txt 
auArricuna_ksSaicane_oeTornadas_kwHaAh auArricunu_ksSuicune_oeTernudus_kwHuAh
_bbSuicuno _bbSuicune 
 SuicuneHuAhArricunuTernudus 
Mô tả: 
Bộ gen gốc là: auArricuna_ksSaicane_oeTornadas_kwHaAh_bbSuicuno 
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau: 
auArricunu_ksSuicune_oeTernudus_kwHuAh_bbSuicune 
Trứng Pokémon được hình thành và nở ra Suicune. 
Đoạn mã gen tuyệt chiêu của Suicune được tạo thành như sau: 
_ Lấy đoạn gen “Suicune” làm đoạn mã gen đầu tiên. 
_ Trong bộ gen mới của Suicune có 3 đoạn gen không chứa “Suicune”: aoArricune, 
oeTernedes và kwHeAh. Chiều dài của mỗi đoạn gen theo thứ tự là: 8; 8; 4. Thứ tự các gen 
gen thông tin được sắp xếp là: HeAh, Arricune, Ternedes. 
Như vậy, đoạn mã gen tuyệt chiêu của Suicune là: SuicuneHeAhArricuneTernedes 
Output của test case này là: 
auArricunu_ksSuicune_oeTernudus_kwHuAh_bbSuicune 
SuicuneHuAhArricunuTernudus 
Nếu như kết thúc quá trình biến đổi gen mà không tạo thành con Pokémon huyền thoại nào 
thì đoạn mã tuyệt chiêu lúc bấy giờ sẽ là “NULL”. 
Ví dụ 8: 
input.txt output.txt 
aoArtecuna_ksZakrom_oeTornadas_kwHaAh aoArtecune_ksZesrem_oeTernedes_kwHeAh
_bbColobi _bbCelebi 
 NULL 
Mô tả: 
Bộ gen gốc là: aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi 
Sau 5 lần biến đổi 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. Đoạn mã 
tuyệt chiêu là: NULL 
 Page 8 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
Trường hợp đặc biệt: 
 Trong quá trình biến đổi gen, Arceus gặp khó khăn khi gặp một gen mã hóa lạ đó là 
“zz”. Khi quá trình biến đổi gen gặp phải gen mã hóa “zz”, quá trình biến đổi gen sẽ bị rối 
loạn. Việc này có nghĩa là, sau khi quá trình biến đổi gen thực hiện đến gen thông tin cuối 
cùng của bộ gen gốc (hoặc bộ gen mới), thì quá trình này lại tiếp tục được thực hiện từ gen 
đầu tiên. Quá trình này lặp đi lặp lại cho đến khi bộ gen mới tạo thành không thay đổi so 
với bộ gen liền trước đó thì dừng lại. 
Ví dụ 9: 
input.txt output.txt 
aoArtricuna_zzZakrom_oeTornadas_haHaAh_ aoArtricune_ 
bbSuicuno zzZekrem_oeTernedes_haHeAe_bbSuicune 
 SuicuneHeAeZekremTernedesArtricune 
Mô tả: 
Bộ gen gốc là: aoArtricuna_zzZakrom_oeTornadas_haHaAh_bbSuicuno 
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau: 
aoArtricune_zzZekrem_oeTernedes_haHeAa_bbSuicune 
Tuy nhiên trong đoạn gen thứ 2 có chứa gen mã hóa “zz” nên quá trình này lại được lặp lại 
lần thứ 2. Sau 5 lần tiếp theo bộ gen mới sẽ là: 
aoArtricune_ zzZekrem_oeTernedes_haHeAe_bbSuicune 
Bộ gen mới ở lần thứ 2 khác lần thứ nhất, tiếp tục lặp lại lần thứ 3. Sau 5 lần tiếp theo bộ 
gen mới sẽ là: 
aoArtricune_ zzZekrem_oeTernedes_haHeAe_bbSuicune 
Kết thúc biến đổi gen lần thứ 3 này, bộ gen mới giống với bộ gen cũ liền trước đó (ở lần thứ 
2). Như vậy quá trình biến đổi gen dừng lại. 
Trứng Pokémon được hình thành và nở ra Suicune. Đoạn mã tuyệt chiêu sẽ là: 
SuicuneHeAeZekremTernedesArtricune 
Trong trường hợp quá trình này bị lặp đi lặp lại vô tận, tức là cứ mỗi lần biến đổi gen bộ 
gen mới thay đổi liên tục không thể ổn định được, Arceus đành phải phá hủy lần biến đổi 
gen này. Khi đó, bộ gen mới trong dữ liệu xuất sẽ là “NULL”. 
Ví dụ 10: 
input.txt output.txt 
aoArtricena_zzZakrom_eaTernadas_oeHaAh_bbSuicuno NULL 
 NULL 
Mô tả: 
Bộ gen gốc là: aoArtricena_zzZakrom_eaTernadas_oeHaAh_bbSuicuno 
Sau 5 lần biến đổi gen thì bộ gen mới sẽ như sau: 
aoArtricane_zzZekrem_eaTarnedes_oeHeAh_bbSuicune 
Tuy nhiên trong đoạn gen thứ 2 có chứa gen mã hóa “zz” nên quá trình này lại được lặp lại 
 Page 9 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
lần thứ 2. Sau 5 lần tiếp theo bộ gen mới sẽ là: 
aoArtricena_zzZakram_eaTernadas_oeHaAh_bbSuicuna 
Bộ gen mới ở lần thứ 2 khác lần thứ nhất, tiếp tục lặp lại lần thứ 3. Sau 5 lần tiếp theo bộ 
gen mới sẽ là: 
aoArtricane_zzZekrem_eaTarnedes_oeHeAh_bbSuicune 
Bộ gen mới ở lần thứ 3 khác lần thứ 2, tiếp tục lặp lại lần thứ 4. Sau 5 lần tiếp theo bộ gen 
mới sẽ là: 
aoArtricena_zzZakram_eaTernadas_oeHaAh_bbSuicuna 
Như vậy, ta nhận thấy qua trình biến đổi gen này sẽ bị lặp lại vô tận không bao giờ dừng, 
vì thế Arceus phải phá hủy quá trình biến đổi gen này. 
 Page 10 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
V. CÁCH DỊCH VÀ THỰC THI CHƯƠNG TRÌNH. 
Sinh viên download file assigment.zip từ trang Web của môn học. Khi giải nén file này, sẽ 
có được các file sau: 
 input.txt Một file input ví dụ 
 pokemon.c Chương trình chính 
 assignment_1.0.pdf Mô tả bài tập lớn 
File input.txt là một file nhập mẫu như được mô tả ở mục III. File pokemon.c là tập tin chứa 
code khởi tạo và code do nhóm sinh viên viết. Lưu ý rằng sinh viên không được phép 
thay đổi những đoạn đã được lưu ý trong file này. Ngoài ra, các hàm do sinh viên viết 
không được xuất bất kỳ dữ liệu nào ra màn hình khi thực thi. 
Để dịch và thực thi chương trình, sinh viên chứa cả 2 files: pokemon.c, và input.txt trong 
cùng một thư mục chứa project; sau đó chỉ cần dịch và thực thi duy nhất file pokemon.c. 
Lưu ý: 
 1. Sinh viên không được thêm bất kỳ thư viện nào khác ngoài 3 thư viện được cho sẵn. 
 2. Thời gian chạy của chương trình phải đảm bảo không quá 5s cho một test case. 
VI. NỘP BÀI. 
Nhóm Sinh viên nộp 2 bài: file viết code (pokemon.c) và file báo cáo. Nội dung cụ thể về 
cách thức nộp bài, nội dung file báo cáo sẽ được thông báo trên lớp. 
Thời hạn nộp bài: Có 2 giai đoạn nộp bài 
 Giai đoạn 1: nộp file viết code với yêu cầu thực hiện được ½ nội dung yêu cầu (làm 
 được những công việc thay thế gen - đến hết ví dụ 5). Thời hạn cho giai đoạn 1: 23 
 giờ 59 phút, Chủ Nhật, ngày 01 tháng 05 năm 2016. 
 Giai đoạn 2: nộp file viết code hoàn chỉnh và file báo cáo. Thời hạn cho giai đoạn 2: 
 đến trước thi cuối kỳ. 
 Page 11 
 Trường Đại học Bách khoa - ĐHQG TP.HCM 
 Khoa Khoa học và Kỹ thuật Máy tính 
VII. XỬ LÝ GIAN LẬN. 
Bài tập lớn phải được nhóm sinh viên TỰ LÀM. Nhóm sinh viên sẽ bị coi là gian lận nếu: 
 1. Có sự giống nhau bất thường giữa mã nguồn của các bài nộp giữa các nhóm. Trong 
 trường hợp này, TẤT CẢ các bài nộp đều bị coi là gian lận. Do vậy nhóm sinh viên 
 phải bảo vệ mã nguồn bài tập lớn của mình. 
 2. Nhóm sinh viên không hiểu mã nguồn do chính mình viết, trừ những phần mã được 
 cung cấp sẵn trong chương trình khởi tạo. Sinh viên có thể tham khảo từ bất kỳ 
 nguồn tài liệu nào, tuy nhiên phải đảm bảo rằng mình hiểu rõ ý nghĩa của tất cả 
 những dòng lệnh mà mình viết. Trong trường hợp không hiểu rõ mã nguồn của nơi 
 mình tham khảo, sinh viên được đặc biệt cảnh báo là KHÔNG ĐƯỢC sử dụng mã 
 nguồn này; thay vào đó nên sử dụng những gì đã được học để viết chương trình. 
Trong trường hợp bị kết luận là gian lận, nhóm sinh viên (tất cả sinh viên trong nhóm) sẽ bị 
điểm 0 cho toàn bộ môn học (không chỉ bài tập lớn). KHÔNG CHẤP NHẬN BẤT KỲ GIẢI 
THÍCH NÀO VÀ KHÔNG CÓ BẤT KỲ NGOẠI LỆ NÀO! 
Sau mỗi bài tập lớn được nộp, sẽ có một số sinh viên trong nhóm được gọi phỏng vấn ngẫu 
nhiên để chứng minh rằng bài tập lớn vừa được nộp là do chính nhóm mình làm. 
 --- HẾT --- 
 Page 12