PHẦN MỞ ĐẦU
Lí do chọn đề tài
Trong chương trình tin học lớp 11, học sinh được làm quen với ngôn ngữ lập trình Pascal, một ngôn ngữ lập trình bậc cao với cú pháp và cấu trúc dữ liệu chặt chẽ Việc học Pascal không chỉ giúp học sinh phát triển tư duy logic mà còn rèn luyện kỹ năng làm việc và giải quyết vấn đề một cách hệ thống.
Trong quá trình giảng dạy, giáo viên cần truyền cảm hứng cho học sinh để phát triển đam mê với môn tin học, từ đó khuyến khích các em tìm tòi, học hỏi Mỗi giáo viên có phương pháp bồi dưỡng học sinh giỏi riêng, nhưng đều nhằm mục đích giúp học sinh nắm vững thuật toán và kiến thức cơ bản để giải quyết các bài toán nâng cao Trong chương trình tin học lớp 10, khi nghiên cứu về thuật toán, học sinh đã làm quen với việc kiểm tra số nguyên dương có phải là số nguyên tố hay không Tuy nhiên, nhiều học sinh, kể cả những em học giỏi, gặp khó khăn trong việc xây dựng thuật toán cho bài toán này và thường chỉ đưa ra ý tưởng giải quyết mà không tối ưu Do đó, để phát triển tư duy cho học sinh giỏi trong việc giải các bài toán về số nguyên tố, giáo viên cần hướng dẫn các em có ý tưởng tốt và nắm vững phương pháp giải cơ bản, từ đó liên kết các dạng bài liên quan và dạy từ cơ bản đến nâng cao theo từng chuyên đề.
Xuất phát từ quá trình bồi dưỡng học sinh giỏi hàng năm, tôi đã phát triển sáng kiến kinh nghiệm mang tên “Chuyên đề về số nguyên tố trong bồi dưỡng học sinh giỏi môn tin học”, nhằm nâng cao kiến thức và kỹ năng cho học sinh trong lĩnh vực này.
Điểm mới của đề tài
Sáng kiến này tập trung vào việc phát triển thuật toán và chương trình giải quyết các bài toán liên quan đến số nguyên tố thông qua việc nhận thức và phân tích Trong quá trình giảng dạy, khảo sát học sinh cho thấy hầu hết đều có ý tưởng về cách kiểm tra tính nguyên tố của một số nguyên dương, nhưng những ý tưởng này cho thấy các em chưa chú trọng đến phạm vi giá trị dữ liệu cần kiểm tra.
Đề tài này nhằm thúc đẩy tính tích cực của học sinh trong việc học lập trình và giải quyết các bài toán chuyên đề Qua đó, học sinh sẽ phát triển tư duy lập trình và nắm vững kiến thức cần thiết, đồng thời giúp giáo viên nâng cao khả năng giảng dạy và ôn thi học sinh giỏi Việc xây dựng chương trình có thể gặp một số lỗi, nhưng điều này sẽ tạo cơ hội cho học sinh rèn luyện kỹ năng thực hành và cải thiện khả năng giải quyết vấn đề.
Hiệu quả và chất lượng dạy học phụ thuộc vào nhiều yếu tố, trong đó nhận thức của giáo viên về vấn đề, sự chuẩn bị kiến thức và phương pháp giảng dạy là rất quan trọng Việc hiểu và phân tích đúng đắn sẽ giúp giáo viên xây dựng chương trình giảng dạy hiệu quả Bài viết này hy vọng sẽ cung cấp định hướng cho đồng nghiệp trong việc nâng cao chất lượng giảng dạy môn Tin học và ôn thi học sinh giỏi.
NỘI DUNG
Cơ sở lí luận
Ngôn ngữ lập trình Pascal là một ngôn ngữ lập trình có cấu trúc, nổi bật với cú pháp chặt chẽ và quy tắc dữ liệu rõ ràng, thuộc tập con của ngôn ngữ máy tính chuẩn hóa Khi phát triển chương trình bằng Pascal, người lập trình cần tuân thủ nghiêm ngặt các quy định về bộ nhớ và cấu trúc dữ liệu Đặc biệt, trong các bài học sinh giỏi, phạm vi giá trị dữ liệu của biến và số lượng biến thường rất phức tạp, đòi hỏi học sinh phải áp dụng các phương pháp xử lý hiệu quả để đảm bảo chương trình chạy đúng kết quả.
Việc áp dụng phương pháp và kỹ thuật xử lý dữ liệu lớn trong lập trình Pascal giúp giải quyết các bài toán khi dữ liệu vượt quá giới hạn của ngôn ngữ này Điều này không chỉ hỗ trợ học sinh và giáo viên trong việc học lập trình hiệu quả mà còn góp phần bồi dưỡng năng lực cho học sinh giỏi.
Thực trạng của vấn đề
Bộ môn Tin học lớp 11 được thiết kế nhằm phát triển tư duy lập trình cho học sinh, tuy nhiên, trong quá trình ôn thi học sinh giỏi, cần tập trung vào lập trình trong môi trường Pascal hoặc Free Pascal Do đó, phương pháp dạy học sẽ có sự khác biệt so với việc ôn thi học sinh giỏi, đòi hỏi sự cụ thể và chuyên sâu hơn trong nội dung lập trình.
Nhiều trường THPT trong tỉnh và trên toàn quốc đang đối mặt với tình trạng cơ sở vật chất thiếu thốn, ảnh hưởng đến chất lượng giáo dục Trang thiết bị của các nhà trường còn nhiều hạn chế, cần được cải thiện để đáp ứng nhu cầu học tập của học sinh.
5 download by : skknchat@gmail.com thốn, thời gian ôn luyện học sinh giỏi cũng chưa được nhiều.
Nhà trường hiện có 03 giáo viên tin học đạt chuẩn, trẻ tuổi và có năng lực Tuy nhiên, ý thức học hỏi và nâng cao trình độ chuyên môn của các giáo viên này vẫn chưa thực sự tích cực.
Hầu hết học sinh đều đến từ nông thôn, nhưng sự phát triển kinh tế địa phương đã giúp họ tiếp cận máy tính và Internet nhiều hơn Môn Tin học, mặc dù mới mẻ và có ứng dụng thực tiễn cao, đã thu hút sự quan tâm của học sinh, khiến các em tích cực tham gia xây dựng bài và tìm hiểu Tuy nhiên, môn học này cũng khó khăn do liên quan đến nhiều lĩnh vực khoa học khác nhau, dẫn đến kết quả học tập chưa cao, đặc biệt là đối với học sinh giỏi.
Kết quả bồi dưỡng học sinh giỏi
Năm học 2015-2016 có 2 giải KK
Năm học 2016-2017 có 2 giải KK
Năm học 2017-2018 có 1 giải nhì, 1 giải ba và 1 giải khuyến khích
Nội dung và giải pháp thực hiện
Trước hết tôi đã đưa ra bài toán như sau:
Bài toán kiểm tra tính nguyên tố của một số nguyên dương là một khái niệm cơ bản trong sách giáo khoa tin học lớp 10 Theo định nghĩa, một số nguyên dương N được coi là số nguyên tố nếu nó chỉ có hai ước số khác nhau, đó là 1 và chính nó Từ định nghĩa này, chúng ta có thể phát triển thuật toán để xác định tính nguyên tố của một số.
- Nếu N=1 thì N không là số nguyên tố
- Nếu 1 [ ] thì thông báo N là 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.
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên
Chia Chia Chia hết hết Không Không Không Không hết Không không? không? a) 29 là số nguyên tố b) 45 không là số nguyên tố
Trên cơ sở thuật toán ta tiến hành cài đặt thuật toán cho bài toán gốc như sau:
If N=1 then begin nt:= false; exit end;
If (N=2) or (N=3) then begin nt:=true; exit end;
If ( N mod k =0) then begin nt:se; exit ; end; nt:=true; end;
7 download by : skknchat@gmail.com Đây là chương trình con kiểm tra 1 số nguyên dương bất kỳ có phải là số nguyên tố ?
Hàm nt(N) thực hiện kiểm tra từng số nguyên k từ 2 đến phần nguyên căn bậc 2 của N Để cải thiện hiệu suất, cần giảm thiểu số lượng các số cần kiểm tra.
Thay vì kiểm tra tất cả các số k, chúng ta chỉ cần xem xét những số k có đặc điểm tương tự như số nguyên tố Vậy đặc điểm của số nguyên tố là gì?
Tính chất số nguyên tố :
Trừ số 2 và số 3 các số nguyên tố có dạng 6k 1 ( vì các số có dạng 6k 2 thì chia hết cho 2, 6k 3 thì chia hết cho 3).
Từ đó ta có chương trình con: Kiểm tra 1 số nguyên dương bất kỳ có phải là số nguyên tố ? áp dụng tính chất số nguyên tố như sau:
Chương trình 2: function nt(N:longint):boolean; var k,m,i:longint; begin if (N=2) or (N=3) then begin nt:=true; exit; end; if( (N=1) or (N mod 2=0) or (N mod 3 =0)) then begin nt:se; exit; end; k:= -1;
M:=trunc(sqrt(N)); repeat inc(k,6); if (N od k =0) or (n mod (k+2) = 0) then break; until k>M if k>Mthen nt:=true else nt:se; end;
Để giải quyết các bài toán liên quan đến số nguyên tố trong lập trình với dữ liệu lớn, chúng ta cần phát triển một chương trình dựa trên bài toán gốc, lựa chọn chương trình 2 làm nền tảng.
Để giải quyết bài toán gốc với chương trình dạng 2, chúng ta có thể sử dụng dữ liệu với số nguyên dương N lớn hơn, không chỉ giới hạn ở kiểu longint mà nên sử dụng kiểu int64.
The function `nt(N: int64): boolean` determines if a given number `N` is a prime number It first checks if `N` is equal to 2 or 3, returning true for these cases If `N` is 1, or divisible by 2 or 3, it returns false For all other values, it initializes a variable `k` to -1 for further checks.
M:=trunc(sqrt(N)); repeat inc(k,6); if (N od k =0) or (n mod (k+2) = 0) then break; until k>M if k>Mthen nt:=true else nt:se; end;
2.3.2 Các dạng bài toán về số nguyên tố
Bài toán 1 : Viết chương trình liệt kê các số nguyên tố trong đoạn từ [2,N]
Dữ liệu vào: Tệp văn bản nguyento.inp chứa duy nhất số nguyên dương N
Kết quả của bài toán là ghi vào tệp văn bản nguyento.out các số nguyên tố, với mỗi số cách nhau ít nhất 1 ký tự trống và ghi trên cùng một dòng Ý tưởng chính của bài toán này là xây dựng một hàm để xác định các số nguyên tố.
Để xây dựng chương trình liệt kê các số nguyên tố trong khoảng từ 2 đến N, bạn cần sử dụng hàm nt(i) Hàm này sẽ kiểm tra từng giá trị i từ 2 đến N; nếu hàm trả về giá trị đúng, số i sẽ được ghi vào tệp bằng cách sử dụng lệnh write(f2, i, ' ').
Thông qua đoạn chương trình:
9 download by : skknchat@gmail.com
The program begins by defining input and output file names, initializing variables, and setting up text file operations It reads an integer 'n' from the input file and checks if 'n' is a prime number using a function The function first verifies if 'n' is 2 or 3, returning true for these cases It then excludes 1 and even numbers greater than 2, as well as multiples of 3, before calculating the square root of 'n' to optimize the prime-checking process.
The code snippet checks if a number \( n \) is divisible by \( k \) or \( k+2 \) and continues until \( k \) exceeds \( M \) If \( k \) is greater than \( M \), a flag \( nt \) is set to true; otherwise, it is set to false The procedure 'xuly' iterates from 2 to \( n \), writing values to a file if they meet the criteria defined by \( nt \) Finally, the procedure 'dongtep' closes the input and output files.
10 download by : skknchat@gmail.com end; begin doctep; xuly; dongtep; end.
Bài toán 2 : Số siêu nguyên tố
Viết một chương trình để đọc một số nguyên N (0 < N < 10) và xuất ra các số siêu nguyên tố có N chữ số cùng với số lượng của chúng Số siêu nguyên tố được định nghĩa là số nguyên tố có tất cả các chữ số của nó cũng là số nguyên tố.
Dữ liệu vào: Tệp văn bản SNT.INP chứa duy nhất số nguyên dương N
Kết quả: Ghi vào tệp SNT.OUT
- Dòng 1: Ghi các số siêu nguyên tố có N chữ số
- Dòng tiếp theo ghi số lượng các số siêu nguyên tố.
Co 15 so sieu nguyen to
Là số nguyên tố mà khi bỏ một số tùy ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Số 37337 là một ví dụ điển hình của siêu nguyên tố 5 chữ số, vì các số 3733, 373, 37 và 3 cũng đều là nguyên tố Bài toán này đặt ra ý tưởng xây dựng một hàm số nguyên tố.
- Xây dưng hàm kiểm tra số i có phải là số siêu nguyên tố hay không Cụ thể ta xây dựng hàm kiểm tra siêu nguyên tố như sau :
Nếu nt(i):se thì SNT:se ;
Nếu nt(i)=true thì tiến hành giảm giá trị của i bằng cách chia nó cho 10 (i:= i div
10) và lại quay lại kiểm tra i cho đến khi i giảm xuống i=0 then snt:=true; 11 download by : skknchat@gmail.com
Chương trình con kiểm tra xem một số nguyên bất kỳ có phải là số siêu nguyên tố hay không được thực hiện thông qua hàm `snt(i: longint): boolean` Hàm này lặp lại việc chia số nguyên `i` cho 10 cho đến khi `i` bằng 0, và nếu số nguyên đó không phải là số nguyên tố, hàm sẽ thoát Để xác định một số siêu nguyên tố, ta cần một hàm kiểm tra số nguyên dương có phải là số nguyên tố, từ đó dễ dàng xây dựng chương trình con để kiểm tra tính siêu nguyên tố của số đó.
- Xây dựng chương trình con thủ tục ghi vào tệp các số siêu nguyên tố đồng thời ứng với mỗi số là siêu nguyên tố thì đếm
- Ý tưởng ghi các số siêu nguyên tố vào tệp:
+ Trước hết tìm giá trị đầu và giá trị cuối của số có n chữ số
For i:=1 to n-1 do gtd:=gtd*10;
Sau khi xác định giá trị đầu và giá trị cuối, tiến hành kiểm tra các số có n chữ số trong khoảng từ GTD đến GTC Nếu số đó là siêu nguyên tố, ghi lại vào tệp và thực hiện việc đếm số lượng.
Thể hiện qua đoạn lệnh sau:
For i:=gtd to gtc do
If snt(i) then begin write(f2, i,’ ‘); inc(dem); end;
Xây dựng cụ thể chương trình con ghi vào tệp các số siêu nguyên tố đồng thời ứng với mỗi số là siêu nguyên tố thì đếm:
The provided code snippet outlines a procedure for generating and counting prime numbers within a specified range It initializes two long integer variables, `gtd` and `gtc`, setting them to 1 and calculating the upper limit based on the input `n` A loop iterates from `gtd` to `gtc`, checking each number to determine if it is prime using the `snt` function If a number is prime, it is written to a file along with a count of the total prime numbers found, which is displayed at the end of the process.
Chương trình cụ thể với bài toán 2:
Const fi='nguyento.inp'; fo='nguyento.out';
Procedure doctep; begin assign(f1,fi); reset(f1); assign(f2,fo); rewrite(f2); read(f1,n);S end;
Function nt(n:longint):boolean; var k,m,i:longint; begin
Ý nghĩa, phạm vi áp dụng của đề tài
Môn Tin học là một lĩnh vực mới mẻ và đầy thách thức cho học sinh, do tính phức tạp và khả năng ứng dụng rộng rãi của nó trong cuộc sống thực.
Dạy Tin học không chỉ đơn thuần là truyền đạt kiến thức, mà còn cần giúp học sinh nhanh chóng nắm bắt kiến thức và phát triển tư duy lập trình Để đạt được điều này, giáo viên cần nỗ lực và áp dụng phương pháp dạy học sáng tạo, nhằm đáp ứng yêu cầu ngày càng cao của môn học và giúp học sinh có khả năng xử lý bài toán và trình bày thuật toán một cách khoa học và tối ưu.
Lập trình Pascal là công cụ hữu ích trong việc giải quyết các bài toán tin học, và việc đảm bảo chương trình đưa ra kết quả chính xác là rất quan trọng Tuy nhiên, mục tiêu chính là chương trình không chỉ phải đúng mà còn phải hoàn thành trong khoảng thời gian cho phép.
Mở rộng bộ nhớ và tối ưu hóa thời gian thực hiện chương trình là mục tiêu quan trọng trong lập trình, đặc biệt để đáp ứng yêu cầu của các bài toán học sinh giỏi Việc này không chỉ giảm chi phí thực hiện mà còn rất cần thiết cho các bài toán yêu cầu xử lý theo thời gian thực.
Bài viết này chia sẻ kinh nghiệm giảng dạy và bồi dưỡng học sinh giỏi trong môn tin học, đặc biệt là phương pháp giải bài toán tối ưu và mở rộng phạm vi giá trị biến trong chương trình Pascal Những phương pháp này đã được áp dụng hiệu quả tại trường THPT Ninh Châu Tôi hy vọng đồng nghiệp sẽ tham khảo và đóng góp ý kiến để cùng nhau phát triển những phương pháp giảng dạy phù hợp với đặc trưng môn học và nhu cầu của từng đối tượng học sinh.
Kiến nghị, đề xuất
Để cải thiện chất lượng dạy học môn Tin học trong trường học, cần tăng cường đầu tư vào cơ sở vật chất và tổ chức các lớp tập huấn nhằm nâng cao trình độ chuyên môn cho đội ngũ giáo viên.
32 download by : skknchat@gmail.com