Phân tích và tối ưu thuật toán “kiểm tra tính nguyên tố của một số nguyên dương” trong chương trình Tin học 10

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT HẬU LỘC I
SÁNG KIẾN KINH NGHIỆM
PHÂN TÍCH VÀ TỐI ƯU THUẬT TOÁN
“KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNG”
TRONG CHƯƠNG TRÌNH TIN HỌC 10
Người thực hiện: Phạm Ngọc Cường
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT Hậu Lộc 1
SKKN thuộc lĩnh vực: Tin học
THANH HOÁ, NĂM 2017
MỤC LỤC
1. Mở đầu	Trang 1
1.1. Lí do chọn đề tài	Trang 1
1.2. Mục đích nghiên cứu	Trang 1
1.3. Đối tượng nghiên cứu	Trang 1
1.4. Phương pháp nghiên cứu	Trang 1
2. Nội dung	Trang 2
2.1. Cơ sở lí luận	Trang 2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm	Trang 2
2.3. Hiệu quả của sáng kiến kinh nghiệm	Trang 2
2.3.1 Tối ưu thuật toán	Trang 4
2.3.2 Phân tích ý tưởng và thuật toán	Trang 5
2.4. Kết quả đạt được	Trang 6
3. Kết luận, kiến nghị	Trang 6
3.1 Kết luận	Trang 6
3.2. Kiến nghị	Trang 6
Tài liệu tham khảo	Trang 8
1. MỞ ĐẦU
1.1. Lí do chọn đề tài
Hiện nay, kiến thức Tin học lớp 10 nói chung và nội dung bài dạy “Bài toán và thuật toán” (Bài 4 – trang 32 SGK) nói riêng gây không ít khó khăn cho học sinh khi các em phải làm quen với những khái niệm rất mới, rất trừu tượng so với các môn học mà các em đã từng học ở THSC. Phần lớn các em học sinh đều tỏ ra hào hứng khi được học những môn học mới, những kiến thức mới mà đặc biệt là kiến thức tin học đang giữ vai trò quan trọng trong đời sống xã hội. Nhưng cũng chính các em lại tỏ ra chán nản, mệt mỏi sau khi học bài này bởi những khái niệm, những kiến thức khá trừu tượng và khó hiểu, với những học sinh học kém về khoa học tự nhiên lại càng không biết gì.
Từ mâu thuẫn đó đã gây nhiều khó khăn cho giáo viên, bởi đây là bài dạy có thời lượng rất dài (4 tiêt). Vì vậy, vai trò của người giáo viên giúp học sinh tiếp cận kiến thức một cách đơn giản, dễ hiểu và có hứng thú là cực kỳ quan trọng. Không chỉ ảnh hưởng trực tiếp đến bài dạy mà còn ảnh hưởng đến tâm lí học bài của học sinh trong suốt chương trình.
Sách giáo khoa Tin học 10 đã xuất bản được hơn 10 năm (từ năm 2006) nhưng vẫn còn tồn tại một số nội dung, khía cạnh nhỏ mà theo tôi cần phân tích rõ hơn và nên làm đơn giản hơn để học sinh dễ hiểu. 
Đó là lí do khiến tôi chọn đề tài: “Phân tích và tối ưu thuật toán kiểm tra tính nguyên tố của một số nguyên dương” (Ví dụ 1, mục 3, bài 4 – SGK tin học 10).
Đây là vấn đề đã quá quen thuộc, học sinh đã được học ở THCS nhưng khi học thuật toán thì hầu như đa số các em đều không hiểu bài. Thuật toán còn rườm rà và những nội dung chưa được làm rõ. Bản thân đã dạy nhiều khóa lớp 10, khóa học nào tôi cũng đặt ra những câu hỏi tại sao? khi dạy nội dung này nhưng các em đều không trả lời được. Ngay cả khi hỏi một số đồng nghiệp cũng không ai giải thích cho học sinh hiểu.
Từ đó, tôi nhận thấy đề tài mà mình đưa ra là rất cần thiết khi Nhà xuất chưa có những chỉnh lí phù hợp.
1.2. Mục đích nghiên cứu.
Căn cứ vào các lí do trên, nội dung đề tài nhằm mục đích giúp giáo viên dạy hiệu quả hơn, học sinh hiểu bài hơn khi học bài Bài toán và thuật toán, cụ thể là thuật toán “Kiểm tra tính nguyên tố của một số nguyên dương” trong chương trình tin học lớp 10. Từ đó tạo hứng thú, say mê môn học, không còn cảm giác nhàm chán, mệt mỏi vì đây là bài dạy có thời lượng rất dài (4 tiết) và kiến thức tương đối khó đối với học sinh lớp 10.
1.3. Đối tượng nghiên cứu
	Ý tưởng và thuật toán Kiểm tra tính nguyên tố của một số nguyên dương trong chương trình SGK Tin học lớp 10.
1.4. Phương pháp nghiên cứu
 - PP nghiên cứu xây dựng cơ sở lý thuyết
 - PP điều tra khảo sát thực tế, thu thập thông tin.
2. NỘI DUNG
2.1. Cơ sở lí luận
- Dựa trên Sách giáo khoa Tin học 10 để xây dựng cơ sở lí luận
- Dựa trên các sách tài liệu tham khảo và Internet để kiểm chứng.
2.2. Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm
* Đặc điểm tình hình của nhà trường: 
 Trường THPT Hậu Lộc I có bề dày kinh nghiệm và thành tích trong công tác giảng dạy các đội tuyển học sinh giỏi cấp tỉnh cũng như ôn thi đại học. Đội ngũ giáo viên nhiệt tình, tâm huyết với công tác chuyên môn còn các em học sinh đa phần là ngoan, chịu khó, một bộ phận mũi nhọn có tư duy tốt. Là trường có chất lượng giáo dục đứng đầu trong huyện và tốp đầu trong tỉnh nên chất lượng đầu vào khá tốt.
 * Thực trạng của vấn đề “Phân tích và tối ưu thuật toán kiểm tra tính nguyên tố của một số nguyên dương” tại trường THPT Hậu Lộc I là: 
- Về kiến thức: Học sinh mới bắt đầu làm quen với các khái niệm trong Tin học, mới đầu làm quen với thuật toán nên còn rất bỡ ngỡ và mơ hồ.
- Về kỹ năng: Đây là ví dụ đầu tiên về xây dựng thuật toán giải bài toán nên học sinh chưa có kỹ năng về hình thành ý tưởng và xây dựng thuật toán.
- Trong quá trình giảng dạy, tôi thường xuyên đặt ra những câu hỏi yêu cầu học sinh phải tự vận động suy nghĩ tìm ra các cách giải khác nhau cho 1 bài toán cụ thể, từ đó chính học sinh sẽ lựa chọn thuật toán tối ưu nhất. Phân tích, giải thích cho học sinh hiểu
- Thực tế, kết quả khảo sát chất lượng Tin học 10 đầu năm của hai lớp 10A3, 10A4
Lớp
Số bài kiểm tra
Giỏi
Khá
Trung bình
Yếu
Kém
SL
%
SL
%
SL
%
SL
%
SL
%
10A3
47
17
36,2
12
25,6
10
21,3
2
4,3
0
0
10A4
39
8
20,5
10
25,7
16
41
5
12,8
0
0
2.3. Giải pháp thực hiện
Xét Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương (Mục 3, bài 4 – SGK Tin học 10).
Xác định bài toán:
- Input: N là một số nguyên dương;
- Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”
Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó. Từ định nghĩa đó, ta suy ra:
- Nếu N = 1 thì N không là số nguyên tố;
- Nếu 1 < N < 4 thì N là số nguyên tố;
- Nếu N 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố. 
Thuật toán
a) Cách liệt kê:
Bước 1: Nhập số nguyên dương N;
Bước 2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
Bước 3: Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4: i 2;
Bước 5: Nếu i > thì thông báo N là số nguyên tố rồi kết thúc;
Bước 6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
Bước 7: i i+1 rồi quay lại bước 5
Nhập N 
i > ? 
N chia hết 
cho i ?
 i ! 2
N = 1?
Thông báo N 
là nguyên tố
rồi kết thúc
 i ! i + 1
Đúng
Đúng
Sai
Sai
Đúng
Sai
Thông báo N
Không là nguyên tố
rồi kết thúc
N < 4?
Đúng
Sai
b) Sơ đồ khối
2.3.1 Tối ưu thuật toán
Tại bước 3 : Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc
Với N là số nguyên dương thì N < 4 nhận 2 giá trị N = 2 và N = 3 (N = 1 đã xét ở bước 1). Đây là 2 số nguyên tố, tuy nhiên nếu bỏ đi bước 3 thì thuật toán vẫn kiểm tra được N là số nguyên tố khi nhận giá trị là 2 hoặc 3.
Bởi tại bước 4 : i căn N thì thông báo N là số nguyên tố rồi kết thúc ;
Như vậy, nếu N = 2 hoặc N = 3 thì i = 2 luôn lớn hơn căn của 2 và 3. Và theo bước 5 hiển nhiên N là số nguyên tố.
Vậy Sách giáo khoa đưa vào bước 3 là thừa, không những thế làm cho học sinh lúng túng và đặt ra câu hỏi tại sao lại chỉ xét N < 4 mà không xét với số khác
Sau khi bỏ đi bước 3, thuật toán kiểm tra tính nguyên tố của một số nguyên dương N sẽ là :
Bước 1: Nhập số nguyên dương N;
Bước 2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
Bước 3: i 2;
Bước 4: Nếu i > thì thông báo N là số nguyên tố rồi kết thúc;
Bước 5: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
Bước 6: i i+1 rồi quay lại bước 5
Nhập N 
i > ? 
N chia hết 
cho i ?
 i ! 2
N = 1?
Thông báo N 
là nguyên tố
rồi kết thúc
 i ! i + 1
Đúng
Đúng
Sai
Sai
Đúng
Sai
Thông báo N
Không là nguyên tố
rồi kết thúc
Thuật toán này luôn đúng với mọi số N nguyên dương
2.3.2. Phân tích ý tưởng và thuật toán
Tại bước 4 : Nếu i > phần nguyên căn N thì N là số nguyên tố rồi kết thúc
Nếu giáo viên đặt câu hỏi : Tại sao lại xét i từ 2 đến mà không xét 1 đoạn khác thì chắc hẳn rất nhiều học sinh không trả lời được (thậm chí là học sinh học tốt khoa học tự nhiên). Vậy bản chất của ý tưởng xét i trên đoạn này xuất phát từ đâu ?
Ta xét 1 số giá trị của N:
N = 6 : có các ước : 	1	2	3	6
N = 12 : có các ước : 	1	2	3	4	6	12
N = 13 : có các ước :	1	13
Ta nhận thấy : 	6 = 1*6 = 2*3
	12 = 1*12 = 2*6 = 3*4
	13 = 1*13
Tức là nếu N có ước là a thì sẽ có ước là b để a*b = N
Thông thường học sinh hay tìm các ước của N trong đoạn từ 1 đến N rồi sau đó đếm xem N có bao nhiêu ước. Nhưng nếu làm như vậy sẽ lãng phí rất nhiều thời gian, để tối ưu trong việc tìm các ước của N ta tìm 1 giá trị x trong đoạn từ 1 đến N thỏa mãn : nếu trong đoạn có ước là a thì tương ứng trong đoạn có ước là b để a*b = N. Và trong đoạn 1-x có bao nhiêu ước thì trong đoạn x-N cũng có bấy nhiêu ước. 
Như vậy, ta sẽ giảm được việc tìm ước của N trên đoạn 
Vậy giá trị x là bao nhiêu ?
Giả sử trong đoạn có ước là a thì trong đoạn có ước là b và a*b = N. Tăng giá trị a dần đến x đồng thời giảm giá trị b dần về x, và tại vị trí x thì a = b = căn N. Do N là số nguyên dương và các ước của N cũng là số nguyên dương nên a = b = .
Xét một số giá trị cụ thể của N
Với N = 12 : = 3 ta chỉ tìm các ước của N từ 1 đến 3 mà không cần tìm đến 12 cũng kết luận được N không phải là số nguyên tố
Với N = 17 : = 5 ta chỉ cần tìm các ước của N từ 1 đến 5 mà không cần tìm đến 17 cũng kết luận được N là số nguyên tố. 
2.4. Kết quả đạt được
 Thông qua tiến hành nghiên cứu trên lớp 10A3 và 10A4 với đề tài “Phân tích và tối ưu thuật toán kiểm tra tính nguyên tố của một số nguyên dương” tôi đã thu được một số kết quả đó là đa số các em đã hiểu được bản chất vấn đề, hứng thú hơn với môn học và vận dụng vào việc hình thành ý tưởng, xây dựng thuật toán để giải một số dạng toán khác. Do đó kết quả học tập của các em đạt được là rất tốt
 Để chứng minh tôi xin đưa ra một số kết quả sau:
 Kết quả khảo sát chất lượng môn Tin học lớp 10A3 và 10A4
Lớp
Số bài kiểm tra
Giỏi
Khá
Trung bình
Yếu
Kém
SL
%
SL
%
SL
%
SL
%
SL
%
10A3
47
17
36,2
12
25,6
10
21,3
2
4,3
0
0
10A4
39
8
20,5
10
25,7
16
41
5
12,8
0
0
3. KẾT LUẬN VÀ KIẾN NGHỊ
3.1. Kết luận
 Đối với giáo viên, đề tài này sẽ giúp giáo viên dạy học hiệu quả hơn khi mà học sinh ban đầu phải tiếp cận với kiến thức khá mới và trừu tượng, gây được nhiều hứng thú học tập cho học sinh, làm cho bài dạy không còn nhàm chán do thời lượng quá dài với nhiều thuật toán khó. 
Từ kết quả nghiên cứu, tôi đã rút ra các bài học kinh nghiệm sau: để việc dạy học đạt kết quả cao, trước hết phải tạo được hứng thú cho học sinh. Bằng cách cùng các em tìm tòi và xây dựng thuật toán giải chứ không sử dụng ngay thuật toán đã trình bày sẵn trong SGK, tránh tình trạng để các em tiếp thu bài học một cách thụ động. Sẵn sàng tối ưu những thuật toán đã có (ngay cả trong SGK) nếu thuật toán đó vẫn đảm bảo đúng để các em cảm thấy hứng thú hơn, chủ động tìm tòi sáng tạo hơn khi xây dựng thuật toán.
 Giúp giáo viên không ngừng tìm tòi, sáng tạo để nâng cao trình độ chuyên môn và nghiệp vụ sư phạm cho bản thân.
3.2. Kiến nghị
Không
 Tôi xin chân thành cảm ơn!
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 9 tháng 6 năm 2017.
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
Phạm Ngọc Cường
TÀI LIỆU THAM KHẢO
1. Sách giáo khoa Tin học 10 – Nhà xuất bản Giáo dục năm 2006.
2. Tham khảo các thuật toán kiểm tra tính nguyên tố của một số nguyên dương trên Internet.