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

us - 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 QUY LUẬT 1 Quá trình biến đổi gen trên bộ gen gốc được thực hiện 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. 2 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 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 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 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 11 Lugia 12 Moltres 13 Palkia 14 Raikou 15 Rayquaza 16 Suicune 17 Terrakion 18 Thundurus 19 Tornadus 20 Virizion 21 Xerneas 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 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 _bbSuicuno aoArricune_ksZesrem_oeTernedes_kwHeAh _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 8 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 _bbSuicuno auArricunu_ksSuicune_oeTernudus_kwHuAh _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 _bbColobi aoArtecune_ksZesrem_oeTernedes_kwHeAh _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 9 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_ bbSuicuno aoArtricune_ 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 10 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 11 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 12 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 ---