Tài liệu dưỡng học sinh giỏi C++

Nội dung text: Tài liệu dưỡng học sinh giỏi C++

1. TÀI LIỆU DƯỠNG HỌC SINH GIỎI C++
2. TÀI LIỆU BỒI DƯỠNG HỌC SINH GIỎI – NGÔN NGỮ LẬP TRÌNH C++ GIỚI THIỆU Trong những năm qua, ngành giáo dục và đào tạo đã tổ chức và triển khai nhiều cuộc thi học sinh giỏi môn Tin học. Về cơ bản, đa số các thầy / cô giáo đang hướng dẫn sử dụng ngôn ngữ lập trình Pascal – Đây là ngôn ngữ đã quá cổ điển và không còn nhận được sự hỗ trợ trên các hệ điều hành mới, đặc biệt là với những màn hình có độ phân giải cao, việc sử dụng công cụ này ngày càng trở lên khó khăn hơn rất nhiều. Tài liệu được xây dựng dựa trên cơ sở các nguồn dữ liệu do các đồng nghiệp cung cấp và một số dữ liệu từ Internet cũng như các kiến thức tác giả đã tìm hiểu, nghiên cứu và phát triển trong quá trình giảng dạy. Hiện tại, công tác thi học sinh giỏi ở Việt Nam đang sử dụng phần mềm Themis để chấm điểm với các ngôn ngữ lập trình được sử dụng là Pascal, C++, Python và Java. Các nội dung INPUT và OUPUT được ghi lại vào tệp *.INP và *.OUT, vì vậy tất cả các bài tập thực hành chúng tôi trình bày theo kiểu đề thi để các em học sinh có thể dễ dàng tiếp cận và tránh được những sai sót trong quá trình làm bài. C++ là ngôn ngữ lập trình hướng đối tượng. Tuy nhiên, tác giả không đề cập đến vấn đề hướng đối tượng, chỉ tập trung vào phần lập trình hướng cấu trúc. Về cơ bản, môn Tin học cũng giống như môn Toán. Chúng ta tập trung chủ yếu vào phần thực hành. Tác giả cũng không đi sâu vào khai thác các vấn đề về lý thuyết mà thông qua các bài tập sẽ giúp cho các em học sinh có thể dễ dàng nắm bắt được các kiến thức thông qua việc giải quyết các bài toán cụ thể. Tài liệu được xây dựng từ những vấn đề đơn giản đến phức tạp theo các nội dung cơ bản của ngôn ngữ lập trình C++. Tác giả rất mong nhận được sự đóng góp ý kiến của quý thầy / cô cũng như các em học sinh tham gia ôn luyện và thi học sinh giỏi bộ môn Tin học khối THCS. Xin trân trọng cảm ơn./.
3. TÀI LIỆU BỒI DƯỠNG HỌC SINH GIỎI – NGÔN NGỮ LẬP TRÌNH C++ MỤC LỤC 1. Giới thiệu ngôn ngữ lập trình C++ ................................................................................................................ 1 2. Môi trường lập trình C++ .................................................................................................................................... 1 3. Các kiểu dữ liệu ......................................................................................................................................................... 2 4. Biến, hằng, các phép toán và toán tử .................................................................................................... 3 5. Hàm ................................................................................................................................................................................... 4 6. Tệp và ghi tệp ............................................................................................................................................................ 5 7. Cấu trúc điều kiện ................................................................................................................................................... 9 8. Vòng lặp ....................................................................................................................................................................... 18 9. Mảng .............................................................................................................................................................................. 35 10. Xâu ký tự (string) ............................................................................................................................................... 55
4. 1. Giới thiệu ngôn ngữ lập trình C++ C++ là ngôn ngữ lập trình phổ biến nhất trên thế giới được phát triển bởi Bjarne Stroustrup. C++ là một phần mở rộng của ngôn ngữ C. Về cơ bản C và C++ gần như là sự tương đồng. C++ cung cấp cho người lập trình khả năng kiểm soát và tối ưu hóa đối với tài nguyên hệ thống và bộ nhớ, được sử dụng để phát triển các hệ điều hành phổ biến như hệ điều hành windows, linus, ios , phát triển giao diện người dùng đồ họa và các hệ thống nhúng. C++ là một ngôn ngữ lập trình hướng đối tượng mang lại cấu trúc rõ ràng cho các chương trình và cho phép mã được sử dụng lại, giảm chi phí phát triển. C++ là nền tảng để phát triển các ngôn ngữ ứng dụng bậc cao hơn như PHP, Java, javascript, C#, ... 2. Môi trường lập trình C++ Để làm việc với C++ bạn cần phải có trình soạn thảo và cài đặt môi trường để biên dịch mã. Ở đây, có một số công cụ hoàn toàn miễn phí và sử dụng phổ biến như Dev C++, Eclipse, Code::Block, Visual Studio Các phần mềm này có sự hỗ trợ cho việc soạn thảo cũng như tạo sẵn môi trường để biên dịch mã C++. Để bắt đầu với C++, chúng ta đến với chương trình Hello World: #include using namespace std; int main() { cout << "Hello World!"; return 0; } Trong đó: - Dòng #include là thư viện được khai báo trong mỗi chương trình C++. Đây là môi trường nhập / xuất (input / output) dữ liệu trong C++. Ngoài ra, với các bài toán chúng ta cần quan tâm đến 2 thư viện toán học đặc biệt quan trọng là cmath và algorithm ngoài ra chúng ta cũng cần bổ sung thêm thư viện cstring để xử lý các bài toán về xâu ký tự. - Dòng using namespace std là không gian tên. Nếu ko có dòng này bạn cần nhập std::cout << “Hello World!”; - Toàn bộ chương trình chính sẽ nằm trong phần: int main() { // Nội dung lệnh return 0; } Lưu ý: - Mọi câu lệnh trong C++ đều kết thúc bằng dấu “;”.
5. - Tất cả các câu lệnh, từ khóa trong C++ đều là chữ in thường. - Để nhập dữ liệu ta sử dụng cin, xuất dữ liệu ta sử dụng cout. Ví dụ: #include using namespace std; int main() { int a; cin >> a; cout << "a = " << a; return 0; } - Nếu bạn bỏ qua không gian tên using namespace std thì câu lệnh nhập / xuất dữ liệu sẽ cần khai báo std: #include int main() { std::cout << "Hello World!"; return 0; } - Hai câu lệnh return 0 và return 1 là hai giá trị trả về duy nhất của hàm main() trong C++. Hai giá trị trả về này của hàm int main() có ý nghĩa như sau: Chúng ta chỉ đinh return 0 để kết thúc chương trình theo cách bình thường (normal termination). Điều đó có nghĩa là kể cả chương trình có xảy ra lỗi hay không, thì C++ vẫn ngầm định là chương trình đã được kết thúc mà không có lỗi xảy ra. Chúng ta chỉ đinh return 1 để kết thúc chương trình theo cách bất thường (abnormal termination). Điều đó có nghĩa là khi chương trình xảy ra lỗi, thì lỗi này sẽ được trả về khi kết thúc chương trình. 3. Các kiểu dữ liệu Với các bài toán xử lý trên C++, chúng ta cần quan tâm một số kiểu dữ liệu như sau: - Kiểu số nguyên int là kiểu dữ liệu thường xuyên sử dụng - Kiểu string, char: khai báo trong những bài toán về xâu ký tự - Kiểu bool: Trả về true (1) hoặc false (0) - Kiểu float, double: trả về kiểu số thực - Kiểu long: Trả về kiểu số nguyên lớn hơn int
6. Tùy theo tình huống và dạng bài tập mà chúng ta sử dụng dữ liệu làm sao cho hợp lý. Có những bài toán yêu cầu về số nguyên lớn ta có thể sử dụng int8_t, int32_t, int64_t để tránh trường hợp file test với số nguyên lớn làm bạn mất điểm do bị tràn số. Còn với những trường hợp không yêu cầu về số nguyên lớn ta có thể sử dụng kiểu thông dụng là int. Các kiểu dữ liệu thường dùng là int, char, string, float, double 4. Biến, hằng, các phép toán và toán tử - Khai báo biến: Việc khai báo biến trong C++ rất đơn giản, cấu trúc chung thường là: Kiểu_dữ_liệu Tên_biến; Hoặc: Kiểu_dữ_liệu biến1, biến2, biến3; Ví dụ: int a, b, c; Bạn hoàn toàn có thể khai báo biến đồng thời với việc gán một giá trị cụ thể nào đó cho biến. Ví dụ: int a = 50, b = 100; Bạn cần phân biệt biến toàn cục và biến cục bộ: Biến toàn cục là biến chạy trong toàn chương trình, còn biến cục bộ chỉ chạy nội bộ trong một hàm. - Khai báo hằng: Việc khai báo hằng cũng giống kiểu khai báo biến Ví dụ: const int a = 50; - Các phép toán: C++ sử dụng các phép toán cơ bản giống như các ngôn ngữ lập trình khác: + Phép cộng: + + Phép trừ: - + Phép nhân: * + Phép chia: / + Phép chia có dư: % - Toán tử: Chúng ta cần lưu ý một số toán tử thông dụng trong C++
7. Toán tử Ý nghĩa Ví dụ == Bằng x == y != Không bằng x != y > Lớn hơn x > y < Nhỏ hơn x < y >= Lớn hơn hoặc bằng x >= y <= Nhỏ hơn hoặc bằng x <= y - Toán tử logic: Chúng ta quan tâm đến 3 toán tử logic thường dùng: Toán tử Ý nghĩa Ví dụ && AND x < 5 && x < 10 || OR x < 5 || x < 4 ! NOT !(x < 5 && x < 10) - Toán tử gán: Giữ vai trò đặc biệt quan trọng trong lập trình. Chúng ta cần chú ý một số phép gán trong C++ dưới đây: Toán tử Ví dụ Tương đương = x = 5 x = 5 += x += 3 x = x + 3 -= x -= 3 x = x - 3 *= x *= 3 x = x * 3 /= x /= 3 x = x / 3 %= x %= 3 x = x % 3 ++ x++ x = x + 1 -- x-- x = x - 1 5. Hàm Hàm là một nhóm các lệnh đi cùng nhau để thực hiện một nhiệm vụ nào đó trong chương trình. Mỗi chương trình C++ có ít nhất một hàm: int main() Cấu trúc: Kiểu_trả_về tên_Hàm(Danh sách tham số) { Thân hàm } Trong đó: Kiểu trả về: Một hàm có thể trả về một giá trị. Kieu_tra_ve là dạng dữ liệu của giá trị mà hàm trả về. Vài hàm cung cấp các hoạt động và không trả về giá trị nào cả. Đó là hàm void. Tên hàm: Đây là tên thực sự của hàm. Tên hàm và danh sách tham số cấu tạo nên dấu hiệu hàm. Danh sách tham số: Khi hàm được gọi, bạn phải truyền vào danh sách các tham số. Một giá trị hướng đến một tham số thực tế. Danh sách tham số có các kiểu, thứ tự và số lượng các tham số của hàm. Các tham số trong hàm là tùy chọn, nghĩa là một hàm có thể không có tham số.
8. Thân hàm: Phần thân của một hàm bao gồm tập hợp các lệnh xác định những gì mà hàm thực hiện. Để gọi hàm, đơn giản là chỉ cần truyền các tham số được yêu cầu cùng với tên của hàm và nếu hàm trả về các giá trị, bạn có thể dự trữ các giá trị trả về. Xét một ví dụ đơn giản về hàm tính tổng hai số: #include using namespace std; int sum(int a, int b) { int ketqua; ketqua = a + b; return ketqua; } int main () { // Khai bao bien cuc bo: int a = 100; int b = 200; int ketqua; // goi ham de tinh tong hai so. ketqua = sum(a, b); cout << "Tong gia tri la: " << ketqua << endl; // goi ham mot lan nua. ketqua = sum(a); cout << "Tong gia tri la: " << ketqua << endl; return 0; } 6. Tệp và ghi tệp Với việc ghi và đọc file chúng ta có thể sử dụng một trong 2 cách: Cách 1: Sử dụng thư viện fstream #include #include using namespace std; int main() { ifstream fin; ofstream fout; int a, b, Tong = 0, Tich = 0; fin.open("Tong.INP",ios::in); fout.open("Tong.OUT",ios::out); fin>>a; fin>>b; fin.close(); fout << a + b << endl; fout << a * b; fout.close(); return 0; }
9. Cách 2: Sử dụng Hàm freopen: #include using namespace std; int main() { int a; freopen("TongChuSo.INP","r",stdin); freopen("TongChuSo.OUT","w",stdout); cin >> a; int c = a % 10; int d = a / 10; cout << c + d; return 0; } Bài tập Bài 1. Nhập số nguyên dương n là số có hai chữ số. Tính tổng các chữ số của n. Ví dụ: PERM.INP PERM.OUT 34 7 Thuật toán: Ta có ̅̅̅ = 10 + . Như vậy: nếu chia số nguyên a cho 10 ta được số dư là b, còn phần nguyên chính là b. Code tham khảo: #include using namespace std; int main() { freopen("PERM.INP","r",stdin); freopen("PERM.OUT","w",stdout); int a; cin >> a; int T = a % 10 + a / 10; cout << T; return 0; } Bài 2. Nhập số nguyên dương N là số có 3 chữ số. Tìm tích các chữ số của N. Ví dụ: TICH.INP TICH.OUT 254 40 Code tham khảo: #include using namespace std; int main() { freopen("TICH.INP","r",stdin); freopen("TICH.OUT","w",stdout); int n;
10. cin >> n; int T = n % 10; n /= 10; T *= n % 10; T *= n / 10; cout << T; return 0; } 푛(푛+1)(푛+2) Bài 3. Nhập số n nguyên dương (n <= 232). Tính S = 3 Ví dụ: TS.INP TS.OUT 7 168 Thuật toán: Để có được các chữ số của N, ta chia lần lượt cho 10 lấy phần nguyên và phần dư, phần dư đầu tiên sẽ là chữ số hàng đơn vị, phần dư lần chia thứ 2 sẽ là chữ số hàng chục và phần nguyên của lần chia thứ 2 sẽ là chữ số hàng trăm. Code tham khảo: #include using namespace std; int main() { freopen("TS.INP","r",stdin); freopen("TS.OUT","w",stdout); int64_t n; cin >> n; int64_t s = n*(n+1)*(n+2) / 3; cout << s; return 0; } Bài 4. Nhập số thời gian là T (giây). Người ta đổi T thành a giờ, b phút, c giây. Hãy tìm a, b, c. Ví dụ: TIME.INP TIME.OUT 6695 1:51:35 Thuật toán: Ta có: 1 giờ = 3600 giây 1 phút = 60 giây - Lấy số giây chia cho 3600 tính được số giờ. - Tiếp tục chia phần dư cho 60 được số phút - Cuối cùng, phần dư còn lại sẽ là số giây. Code tham khảo: