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

ốt cần có một quá trình nghiên cứu, học tập về ngôn ngữ lập trình và chọn một ngôn ngữ lập trình thích hợp.
Hiện nay có rất nhiều ngôn ngữ lập trình bậc cao như: Pascal, Java, Basic, C, C++,.
Tuy nhiên điều cơ bản của C++ là cho phép người lập trình hiểu và quản lí
các chương trình lớn, phức tạp. Vì vậy, nó được sử dụng nhiều trong các kỳ thi học sinh giỏi Tin học.
Xuất phát từ cơ sở trên, tôi đã chọn đề tài “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”.
Mục đích nghiên cứu
Qua quá trình tham gia giảng dạy, bồi dưỡng học sinh giỏi và việc nghiên cứu các vấn đề về lập trình theo từng dạng bài tập từ cơ bản đến phức tạp của ngôn ngữ lập trình C++, các tài liệu về phương pháp giảng dạy phục vụ cho việc học tập, ôn thi học sinh giỏi của học sinh cũng như giảng dạy của giáo viên, tôi đã giải các bài toán bằng ngôn ngữ lập trình C++ với hệ thống lập trình CodeBlocks. Từ đó, tôi đưa ra đề tài “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 trung học phổ thông” với mong muốn phần nào giúp học sinh cũng như giáo viên có thêm tài liệu tham khảo phục vụ cho việc học tập và giảng dạy, ôn thi HSG.
Đối tượng nghiên cứu
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 trung học phổ thông.
Phương pháp nghiên cứu.
Kinh nghiệm bản thân qua các kỳ ôn thi HSG, nghiên cứu các tài liệu về C++ qua sách tham khảo, mạng internet, sưu tầm tài liệu, thử nghiệm thực tế, rút kinh nghiệm từ các tiết dạy bồi dưỡng HSG.
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
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
Cơ sở lý luận và thực tiễn
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.
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,
BÀI TẬP SỐ HỌC
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
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.
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ố đó.
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:
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ả
5
3 5 7 9 11
1

Dữ liệu vào
Kết quả
6
1 3 5 6 8 10
0

Chương trình:
Kết quả chương trình:
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ả
ìn7h:
11

Dữ liệu vào
Kết quả
14
17

Chương tr
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
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:
Kết quả chạy chương trình:
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:
Kết quả chương trình:
BÀI TẬP VỀ SỐ HOÀN HẢO
Số hoàn hảo được hiểu đơn giản là số có tổng các ước số thật sự của nó bằng chính nó. Ước số thật sự là ước số không bao gồm chính nó.
Ví dụ:
Số 6 là một số hoàn hảo vì tổng các ước số thật sự của số 6 là: 1 + 2 + 3 = 6 (tức là bằng chính nó)
Số 12 không phải là một số hoàn hảo vì tổng các ước số thực sự của số 12 là: 1
+ 2 + 3 + 4 + 6 = 16 (khác với chính nó)
Giải thích thuật toán: giả sử ta có một số a là số cần kiểm tra.
Đầu tiên ta tìm ra các ước số của a, -> ta sẽ cần một vòng lặp For, lặp từ 1 đến a/2 với bước nhảy là 1 (i++).
Tiếp đến tạo một biến Sum, được dùng để tính tổng các ước số của a. Ta tạo một điều kiện trong vòng lặp For, nếu (a % i == 0) thì sum += i
Cuối cùng, kiểm tra nếu sum == a thì a chính là số hoàn hảo và ngược lại.
* Lưu ý: Các ước số của a luôn bé hơn hoặc bằng a/2.
Bài 1. Nhập vào số nguyên n, kiểm tra số vừa nhập có phải là số hoàn hảo không? Ví dụ:
Dữ liệu vào
Kết quả
6
6 La so Hoan Hao

Dữ liệu vào
Kết quả
12
12 Khong la so Hoan Hao

Chương trình:
Kết quả chạy chương trình:
Bài 2:	Cặp đôi hoàn hảo
Cho dãy số nguyên gồm n phần tử a1, a2, an. Hai số ai và aj (i=1, 2,n; j=1, 2,n; i≠j) được gọi là cặp đôi hoàn hảo nếu ai, aj là 2 số nguyên tố. Với dãy số trên tìm số cặp đôi hoàn hảo.
Yêu cầu: Hãy cho biết có bao nhiêu cặp đôi hoàn hảo. Ví dụ: Dãy số a là 3 2 -4 7 thì số cặp đôi hoàn hảo là 3 Dữ liệu vào có nội dung như sau:
Dòng đầu là số nguyên dương n (n≤103)
Trong n dòng sau, dòng thứ i là số nguyên ai (i=1, 2, n; |ai|≤105) Kết quả ghi ra:
Một số nguyên duy nhất là số cặp đôi hoàn hảo.
Ví dụ:
Dữ liệu vào

Kết quả ra
4

3
3


2


-4


7


Chương trình:




BÀI TẬP VỀ SỐ CHÍNH PHƯƠNG
Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương của một số tự nhiên.
Ví dụ:
Số 4 là số chính phương vì 2^2 = 4. (hoặc sqrt(4) = 2).
Tập các số chính phương như sau: CP = {4; 9; 16; 25; ...}. Có các cách để viết thuật toán kiểm tra số chính phương như sau:
Kiểm tra số chính phương bằng vòng lặp.
Kiểm tra số chính phương bằng hàm sqrt() trong thư viện math.h.
.
Thuật toán kiểm tra số chính phương bằng vòng lặp.
Thuật toán:
Lặp i chạy từ 0 đến khi i*i > n. Nếu i * i = n thì n chính là số chính phương, kết thúc chương trình.
Nếu i * i > n thì n không phải là số chính phương.
Thuật toán kiểm tra số chính phương bằng hàm sqrt()
Thuật toán:
Trong thư viện math.h có một hàm được dùng để tính căn bậc hai, đó chính là hàm sqrt()
Chúng ta sử dụng hàm sqrt() để đặt điều kiện cho số n. Nếu sqrt(n) * sqrt(n)
= n, thì n chính là số chính phương và ngược lại.
Bài 1: Viết chương trình nhập vào một dãy gồm n số nguyên. Hãy tìm và in ra màn hình các số chính phương có trong dãy đó.
Ví dụ:
Dữ liệu vào
Kết quả
Nhap n = 6 2
4 5 8 9 14
Cac so chinh phuong: 4 9
Chương trình:
Kết quả chạy chương trình:
BÀI TẬP VỀ SỐ PHONG PHÚ
Bài tập: Đếm số phong phú.
Số phong phú là số có tổng các ước số nguyên của nó kể cả số 1 (không kể chính nó) lớn hơn nó. Ví dụ: Số 6 có tổng các ước 1+ 2+ 3 = 6 không là số phong phú. Số 12 có tổng các ước là 1+ 2+ 3+ 4+ 6 = 16 (Lớn hơn 12) là số phong phú.
Yêu cầu: Hãy cho biết có bao nhiêu số phong phú không lớn hơn N. Dữ liệu vào: Số nguyên N (0< N ≤ 105)
Kết quả: Ghi một số nguyên duy nhất là kết quả tìm được theo yêu cầu. Ví dụ:
Dữ liệu vào
Kết quả ra
ụNtrhêanpcnó:42s4ố pho
n4g phú là 12, 18, 20

Giải thích: Trong ví d
Chương trình:
, 24
Kết quả chạy chương trình:
BÀI TẬP VỀ SỐ ĐẸP
Bài tập:
Một số nguyên dương được gọi là số đẹp khi tổng bình phương các chữ số của nó là một số nguyên tố.
Ví dụ: số 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.
Yêu cầu: Cho số nguyên dương N, có bao nhiêu số đẹp nhỏ hơn hoặc bằng N. Dữ liệu nhập vào gồm một số nguyên dương N (1 ≤ N ≤ 106)
Kết quả ra là số lượng số đẹp nhỏ hơn hoặc bằng N. Ví dụ:
20
Dữ liệu vào
	4
Kết quả ra
Hướng dẫn: Cần viết 2 hàm: Kiểm tra Số đẹp; Kiểm tra nguyên tố. Chương trình:
Kết quả chạy chương trình:
BÀI TẬP VỀ SỐ THÂN THIỆN
Bài tập
Đang tìm hiểu các thuật toán về số tự nhiên, Nguyên phát hiện ra số tự nhiên có rất nhiều tính chất thú vị. Nhiều số tự nhiên khi tìm ước chung lớn nhất với số đảo ngược của nó bằng 1, những số như thế được gọi là số thân thiện. Chẳng hạn số 23, số đảo ngược của nó là 32, hai số này có ước chung lớn nhất là 1 nên số 23 là số thân thiện và 32 cũng là số thân thiện.
Yêu cầu: Cho 2 số tự nhiên a, b (10 ≤ a ≤ b ≤ 104). Hãy đếm xem trong đoạn từ a đến b có bao nhiêu số thân thiện.
Ví dụ:
Dữ liệu vào
Kết quả
Giải thích
19	29
4
Đó là các số: 19, 23, 25, 29
Ý tưởng: Dùng 1 biến Dem để lưu số lượng số thân thiện Xét lần lượt các số tự nhiên i từ a tới b
Với mỗi số i xác định số tự nhiên j là đảo ngược của i Nếu UCLN(i,j)= 1 thì tăng biến Dem lên 1
Kết quả bài toán là Dem Chương trình:
Phần 3. KẾT LUẬN VÀ KIẾN NGHỊ
Kết luận
Ngôn ngữ lập trình nói chung đóng vai trò rất quan trọng trong việc xây dựng các chương trình ứng dụng để phục vụ cho cuộc sống. Nhờ sự phát triển của tin học
trong đó các nhà lập trình chuyên nghiệp đóng vai trò không nhỏ - mà hiện nay hầu hết các lĩnh vực trong xã hội đã ứng dụng được tin học để giải quyết công viêc nhanh, hiệu quả và chính xác hơn.
Hiện nay, ngôn ngữ lập trình C++ đã trở thành ngôn ngữ lập trình phổ biến được sử dụng trong lĩnh vực giảng dạy đặc biệt là bồi dưỡng học sinh giỏi.
Đề tài của tôi trên đây có thể còn chưa hoàn thiện do còn hạn chế về trình độ kiến thức và kinh nghiệm giảng dạy. Vì vậy, tôi rất mong nhận được sự đóng góp ý kiến quí báu của các thầy giáo, cô giáo và các bạn đồng nghiệp để ngày càng hoàn thiện hơn. Tôi xin chân thành cảm ơn!
Kiến nghị
Trong quá trình dạy học, mỗi thầy cô cần cố gắng xây dựng những nội dung khoa học, lựa chọn phương pháp phù hợp, thu hút và tạo hứng thú cho học sinh ham thích môn Tin học. Nội dung của đề tài rất thiết thực và bổ ích cho học sinh học lập trình nói chung, cũng như học sinh ôn thi học sinh giỏi các cấp môn Tin học nói riêng. Vì vậy tôi mong rằng đề tài sớm tiếp cận được các học sinh và các em vận dụng hiệu quả nâng cao trình độ, kiến thức lập trình.
TÀI LIỆU THAM KHẢO
Sách giáo khoa tin học 11	Hồ Sĩ Đàm	chủ biên
Sách giáo viên tin học 11	Hồ Sĩ Đàm	chủ biên
Sách giáo khoa tin học 11_Biên dịch sang C++
Sách tham khảo NNLT C++, Quách Tuấn Ngọc_NXB Thống kê
Tự học lập trình C++, Đinh Hùng, NXB Đà Nẵng
Sách tham khảo NNLT C++ ĐH Đồng Nai
Giáo trình Giải thuật và Lập trình, Lê Minh Hoàng
Lập trình hướng đối tượng với C++, Gs.Phạm-Văn-Ất
Một số sáng kiến kinh nghiệm, nguồn tài liệu về C++ trên internet ...