Báo cáo Biện pháp Giúp học sinh tiếp cận một số bài toán số học bằng ngôn ngữ lập trình C++ nhằm nâng cao chất lượng học sinh giỏi môn tin học THPT

Nội dung tài liệu: Báo cáo Biện pháp Giúp học sinh tiếp cận một số bài toán số học bằng ngôn ngữ lập trình C++ nhằm nâng cao chất lượng học sinh giỏi môn tin học THPT

1. 5. Phạm vi nghiên cứu Đề tài chủ yếu nghiên cứu giải một số bài toán số học từ cơ bản đến nâng cao bằng ngôn ngữ C++. Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng học sinh giỏi Tin học cho giáo viên và học sinh THPT trên địa bàn toàn tỉnh Hà Tĩnh 6. Tính mới của đề tài - Đề tài nghiên cứu về vận dụng các kiến thức đã học về thuật toán, từ đó viết chương trình trên ngôn ngữ lập trình C++ - Mô tả được thực trạng về vấn đề cấp thiết cho cho học sinh THPT ở cách học lập trình và lựa chọn ngôn ngữ lập trình đặc biệt là trong các kỳ thi học sinh giỏi Tỉnh. Phần 2. NỘI DUNG ĐỀ TÀI 1. Cơ sở lý luận và thực tiễn 1.1. Cơ sở lí luận: C++ được biết đến như là ngôn ngữ mới bao trùm lên C và do Bjarne Stroustrup sáng tác ra vào năm 1980 tai bang New Jersey, Mĩ. Lúc đầu ông đặt tên là “C với các lớp”, tuy nhiên đến năm 1983 thì ông đổi tên thành C++. Trong C++ chẳng những đưa vào tất cả các khái niệm, công cụ của lập trình hướng đối tượng mà còn đưa vào nhiều khả năng mới mẻ cho hàm. Nó có một thư viện hàm chứa mã đối tượng cho những hàm đã được tạo sẵn. Những hàm này thực hiện các tác vụ thường dùng như nhập một chuổi ký tự từ bàn phím (gets()), tính căn bậc hai (sqrt()), ... mà chương trình được viết có thể sử dụng mà không phải viết lại. 1.2. Cơ sở thực tiễn: Qua thực tế giảng dạy ở trường THPT các năm qua, tôi nhận thấy khi học đến chương trình NNLT tin học lớp 11 đa số học sinh đều nhận xét bộ môn này rất khó. Tuy nhiên cũng có một số lượng không nhỏ học sinh rất yêu thích tin học và thích tìm hiểu một số bài toán, cách giải các bài toán bằng NNLT. Trong chương trình phổ thông NNLT Pascal đang được giảng dạy cho HS khối 11, nhưng tôi thấy NNLT C++ rất thuận tiện và có nhiều lợi thế khi dạy bồi dưỡng học sinh giỏi và giúp học sinh giải các bài toán phức tạp thuận tiện hơn. Nội dung vấn đề nghiên cứu Ví dụ: Bài tập đơn giản “Chương trình Hello World” Viết ra màn hình dòng chữ Hello world Một chương trình C++ cơ bản thường được bắt đầu bởi dòng include khai báo thư viện, sau đó là hàm main. Có rất nhiều kiểu dữ liệu trong C++, đối với các bạn mới bắt đầu và để làm các bài tập cơ bản thì nên tìm hiểu trước về kiểu dữ liệu int, long, long long, float, double, long double, char, string, 2
2. 2.1 BÀI TẬP SỐ HỌC 2.1.1 BÀI TẬP VỀ ƯỚC CHUNG LỚN NHẤT (UCLN) Bài 1: Nhập vào 2 số nguyên A và B, viết chương trình tìm ước chung lớn nhất của 2 số đó. Trong bài này chúng ta có thể sử dụng cách giải tìm ước chung lớn nhất trong C++, bằng cách sử dụng thuật toán loại trừ hoặc thuật toán Euclid hoặc bằng hàm gcd có sẵn trong thư viện algorithm của C++ Ví dụ Tìm UCLN bằng phương pháp trừ Ý tưởng của thuật toán này là trừ hai số A và B cho nhau tới khi hai số này bằng nhau. Lúc này ta sẽ tìm được UCLN của 2 số. Các bước triển khai thuật toán sẽ như sau: - Kiểm tra A hoặc B có bằng 0 hay không? Nếu bằng 0 trả về UCLN là A+B. Dừng chương trình. - Lặp cho tới khi A = B. Với mỗi vòng lặp thì biến biến max(A, B) = giá trị max(A, B) - giá trị min(A, B). Input : A = 20, B = 15 Output : 5 3
3. Kết quả chương trình: * Tìm UCLN sử dụng thuật toán Euclid Giải thuật Euclid, hay Thuật toán Euclid là một giải thuật giúp tính UCLN của hai số một cách hiệu quả. Thuật toán Euclid Thuật toán Euclid là một giải thuật giúp chúng ta tìm ước chung lớn nhất của 2 số. Nó được triển khai dựa trên tính chất của UCLN đó là UCLN(A, B) = UCLN(B, A%B). Ý tưởng triển khai thuật toán này sẽ quy nạp cho tới khi A % B = 0. 4
4. Kết quả chương trình: 5 -> Đây là cách tối ưu để giải các bài toán với dữ liệu lớn. * Tìm UCLN bằng hàm có sẵn trong C/C++ Ngoài cách tự viết các hàm tìm uớc chung lớn nhất, chúng ta còn có thể sử dụng hàm gcd có sẵn trong thư viện algorithm của C/C++. Chương trình: Kết quả chương trình: 5 Đây là cách nhanh nhất để giải bài toán trong C/C++, ngoài tìm ước chung lớn nhất thư viện algorithm còn có nhiều hàm hỗ trợ khác cho giải các bài toán như max, min, sort,... Bài 2: Cho dãy A gồm N số tự nhiên. Tìm ước chung lớn nhất của dãy số đó. 5
5. -Dữ liệu vào gồm: + Dòng thứ nhất là số nguyên dương N + Các dòng tiếp theo các phần tử của dãy - Kết qua ra là ước chung lớn nhất của dãy. VD: Nhap N = 5 a[0] = 3 a[1] = 6 a[2] =12 a[3] =15 a[4] =9 Chương trình: Kết quả chương trình: 6
6. 2.1.2 BÀI TẬP VỀ CẤP SỐ CỘNG Bài 1. Viết chương trình nhập số nguyên dương N và dãy số nguyên A1, A2, A3, ,An. Kiểm tra xem dãy vừa nhập có phải là cấp số cộng hay không, Nếu đúng thì ghi số 1, ngược lại ghi số 0. Ví dụ: Dữ liệu vào Kết quả Dữ liệu vào Kết quả 5 1 6 0 3 5 7 9 11 1 3 5 6 8 10 Chương trình: 7
7. Kết quả chương trình: 2.1.3 BÀI TẬP VỀ SỐ NGUYÊN TỐ Định nghĩa Số nguyên tố trong lập trình: Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Hay nói cách khác Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Bài 1. Nhập vào số nguyên dương N, Tìm và đưa ra số nguyên tố lớn hơn N. Ví dụ: Dữ liệu vào Kết quả Dữ liệu vào Kết quả Chương trìn7h: 11 14 17 8
8. Kết quả chạy chương trình: Bài 2: Số nguyên tố đối xứng Một số nguyên dương T được gọi là số nguyên tố đối xứng nếu thỏa mãn các yêu cầu sau: - T là một số nguyên tố - T là một số đối xứng (đọc T từ trái qua phải thu được kết quả giống như đọc T từ phải qua trái). Ví dụ 12321 là 1 số đối xứng. Yêu cầu: cho 2 số nguyên dương A và B (104 ≤ A < B <105 ), hãy tìm số lượng các số nguyên tố đối xứng T thỏa mãn A ≤ T ≤ B Ví dụ: Dữ liệu vào Kết quả 11111 22222 23 Chương trình 9
9. Kết quả chạy chương trình: Bài 3: TÌM SỐ Cho số nguyên dương X, khi đảo ngược trật tự các chữ số của X ta sẽ thu được một số nguyên dương Y, Y được gọi là số đảo ngược của X. Ví dụ: X = 613 thì Y = 316 là số đảo ngược của X. Số nguyên dương Y được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố. Cho hai số nguyên dương P và Q (1 ≤ P ≤ Q ≤ 2 109; Q - P ≤ 105). Yêu cầu: Hãy tìm tất cả các số nguyên dương X nằm thỏa mãn P ≤ X ≤ Q và số đảo ngược của số X là số nguyên tố. Dữ liệu vào: Cho trong file văn bản TIMSO.INP có cấu trúc như sau: - Dòng 1: Ghi hai số nguyên dương P Q, hai số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản TIMSO.OUT trên nhiều dòng, mỗi dòng ghi một số nguyên X tìm dược. Ví dụ: TIMSO.INP TIMSO.OUT 10 19 11 13 14 16 17 Chương trình: 10
10. Kết quả chạy chương trình: 2.1.1 BÀI TẬP VỀ GIAI THỪA Bài 1. Giai thừa của một số được cho bởi công thức sau: n!=1*2* *n Cho số N (N<=2.109) nguyên dương, hãy tính tổng giai thừa các chữ số của nó. Hướng dẫn: Viết 1 hàm tính giai thừa của số nguyên dương N. Sử dụng hàm này để tính tổng giai thừa các chữ số của một số. Ví dụ: Dữ liệu vào Kết quả 123 9 Giải thích: Nhập vào N =123 -> Kết quả: 1!+2!+3! = 9 Chương trình: 12