SKKN Rèn luyện kĩ năng, vân dụng và phát triển tư duy lập trình bằng cách phân tích và mở rộng các bài toán đơn giản

PHẦN 1. MỞ ĐẦU
1. Lý do chọn đề tài
Theo chương trình giáo dục phổ thông 2018 được Bộ Giáo dục và Đào tạo ban hành kèm Thông tư số 32/2018/TT-BGDĐT ngày 26/12/2018, môn tin học có triết lí cốt lõi tạo ra một thế hệ mới có tư duy áp dụng công nghệ trong giải quyết các vấn đề thực tế. Vì vậy, những kiến thức về phần giải thuật và lập trình đóng vai trò quan trọng trong chương trình tin học ở bậc Trung học phổ thông.
Để rèn luyện kỹ năng lập trình cho học sinh khá, giỏi trước khi chọn đội tuyển đi thi HSG môn Tin học có rất nhiều cách mà giáo viên có thể áp dụng đối với các đối tượng học sinh khác nhau. Tuy nhiên trong cùng một trường với các đối tượng học sinh khác nhau giáo viên có thể áp dụng nhiều biện pháp khác nhau để rèn luyện kỹ năng lập trình cho học sinh với hiệu quả khác nhau.
Trong quá trình dạy để chọn đội tuyển, bồi dưỡng học sinh giỏi Tỉnh nhiều năm liền tôi đã chọn lựa ra một số dạng bài toán từ SGK cơ bản và phát triển thêm thành các bài toán nâng cao để mở rộng phạm vi kiến thức giúp học sinh dần dần hình thành các kiến thức nâng cao.
Trên cơ sở đó tôi đã mạnh dạn nghiên cứu và lựa chọn đề tài “Rèn luyện kĩ năng, vận dụng và phát triển tư duy lập trình bằng cách phân tích, mở rộng các bài toán đơn giản”.
2. Mục đích nghiên cứu
Mục đích chính của sáng kiến là giới thiệu đến giáo viên và học sinh một số bài toán cơ bản, phân tích và mở rộng các bài toán đó để học sinh dần hình thành các kiến thức nâng cao:
– Phát triển tư duy lập trình, giúp các em học giỏi môn Tin Học đạt kết quả cao.
– Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT.
– Sử dụng NNLT C++  và Python trong chương trình giáo dục phổ thông mới.
3. Nhiệm vụ
Đề tài có nhiệm vụ giải đáp các câu hỏi khoa học sau đây:
– Học sinh có giải quyết được các bài toán đơn giản.
– Giáo viên mở rộng các bài toán đó như thế nào cho phù hợp với năng lực học sinh.
– Những tình huống nào thường gặp trong quá trình dạy học theo phương pháp này.
– Học sinh gặp những khó khăn nào trong quá trình dạy học theo phương
pháp này.
– Các kỹ năng học sinh đạt được nhờ phương pháp dạy học này.
– Kết quả thực nghiệm như thế nào.
4. Đối tượng nghiên cứu
– Học sinh tham gia bồi dưỡng học sinh giỏi Tin học.
– Hệ thống các bài tập từ cơ bản đến nâng cao theo từng chủ đề.
5. Phương pháp nghiên cứu
– Phương pháp điều tra, nghiên cứu tài liệu.
– Phương pháp phân tích, tổng hợp.
– Phương pháp khảo sát thực tiễn.
– Phương pháp tổng kết kinh nghiệm.
6. Phạm vi nghiên cứu
Hệ thống lại các bài tập từ đơn giản đến mức độ tăng dần bằng việc mở rộng các bài toán đó giúp đạt hiệu quả cao trong quá trình chọn đội tuyển và bồi dưỡng học sinh giỏi môn Tin học.
7. Những đóng góp mới của đề tài
– Qua một số năm làm công tác dạy học và bồi dưỡng học sinh giỏi môn tin học tôi thấy dạy học theo phương pháp này học sinh hứng thú học hơn, chất lượng học sinh được tăng lên đáng kể, nhiều học sinh sau khi học  theo phương pháp này đã tự giải quyết được các bài toán khó trong các đề thi cấp tỉnh, tin học không chuyên…
– Đề tài sẽ làm phong phú hơn các phương pháp day học môn tin học tại các trường trung học phổ thông hiện nay.

PHẦN 2. NỘI DUNG NGHIÊN CỨU
1. Cơ sở lý luận
Xây dựng hệ thống các bài tập theo các chủ để chính, mỗi chủ đề có thể chia thành một hoặc nhiều buổi dạy tuỳ vào từng đối tượng học sinh của mình.
Hệ thống các bài tập của mỗi chủ đề theo các mức độ từ cơ bản đến mức độ khó tăng dần tuy nhiên hệ thống bài tập phải liên quan và phải vận dụng được các bài tập cơ bản để giải quyết các bài toán khó hơn.
Cụ thể mỗi chủ đề được thực hiện theo các bước:
Bước 1: Giới thiệu lí thuyết cơ bản của chủ đề
Bước 2: Chọn bài toán cơ bản hoặc bài toán quen thuộc với học sinh để học sinh lập trình (thường là các bài toán trong sách giáo khoa).
Bước 3: Mở rộng bài toán nâng cao ở cấp độ 1 (chỉ cần học sinh lập trình được mà chưa cần quan tâm đến các yếu tố như: quan tâm đến các yếu tố đặc biệt của dữ liệu vào, thời gian, phạm vi giá trị của biến…)
Bước 4: Mở rộng bài toán nâng cao ở cấp độ 2 (quan tâm đến các yếu tố như: các trường hợp đặc biệt của dữ liệu vào, phạm vi giá trị của các biến, thời gian…)
Bước 5: Thực hiện chấm các chương trình bằng phần mềm Themis với cùng một bộ test để so sánh thời gian thực hiện của các thuật toán với cùng một bài toán.
Bước 6: Phân tích và nhận xét sự tối ưu của thuật toán
Bước 7: Mở rộng bài toán để học sinh rèn luyện kỹ năng lập trình và vận dụng các bài tập ở nhà. Thường là những bài toán tương đương đề học sinh giỏi cấp Tỉnh.
2. Cơ sở thực tiễn
Nhiều học sinh có suy nghĩ môn lập trình rất khó và không phải là môn thi tốt nghiệp, đại học nên các em ít lựa chọn tham gia đội tuyển chọn HSG Tỉnh
Qua công tác dạy học nhiều năm tại trường tôi thấy đa số học sinh đều gặp không ít khó khăn trong việc xác định thuật toán để giải một bài toán. Việc giải các bài toán cơ bản trong sách giáo khoa các em có thể giải quyết được tuy nhiên vận dụng để giải các bài toán khó hơn lại gặp rất nhiều khó khăn.
Nhiều giáo viên đang lúng túng trong việc chọn học sinh có kĩ năng và tư duy lập trình để bồi dưỡng thêm.
3. Các biện pháp sử dụng để giải quyết vấn đề
3.1. Chủ đề về số nguyên tố
3.1.1. Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.

3.1.2 Bài toán cơ bản
Bài toán: Viết chương trình nhập vào từ bàn phím số nguyên N, Kiểm tra và thông báo ra màn hình N là số nguyên tố hoặc N không là số nguyên tố.  Nhận xét: Đây là bái toán cơ bản mà học sinh đã được làm quen ở bài 4: Bài toán và thuật toán lớp 10. Học sinh có thể vận dụng khái niệm của số nguyên tố để đưa ra các thuật toán. Tuy nhiên cách được giới thiệu trong SGK Tin học 10 là tối ưu nhất. Chương trình cụ thể như sau:
C++ Python
#include<iostream> #include<math.h> using namespace std; bool check(int n) {     if (n <= 1) return false;     for (int i = 2; i <= round(sqrt(n)); i++)
if (n % i == 0)             return false;     return true;
} int main() {     int n;
cout<<“nhap n=”;     cin>>n;     if (check (n)) cout<<n<<” la so nguyen to”;         else cout<<n<<” khong la so nguyen to”; return 0;
} import math def check_prime_number(n):
flag = 1;     if (n<2):         flag = 0         return flag     for p in range(2,round(math.sqrt(n))):         if n % p == 0:
flag = 0             break     return flag n = int(input(“>>nhap n: “)) if check_prime_number(n) == 1:
print(n,” la so nt”) else:
print(n,”khong la so nt”)

3.1.3. Bài toán nâng cao cấp độ 1
Bài toán: Viết chương trình nhập vào từ bàn phím số nguyên N, đếm số nguyên tố nhỏ hơn N.
Nhận xét: Khi học sinh đã hiểu và thực hiện được thuật toán kiểm tra số nguyên tố thì học sinh hoàn toàn có thể thực hiện được thuật toán này khi học đến nội dung mảng một chiều.
Thuật toán mà nhiều học sinh lựa chọn nhất là duyệt từ đẩu đến cuối mảng, với mỗi phần tử kiểm tra xem có phải số nguyên tố không. Nếu đúng thì đếm tăng lên 1. Chương trình cụ thể như sau:
C++ Python
#include <iostream>
#include <math.h> #include <fstream> using namespace std; bool KT(int n)
{     bool kt=true;     for (int i=2;i<=round(sqrt(n));i++)         if (n%i==0)         kt=false;     return (kt);
} int main()
{     ifstream fi(“demnt.inp”);     int n;int dem=0;     fi>>n;     ofstream fo(“demnt.out”);     for (int i=2;i<=n;i++)         if (KT(i))         dem++;     fo<<dem;
fi.close();fo.close();
}
import math def ktnt(n):     if (n<2):
return False;     x=int(math.sqrt(n))     for i in range(2,x+1):         if n % i == 0:             return False     return True n = int(input(“>>nhap n: “)) dem=0; if (n>=2):     dem=1; for i in range(3,n+1):     if (ktnt(i)):
dem=dem+1;     i=i+2; print(dem)
3.1.4 Bài toán nâng cao cấp độ 2
Bài toán: Viết chương trình nhập vào từ bàn phím số nguyên N, đếm số nguyên tố nhỏ hơn N.
Nhận xét: Dựa theo lý thuyết về số nguyên tố: “Một số nguyên tố là số chỉ có 2 ước là 1 và chính nó”. Do vậy, nếu ta xác định được số x là số nguyên tố thì ta có thể kết luận mọi số chia hết cho x đều không phải là số nguyên tố. Do đó ta đã loại bỏ được rất nhiều số mà không cần kiểm tra.
Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.
Mã giả (Pseudo Code):
B1: Đánh dấu tất cả các số đều là số nguyên tố.
B2: Với mỗi số nguyên tố nhỏ hơn N
B3: Đánh dấu các bội lớn hơn nó là số nguyên tố.
Chương trình cụ thể như sau:
C++ Python
#include<iostream>
#include<math.h> #include <fstream> using namespace std; int main()
{
ifstream fi(“demnt.inp”); ofstream fo(“demnt.out”); int n; fi>>n;  bool check[n+1] = {};  for(int i=2;i <= round(sqrt(n));i ++ )
{
if(check[i]==0)
{
for(int j = 2*i;j <= n; j += i)
{ def sieve(n):
prime  = [True for i in range(n+1)]     p=2     while (p*p<=n):         if (prime[p] == True):             for i in range(p **2, n + 1, p):
prime[i] = False         p += 1     prime[0] = False     prime[1] = False     for p in range(n+1):
if prime[p]:             print(p)
n = int(input(“>>nhap n = “)) print(sieve(n))
check[j] = 1;
}
}
}
int dem=0;  for(int i=2;i<=n;i ++)
{
if(check[i]==0)         dem++;
}
fo<<dem;
fi.close();fo.close();
}
3.1.5. Đánh giá thuật toán
So sánh thời gian thực hiện của bài toán nâng cao cấp độ 1 và bài toán nâng cao cấp độ 2 qua phần mềm Themis

Test <100 1000 3000 10000 5000
Cách 1 0,20509 0,19380 0,19923 0,22808 0,20207
Cách 2 0,19180 0,18969 0,19708 0,19007 0,1909
Nhìn vào thời gian thực hiện của từng thuật toán nhận thấy thuật toán sàng nguyên tố có thời gian thực hiện nhanh hơn, điều này sẽ có lợi hơn khi thực hiện các test lớn.
3.1.6 Các bài toán giao về nhà
3.1.6.1. Thừa số nguyên tố
Bài toán: Cho số tự nhiên 2<= n <= 105. Hãy phân tích n ra tích của các số nguyên tố theo thứ tự tăng dần.
Nhận xét: Tại mỗi bước ta phải tìm số nguyên tố nhỏ nhất mà N chia hết cho số đó. Do đó, ta phải biến đổi sàng Eratosthenes để tìm được số mình mong muốn trong O(1)O(1).
Cài đặt thuật toán:
C++ Python
#include <iostream> using namespace std;   int main(){     int n;
cout << “\nNhap n = “;     cin >> n;     int dem;

for(int i = 2; i <= n; i++){         dem = 0;         while(n % i == 0){
++dem;             n /= i;
}         if(dem){             cout << i;             if(dem > 1) cout << “^” << dem;
if(n > i){                 cout << ” * “;
}
}
}
} n = int(input(“Nhập số cần phân tích:
“)) a = n i = 2 while a != 1:     if a % i == 0:
print(“%5d %c %2d” % (a, chr(9474), i))         a = a/i     else:
i = i+1
print(“%5d %c” % (1, chr(9474)))
3.1.6.2. Số nguyên tố tương đương
Bài toán: Hai số gọi là nguyên tố tương đương nếu chúng có cùng các ước số nguyên tố. Ví dụ 15 và 75 là các số nguyên tố tương đương. Bởi vì 15=3*5 trong khi 75=3*5^2, có cùng ước số nguyên tố là 3 và 5. Tương tự 12=2^2*3 và 18=2*3^2 là hai số nguyên tố tương dương vì có cùng hai ước số nguyên tố là 2 và 3. Tuy nhiên 12 và 60 ko nguyên tố tương đương vì 12=2^2*3 và 60=2^2*3*5, 60 có ước số nguyên tố 5 trong khi 12 không có.
Cho trước hai số tự nhiên M và N. Hãy viết chương trình kiểm tra các số này có là nguyên tố tương đương với nhau không?

Cài đặt thuật toán:
C++ Python
#include <bits/stdc++.h> #include <math.h> using namespace std; typedef int Mang[1001]; int m,n,dem,d; Mang a,b; bool SNT(int n)
{
bool kt=true;  if (n<=1) kt=false;  else
for (inti=2;i<=round(sqrt(n));i++)    if (n % i==0)
{      kt=false;      break;
}
return kt;
} bool NTTD (int m,int n)
{
bool kttd;
d=0; import sys def SNT(n):     kt=True     if n<=1: kt=True     else:
t=int(n/2)         for i in range(2,t+1):             if n%i==0:                 kt=False                 break     return kt def NTTD (m,n):     d=[]     for j in range(2,n+1):
if SNT(j) and (n%j==0):             d.append(j)     dem=[]     for k in range(2,m+1):         if SNT(k) and (m%k==0):
dem.append(k)     s=0     if len(d)==len(dem):         for i in range(0,len(d)):

for (int j=2;j<=n;j++)
if (SNT(j) && (n % j==0))
{  d++;
a[d]=j;
}  dem=0;
for (int k=2;k<=m;k++)
if (SNT(k)&&(m % k==0))
{
dem++;  b[dem]=k;
}
int s=0;  if (d==dem)  for(int i=1;i<=d;i++)
if (a[i]==b[i])  s++;  if (s==d) kttd=true;  else kttd=false;  return kttd;
} int main()
{
cout<<“Nhap M=”; cin>>m;  cout<<“Nhap N=”; cin>>n;
if (NTTD(m,n))  cout<<“La so nguyen to tuong duong”;         else cout<<“Khong phai la so nguyen to tuong duong”;  return 0;
}             if d[i]==dem[i]: s=s+1     if s==len(d): kttd=True     else: kttd=False     return kttd
m=int(input(“<<Nhap M=”)) n=int(input(“<<Nhap N=”)) if NTTD(m,n): print(“La so nguyen to tuong duong”) else: print(“Khong phai la so nguyen to tuong duong”)
3.1.6.3. Số siêu nguyên tố
Bài toán: Số siêu nguyên tố là số:
• Bản thân nó là số nguyên tố.
• Khi xóa đi lần lượt các chữ số sau cùng của nó, thì số mới vẫn là số nguyên tố.
Ví dụ 2393 là số siêu nguyên tố vì 2393, 239, 23, 2 là số nguyên tố.
Cho một số n, hãy đưa dãy số siêu nguyên tố nhỏ hơn hoặc bằng n, các số đã được sắp xếp tăng dần.
Cài đặt thuật toán:
C++ Python