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

Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
NHP MÔN LP TRÌNH  
BÀI TP LN  
ARCEUS VÀ HUYN THOI CÁC POKÉMON  
Version 1.3.  
I. GII THIU  
Sau khi tm mình trong ánh sáng mt tri, 1 qutrng khrung mình và ri sinh ra  
con pokémon đầu tiên: Arceus trong vng sáng chói lòa. Mt sinh vt như con kì lân trng  
vi chiếc vòng sáng trên lưng. Vi blông trng như sao tri mái tóc dài vút bay, mi bước  
chân nhnhàng ca nó được tô đim thêm nhchiếc vòng vàng sáng chĩa 4 cnh ra vi  
mt sc vàng rc r. Arceus - vua ca các loài pokémon.  
Theo truyn thuyết, Arceus đc xem là Pokémon đã sáng to ra thế gii Pokémon và  
mang li ssng cho chúng. Arceus mang trong mình 16 mnh ca ngun sng (côn trùng,  
bóng ti, rng, đin, chiến đấu, bay, bóng ma, c, đất, la, băng, độc t, tâm linh, đá,  
thép, nước). Trong gic mơ ca mình ngài mơ thy mt con Pokémon mèo màu hng nhỏ  
bé sgiúp mình sáng to ssng cho muôn loài. Từ đó, Pokémon ca nhng gic mơ được  
hình thành: Mew - vthn sáng to. Mew cha bgen gc để từ đó to ra nhng vthn  
khai sinh ra thế gii Pokémon khác, Mew được xem là vthy tca Pokémon.  
(Phóng tác tngun wikipedia).  
II. YÊU CU  
Trong bài tp ln này, sinh viên sẽ được cung cp mt file cha dliu nhp. Trong  
đó bao gm thông tin về đon bgen gc ca Mew để từ đó to ra các con Pokémon huyn  
thoi khác. Nhóm sinh viên sthc hin nhng yêu cu biến đổi gen được cho trong bài để  
to ra mt chui cha tên ca các con Pokémon huyn thoi được sinh ra. Chi tiết mô tdữ  
liu nhp, xut và các công vic sinh viên phi làm được nêu trong các mc la mã dưới đây.  
Page 1  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
III. DLIU NHP - DLIU XUT  
Dliu nhp ca chương trình được cha trong file nhp mang tên input.txt. File  
này scha thông tin như ví dsau:  
aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi  
Như vy file nhp input.txt sbao gm mt dòng duy nht. Dòng này smô tvbgen  
gc ca Mew, tbgen gc này kết hp vi các phương pháp biến đổi gen sto ra nhng  
con Pokémon huyn thoi mi. Bgen gc này là mt chui các ký tchcái, chui này sẽ  
có ti đa 1000 ký t. Trong bgen gc sbao gm nhng đon gen. Chiu dài ca mt  
đon gen là tng sgen thông tin có trong đon gen.  
Các định nghĩa:  
TÊN  
Ý NGHĨA  
Là 1 ký tchcái la tinh trong s26 chcái  
la tinh ta đến z. Chhoa phân bit vi chữ  
thường  
Gen  
Tp hp các Gen. Nhng gen này phi đứng  
kế nhau.  
Đon gen  
Hai ký tự đầu tiên trong đon gen. Hai ký tự  
này luôn luôn là 2 ký tthường.  
Ký tth3 trở đi trong đon gen. Ký tthứ  
3 trong đon gen ca bgen gc luôn luôn  
là ký thoa.  
Gen mã hóa  
Gen thông tin  
Tng sgen thông tin ca đon gen. Chiu  
dài đon gen ti thiu bng 3.  
Tp hp các đon gen, mi đon gen ngăn  
cách nhau bi du gch dưới “_”.  
Chiu dài đon gen  
Bgen gc  
d1:  
input.txt  
aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi  
Mô t:  
Bgen gc là: aoArticuna_ksZakrom_aeTornadas_cwHaAh_bbCalabi  
Bgen gc này bao gm 5 đon gen, chiu dài ca mi đon gen theo thtttrái sang  
phi là: 8; 6; 8; 4; 6.  
Dliu xut sgm có 2 dòng. Dòng thnht là mt chui cha gen đã được biến  
đổi tbgen gc. Dòng th2 sđon mã gen tuyt chiêu ca con Pokémon huyn thoi  
được sinh ra (nếu có).  
Page 2  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
IV. CÁC QUY LUT BIN ĐỔI GEN  
Arceus sda trên bgen gc tPokémon Mew và biến đổi nó thành nhng gen  
mi, sau đó nhng gen mi này hình thành nên nhng qutrng và nthành nhng con  
Pokémon huyn thoi mi. Tuy nhiên không phi lúc nào quá trình biến đổi gen cũng thành  
công (nghĩa là không phi lúc nào gen mi cũng có thto thành trng để nthành  
Pokémon).  
Sau mi ln mt con Pokémon huyn thoi mi được sinh ra, Arceus stiếp tc thc hin  
giao nhim vxây dng thế gii cho con Pokémon mi này bng cách to cho nó mt  
quyn năng nào đó; quyn năng này được thhin bng nhng tuyt chiêu. Mt con  
Pokémon scó ít nht là mt tuyt chiêu.  
Các phương pháp biến đổi gen phi tuân theo các lut biến đổi gen được cho trong bng 1:  
(Ưu tiên theo thtttrên xung)  
STT  
QUY LUT  
Quá trình biến đổi gen trên bgen gc được thc hin  
tun ttng ký tmt ttrái sang phi cho đến khi kết  
thúc bgen gc.  
1
Gen mã hóa trong mi đon gen slà phương pháp biến  
đổi gen. Gen mã hóa là xy nghĩa là gen thông tin x được  
thay thế bi gen thông tin y trong tt ccác đon gen từ  
bgen gc.  
2
Bng 1: Các quy lut biến đổi gen  
Kết thúc quá trình biến đổi gen tbgen gc sto ra mt bgen mi. Bgen mi này sẽ  
hình thành được trng Pokémon nếu như trong tt ccác đon gen tbgen mi, có duy  
nht mt đon gen có các gen thông tin trùng vi đon gen ca Pokémon huyn thoi (chi  
tiết vcác đon gen ca Pokémon huyn thoi, xem bng 2) hoc trong trường hp có  
nhiu đon gen trùng vi gen ca Pokemon huyn thoi thì các đon gen này phi ging  
nhau hoc các đon gen chỉ được trùng vi mt gen Pokemon huyn thoi duy nht thì  
trng Pokémon huyn thoi này được hình thành và nra mt con Pokémon huyn thoi.  
d2:  
input.txt  
aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi  
Mô t:  
Bgen gc là: aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi  
Bgen gc có 5 đon gen. Quá trình biến đổi gen bt đầu từ đon gen đầu tiên:  
aoArtecuna.  
Đon gen này có gen mã hóa là “ao”, tc là trong cbgen gc, tt ccác gen thông tin  
“a” sthay thế bng gen thông tin “o”. Như vy sau ln biến đổi đầu tiên, bgen mi sẽ  
như sau: aoArtecuno_ksZokrom_oeTornodos_kwHoAh_bbColobi  
Nhng ln biến đổi gen tiếp theo cũng như thế, và sau 5 ln biến đổi gen (tương ng vi 5  
Page 3  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
gen mã hóa 5 đon gen) thì bgen mi snhư sau:  
aoArtecune_ksZesrem_oeTernedes_kwHeAh_bbCelebi  
Trong bgen mi không có đon gen nào chưa các gen thông tin trùng vi gen ca  
Pokémon huyn thoi nên vì thế bgen mi không to thành trng Pokémon.  
d3:  
input.txt  
aoArtricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno  
Mô t:  
Bgen gc là: aoArtricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
aoArtricune_ksZesrem_oeTernedes_kwHeAh_bbSuicune  
Trong bgen mi có đon gen th5 cha các gen thông tin: “Suicune” trùng vi Pokémon  
huyn thoi mang stht16 trong bng 2. Như vy trng Pokémon được hình thành và  
nra Suicune.  
d4:  
input.txt  
auArticuna_ksSaicane_oeTornadas_kwHaAh_bbSuicuno  
Mô t:  
Bgen gc là: auArticuna_ksSaicane_oeTornadas_kwHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
auArticunu_ksSuicune_oeTernudus_kwHuAh_bbSuicune  
Trong bgen mi có đon gen th2 và th5 cha các gen thông tin: “Suicune” trùng vi  
Pokémon huyn thoi mang stht16 trong bng 2. Như vy trng Pokémon được hình  
thành và nra Suicune.  
Nếu như trong bgen mi có t2 đon gen trlên mà có các gen thông tin trùng vi đon  
gen ca thai Pokémon huyn thoi trlên thì bgen mi này skhông hình thành được  
trng Pokémon.  
d5:  
input.txt  
uuArtichmk_huZakrom_juTornadjs_koHaAh_mnSuicume  
Mô t:  
Bgen gc là: uuArtichmk_huZakrom_juTornadis_koHaAh_mnSuicume  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
uuArticuno_huZaoron_juTornadus_koHaAu_mnSuicune  
Trong bgen mi có đon gen thnht, th3 và th5 cha các gen thông tin: “Articuno”,  
“Tornadus” và “Suicune” trùng vi Pokémon huyn thoi mang stht1; 19 và 16 trong  
bng 2. Như vy trng Pokémon không được hình thành.  
Page 4  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
Danh sách đon gen ca Pokémon huyn thoi được cho trong bng 2:  
STT ĐON GEN POKÉMON HUYN THOI HÌNH MINH HA  
1
2
Articuno  
Cobalion  
Dialga  
3
4
Entei  
5
Giratina  
Groudon  
HoOh  
6
7
8
Keldeo  
Kyogre  
Landorus  
9
10  
Page 5  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
Lugia  
Moltres  
Palkia  
Raikou  
Rayquaza  
Suicune  
Terrakion  
Thundurus  
Tornadus  
Virizion  
Xerneas  
Page 6  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
22  
23  
Yveltal  
Zapdos  
Bng 2: Các đon gen Pokémon huyn thoi  
Sau khi trng Pokémon nra được con Pokémon huyn thoi, Arceus stiếp tc to ra  
tuyt chiêu cho nó. Đon mã gen ca tuyt chiêu sẽ được sp xếp theo quy lut như sau:  
ly đon gen ca Pokémon huyn thoi to thành đon mã gen đầu tiên, tiếp sau đó slà  
các gen thông tin trong các đon gen tbgen mi ca con Pokémon huyn thoi đó (bỏ  
đi các đon gen tbgen mi mà cha đon gen ca Pokémon huyn thoi), các gen  
thông tin này được sp xếp theo thtự đon gen nào có chiu dài ngn hơn được sp xếp  
trước, nếu 2 đon gen có cùng chiu dài thì sp xếp gen thông tin ca đon gen nào trước  
theo thtbng chcái (tính theo gen thông tin).  
d6:  
input.txt  
output.txt  
aoArricuna_ksZakrom_oeTornadas_kwHaAh aoArricune_ksZewrem_oeTernedes_kwHeAh  
_bbSuicuno  
_bbSuicune  
SuicuneHeAhZewremArricuneTernedes  
Mô t:  
Bgen gc là: aoArricuna_ksZakrom_oeTornadas_kwHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
aoArricune_ksZewrem_oeTernedes_kwHeAh_bbSuicune  
Trng Pokémon được hình thành và nra Suicune.  
Đon mã gen tuyt chiêu ca Suicune được to thành như sau:  
_ Ly đon gen “Suicune” làm đon mã gen đầu tiên.  
_ Trong bgen mi ca Suicune có 4 đon gen không cha “Suicune”: aoArricune,  
ksZewrem, oeTernedes và kwHeAh. Chiu dài ca mi đon gen theo thtlà: 8; 6; 8; 4.  
Thtcác gen gen thông tin được sp xếp là: HeAh, Zewrem, Arricune, Ternedes.  
Như vy, đon mã gen tuyt chiêu ca Suicune là: SuicuneHeAhZewremArricuneTernedes  
Output ca test case này là:  
aoArricune_ksZewrem_oeTernedes_kwHeAh_bbSuicune  
SuicuneHeAhZewremArricuneTernedes  
Page 7  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
d7:  
input.txt  
output.txt  
auArricuna_ksSaicane_oeTornadas_kwHaAh aoArricune_ksZewrem_oeTernedes_kwHeAh  
_bbSuicuno  
_bbSuicune  
SuicuneHeAhArricuneTernedes  
Mô t:  
Bgen gc là: auArricuna_ksSaicane_oeTornadas_kwHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
auArricunu_ksSuicune_oeTernudus_kwHuAh_bbSuicune  
Trng Pokémon được hình thành và nra Suicune.  
Đon mã gen tuyt chiêu ca Suicune được to thành như sau:  
_ Ly đon gen “Suicune” làm đon mã gen đầu tiên.  
_ Trong bgen mi ca Suicune có 3 đon gen không cha “Suicune”: aoArricune,  
oeTernedes và kwHeAh. Chiu dài ca mi đon gen theo thtlà: 8; 8; 4. Thtcác gen  
gen thông tin được sp xếp là: HeAh, Arricune, Ternedes.  
Như vy, đon mã gen tuyt chiêu ca Suicune là: SuicuneHeAhArricuneTernedes  
Output ca test case này là:  
aoArricune_ksZewrem_oeTernedes_kwHeAh_bbSuicune  
SuicuneHeAhArricuneTernedes  
Nếu như kết thúc quá trình biến đổi gen mà không to thành con Pokémon huyn thoi nào  
thì đon mã tuyt chiêu lúc by gislà “NULL”.  
d8:  
input.txt  
output.txt  
aoArtecuna_ksZakrom_oeTornadas_kwHaAh aoArtecune_ksZewrem_oeTernedes_kwHeAh  
_bbColobi  
_bbCelebi  
NULL  
Mô t:  
Bgen gc là: aoArtecuna_ksZakrom_oeTornadas_kwHaAh_bbColobi  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
aoArtecune_ksZewrem_oeTernedes_kwHeAh_bbCelebi  
Trong bgen mi không có đon gen nào chưa các gen thông tin trùng vi gen ca  
Pokémon huyn thoi nên vì thế bgen mi không to thành trng Pokémon. Đon mã  
tuyt chiêu là: NULL  
Page 8  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
Trường hp đặc bit:  
Trong quá trình biến đổi gen, Arceus gp khó khăn khi gp mt gen mã hóa lạ đó là  
“zz”. Khi quá trình biến đổi gen gp phi gen mã hóa “zz”, quá trình biến đổi gen sbri  
lon. Vic này có nghĩa là, sau khi quá trình biến đổi gen thc hin đến gen thông tin cui  
cùng ca bgen gc (hoc bgen mi), thì quá trình này li tiếp tc được thc hin tgen  
đầu tiên. Quá trình này lp đi lp li cho đến khi bgen mi to thành không thay đổi so  
vi bgen lin trước đó thì dng li.  
d9:  
input.txt  
output.txt  
aoArtricuna_zzZakrom_oeTornadas_haHaAh_ aoArtricune_  
bbSuicuno  
zzZekrem_oeTernedes_haHeAe_bbSuicune  
SuicuneHeAeZekremTernedesArtricune  
Mô t:  
Bgen gc là: aoArtricuna_zzZakrom_oeTornadas_haHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
aoArtricune_zzZekrem_oeTernedes_haHeAa_bbSuicune  
Tuy nhiên trong đon gen th2 có cha gen mã hóa “zz” nên quá trình này li được lp li  
ln th2. Sau 5 ln tiếp theo bgen mi slà:  
aoArtricune_ zzZekrem_oeTernedes_haHeAe_bbSuicune  
Bgen mi ln th2 khác ln thnht, tiếp tc lp li ln th3. Sau 5 ln tiếp theo bộ  
gen mi slà:  
aoArtricune_ zzZekrem_oeTernedes_haHeAe_bbSuicune  
Kết thúc biến đổi gen ln th3 này, bgen mi ging vi bgen cũ lin trước đó (ln thứ  
2). Như vy quá trình biến đổi gen dng li.  
Trng Pokémon được hình thành và nra Suicune. Đon mã tuyt chiêu slà:  
SuicuneHeAeZekremTernedesArtricune  
Trong trường hp quá trình này blp đi lp li vô tn, tc là cmi ln biến đổi gen bộ  
gen mi thay đổi liên tc không thể ổn định được, Arceus đành phi phá hy ln biến đổi  
gen này. Khi đó, bgen mi trong dliu xut slà “NULL”.  
d9:  
input.txt  
output.txt  
NULL  
aoArtricena_zzZakrom_eaTernadas_oeHaAh_bbSuicuno  
NULL  
Mô t:  
Bgen gc là: aoArtricena_zzZakrom_eaTernadas_oeHaAh_bbSuicuno  
Sau 5 ln biến đổi gen thì bgen mi snhư sau:  
aoArtricane_zzZekrem_eaTarnedes_oeHeAh_bbSuicune  
Tuy nhiên trong đon gen th2 có cha gen mã hóa “zz” nên quá trình này li được lp li  
Page 9  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
ln th2. Sau 5 ln tiếp theo bgen mi slà:  
aoArtricena_zzZakram_eaTernadas_oeHaAh_bbSuicuna  
Bgen mi ln th2 khác ln thnht, tiếp tc lp li ln th3. Sau 5 ln tiếp theo bộ  
gen mi slà:  
aoArtricane_zzZekrem_eaTarnedes_oeHeAh_bbSuicune  
Bgen mi ln th3 khác ln th2, tiếp tc lp li ln th4. Sau 5 ln tiếp theo bgen  
mi slà:  
aoArtricena_zzZakram_eaTernadas_oeHaAh_bbSuicuna  
Như vy, ta nhn thy qua trình biến đổi gen này sblp li vô tn không bao gidng,  
vì thế Arceus phi phá hy quá trình biến đổi gen này.  
Page 10  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
V. CÁCH DCH VÀ THC THI CHƯƠNG TRÌNH.  
Sinh viên download file assigment.zip ttrang Web ca môn hc. Khi gii nén file này, sẽ  
được các file sau:  
input.txt  
Mt file input ví dụ  
main.c  
Chương trình chính  
pokemon.c  
defs.c  
assignment_1.3.pdf  
Chương trình thc hin bi sinh viên  
Định nghĩa cu trúc và hàm dùng chung  
Mô tbài tp ln  
File input.txt là mt file nhp mu như được mô tả ở mc III. File main.c là chương trình  
khi to, bao gm mt shàm viết sn. Lưu ý rng sinh viên không được phép thay đổi  
file main.c defs.h khi hin thc chương trình. Ngoài ra, các hàm do sinh viên viết  
không được xut bt kdliu nào ra màn hình khi thc thi. Vic in ra màn hình đã  
có hàm viết sn trong file main.c. File pokemon.c là tp tin cha code do nhóm sinh viên  
viết.  
Để dch và thc thi chương trình, sinh viên cha c4 files: main.c, defs.h, pokemon.c, và  
input.txt trong cùng mt thư mc cha project; sau đó chcn dch và thc thi duy nht file  
main.c.  
Lưu ý:  
1.  
2.  
Sinh viên không được thêm bt kthư vin nào khác ngoài các thư vin được cho  
sn.  
Thi gian chy ca chương trình phi đảm bo không quá 5s cho mt test case.  
VI. NP BÀI.  
Nhóm Sinh viên np 2 bài: file viết code (pokemon.c) và file báo cáo. Ni dung cthvề  
cách thc np bài, ni dung file báo cáo sẽ được thông báo trên lp.  
Thi hn np bài: Có 2 giai đon np bài  
Giai đon 1: np file viết code vi yêu cu thc hin được ½ ni dung yêu cu (làm  
được nhng công vic thay thế gen - đến hết ví d5). Thi hn cho giai đon 1: 23  
gi59 phút, ChNht, ngày 8 tháng 5 năm 2016.  
Giai đon 2: np file viết code hoàn chnh và file báo cáo. Thi hn cho giai đon 2:  
đến trước thi cui k.  
Page 11  
Trường Đại hc Bách khoa - ĐHQG TP.HCM  
Khoa Khoa hc và Kthut Máy tính  
VII. XLÝ GIAN LN.  
Bài tp ln phi được nhóm sinh viên TLÀM. Nhóm sinh viên sbcoi là gian ln nếu:  
1.  
2.  
Có sging nhau bt thường gia mã ngun ca các bài np gia các nhóm. Trong  
trường hp này, TT Ccác bài np đều bcoi là gian ln. Do vy nhóm sinh viên  
phi bo vmã ngun bài tp ln ca mình.  
Nhóm sinh viên không hiu mã ngun do chính mình viết, trnhng phn mã được  
cung cp sn trong chương trình khi to. Sinh viên có ththam kho tbt kỳ  
ngun tài liu nào, tuy nhiên phi đảm bo rng mình hiu rõ ý nghĩa ca tt cả  
nhng dòng lnh mà mình viết. Trong trường hp không hiu rõ mã ngun ca nơi  
mình tham kho, sinh viên được đặc bit cnh báo là KHÔNG ĐƯỢC sdng mã  
ngun này; thay vào đó nên sdng nhng gì đã được hc để viết chương trình.  
Trong trường hp bkết lun là gian ln, nhóm sinh viên (tt csinh viên trong nhóm) sbị  
đim 0 cho toàn bmôn hc (không chbài tp ln). KHÔNG CHP NHN BT KGII  
THÍCH NÀO VÀ KHÔNG CÓ BT KNGOI LNÀO!  
Sau mi bài tp ln được np, scó mt ssinh viên trong nhóm được gi phng vn ngu  
nhiên để chng minh rng bài tp ln va được np là do chính nhóm mình làm.  
--- HT ---  
Page 12  
pdf 12 trang baolam 29/04/2022 5880
Bạn đang xem tài liệu "Bài tập lớn Nhập môn lập trình - Arceus và huyền thoại các pokémon", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_tap_lon_nhap_mon_lap_trinh_arceus_va_huyen_thoai_cac_pok.pdf