SKKN Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi

1. MỞ ĐẦ U
1.1. Lý do chon đ̣ ề tài
Chúng ta biết rằng để có kết quả cao trong kì thi tuyển chọn học sinh giỏi môn Tin học nói chung thì phải có vốn kiến thức tốt về thuật toán để giải được các bài toán khó, sau đó học sinh lựa chọn NNLT để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo yêu cầu.
Điều này lại chỉ được hình thành sau khi người học được tiếp xúc với một hệ thống các bài toán được tổ chức cẩn thận, chặt chẽ. Hệ thống này giúp xây dựng được các thói quen tư duy cơ bản cũng như các kỹ thuật cơ bản trong lập trình.
Với mong muốn giúp các em giải các bài toán trong Tin học theo hướng tối ưu nhất, qua quá trình bồi dưỡng học sinh giỏi, chúng tôi đã phát hiện, rút ra được một số kỹ thuật cơ bản, rất quan trọng giúp đạt hiệu quả cao trong bồi dưỡng kiến thức, kỹ năng lập trình cho học sinh.
Mặt khác, theo chương trình mới của Bộ giáo dục khuyến khích giáo viên dạy NNLT mới thay Pascal nên chúng tôi viết chương trình bằng NNLT C++ và Python để làm tài liệu tham khảo mới cho giáo viên và học sinh.
Từ những lý do trên chúng tôi đã mạnh dạn triǹ h bày sáng kiến kinh nghiêm: ̣
“Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi”.
1.2. Muc đ̣ í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ố kỹ thuật cơ bản dành cho đối tượng HSG khối THPT:
– 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 2018 sắp tới.
1.3. Đối tương nghiên c̣ ứ u
– Giáo viên và học sinh tham gia bồi dưỡng HSG Tin học.
– Tổng hợp lại một số kỹ thuật giúp học sinh phát triển tư duy lập trình thông qua hệ thống các bài tập được phân loại kỹ lưỡng.
1.4. 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.
1.5. Phạm vi nghiên cứu
Phạm vi nghiên cứu: Một số kỹ thuật cơ bản để tăng tốc chương trình giúp đạt hiệu quả cao trong bồi dưỡng HSG môn Tin học.
2. NÔI DUNG NGHIÊN C̣ Ứ U
2.1. Cơ sở lý luâṇ
Trong quá trình ôn luyện đội tuyển, học sinh được dạy khá nhiều về các phương pháp tối ưu thuật toán như: phương pháp tham lam, chia để trị (sắp xếp nhanh, chặt nhị phân…), quay lui, quy hoạch động, Z Algorithm, KMP… Nhưng nếu không biết kết hợp với những kỹ thuật khác, không biết cách tổ chức dữ liệu, những phương pháp này xét về phương diện độc lập sẽ không đạt được sự tối ưu cao nhất và không có ý nghĩa.
Các kỹ thuật được giới thiệu trong sáng kiến đều là những kỹ thuật rất cơ bản, đơn giản và rất dễ tiếp cận đồng thời đem lại một hiệu quả rất đáng kể trong việc giảm độ phức tạp thuật toán, tiến tới một thuật toán tối ưu nhất.
Học sinh dần được làm quen với NNLT C++ hoặc Python.
2.2. Thực trạng
Trên thực tế đã có một số tài liệu đề cập đến những kỹ thuật để tăng tốc chương trình, tuy nhiên chưa đi sâu vào phân tích cách tư duy, cách lựa chọn và cài đặt chương trình tối ưu, đặc biệt việc tổng hợp lại các kỹ thuật giúp học sinh có thể so sánh các cách giải, các kết quả, độ phức tạp còn rất ít, hệ thống bài tập cũng không nhiều.
2.3. Các kĩ thuật lập trình cơ bản
2.3.1. Kỹ thuật lính canh (Sentinel)
– Là kĩ thuật sử dụng 1 biến (mang giá trị đặc biệt) làm “chốt chặn”.
– Mục đích chính: tạo điều kiện dừng cho các vòng lặp không xác định số lần lặp.
– Xét một số bài toán cụ thể sau:
2.3.1.1. Bài toán 1 – Tìm max / min
Cho dãy gồm N số nguyên a1, a2,…,aN. Hãy tìm giá trị  lớn nhất của dãy số. a. Ý tưởng của thuật toán
– Xét bài toán tìm kiếm giá trị lớn nhất trong một mảng số, đặt biến kết quả max bằng giá trị đầu tiên trong mảng (biến này gọi là biến lính canh), xét lần lượt phần tử thứ 2 đến n, nếu có một phần tử nào lớn hơn “lính canh” ban đầu thì thực hiện đổi “lính canh”:
+ Khởi tạo max=a1;
+ Lần lượt với i=2 đến n, so sánh số ai với max, nếu ai > max thì gán max=ai.
b. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật:
Bước 1: Nhập N và dãy a1, a2, …, aN.
Bước 2: Max ← a1, csmax←1, i ←2;
Bước 3: Nếu i > N thì đưa ra giá trị Max và csmax rồi kết thúc;
Bước 4: Nếu ai > Max thì Max ←ai, csmax ←i;
Bước 5: i ← i + 1 rồi quay lại Bước 3; Cài đặt chương trình:
C++ Python
#include<iostream> #include<fstream> using namespace std; long long n,max,csmax; long long a[10000]; void doctep()
{ifstream fi (“max.inp”); fi>>n; for (int i=0;i<n;i++) fi>>a[i]; fi.close();
}
void maxday()
{
long long max=a[0];//dat linh canh csmax=0; for(int i=1;i<n;i++)  if (max<a[i])  {max=a[i];  csmax=i;
}
ofstream fo (“max.out”); import sys fi=open(“max.inp”,encoding=”utf-8″) fo=open(“max.out”,”w”,encoding=”utf-
8″) sys.stdin=fi sys.stdout=fo
# đọc dữ liệu từ tệp n=int(input()) ds=str.split((input()))
# Đổi các phần tử sang kiểu số nguyên for i in range(n):     ds[i]=int(ds[i]) fi.close()
# tìm phần tử lớn nhất lonnhat=ds[0] # khai báo lính canh,
gán giá trị ban đầu cho biến csmax=0 for i in range(1,len(ds)):
if ds[i]>lonnhat:
lonnhat=ds[i] # cập nhật lại giá trị lính canh         csmax=i print(csmax)
fo<<csmax<<“\n”;  fo<<max;
fo.close();
} int main() {doctep(); maxday(); return 0;
} print(lonnhat) fo.close()
2.3.1.2. Bài toán 2- Tìm kiếm tuần tự
Cho dãy gồm N số nguyên khác nhau a1, a2,…, aN và số nguyên K. Hãy cho biết trong dãy có hay không phần tử ai=k với 1<=i<=N. Nếu có thì đưa ra chỉ số i mà ai=k, nếu không có thì ghi -1.
a. Ý tưởng của thuật toán
Thuật toán tìm kiếm tuần tự (Sequential Search) là một kỹ thuật tìm kiếm đơn giản. Tư tưởng của thuật toán là: Bắt đầu từ phần tử đầu tiên, lần lượt so sánh khóa tìm kiếm với các phần tử trong dãy, cho tới khi tìm thấy phần tử có giá trị bằng khóa tìm kiếm hoặc đã duyệt hết dãy mà không thấy. Thuật toán tìm kiếm tuần tự dễ thực hiện nhất đối với thông tin lưu trữ dạng mảng.
Thường thì các bạn sẽ sử dụng vòng lặp for để duyệt hết mảng, vòng lặp for như sau:
for (i=0; i<n; i++)
{     if (a[i] == k)
{
Cs=i+1;        break;
}
}
Với mỗi vòng lặp, máy tính phải thực hiện 1 câu lệnh i++, 2 câu lệnh kiểm tra i<n và a[i]==k.
Bây giờ, nếu ta dùng kĩ thuật lính canh bằng cách thêm k vào cuối mảng rồi cài đặt lại vòng lặp như sau:
a[n] = k; // gán lính canh vào cuối mảng for (i=0; ; i++)
{         if (a[i] == k)
{

Cs=i+1;
break; }
}
Như vậy, mỗi vòng lặp for đã giảm được 1 câu lệnh kiểm tra i<n, chương trình sẽ chạy nhanh hơn. Đó chính là ưu điểm của việc sử dụng lính canh.
b. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật:
Bước 1. Nhập N, các số hạng a0,…a2,…, aN-1 và khoá k; Bước 2. i ←0, aN ←k;
Bước 3. Nếu ai= k thì thông báo chỉ số i, rồi kết thúc;
Bước 4. i ← i+1;
Bước 5. Nếu i =N thì thông báo dãy A không có số hạng nào có giá trị nào bằng k, rồi kết thúc;
Bước 6. Quay lại bước 3.
Cài đặt chương trình:
C++ Python
#include<bits/stdc++.h> #include<fstream> using namespace std; const long long maxn=50000; long long k,i,n,cs; long  long a[maxn]; void doctep()
{ ifstream fi (“tk.inp”); import sys fi=open(“tk.inp”,encoding=”utf-8″) fo=open(“tk.out”,”w”,encoding=”utf-
8″) sys.stdin = fi sys.stdout = fo
# đọc dữ liệu từ tệp a = str.split(input()) n = int(a[0])
fi>>n>>k;               //dữ liệu vào: dòng đầu lưu hai số nguyên n và k for (i=0;i<n;i++)  //dòng thứ hai
lưu n số nguyên   fi>>a[i]; fi.close();
} int main()
{ doctep();
ofstream  fo (“tk.out”); a[n]=k;//đặt lính canh vào cuối
mảng
for (i=0;;i++)
{
if (a[i]==k)
{
cs=i;
Break;
}
}
if (i==n) fo<<-1;//trường hợp không có ghi -1 else fo<<cs;//nếu có đưa ra chỉ số
phần tử có giá trị =k fo.close(); return 0;
k = int(a[1]) ds = str.split((input()))
#  thêm lính canh vào cuối danh sách ds.append (k)
# đổi các phần tử sang kiểu số nguyên n = len(ds) for i in range (n):     ds[i] = int (ds[i]) fi.close()
# tìm kiếm phần tử có giá trị = k for i in range(n):     if ds[i]==k:
cs = i         break if i==n-1:     print(-1) else:
print (cs) fo.close()

Đánh giá:
Trong lập trình, kỹ thuật đặt lính canh khá cơ bản, chủ yếu áp dụng trong các bài tìm kiếm giá trị lớn nhất hoặc nhỏ nhất, hoặc làm điều kiện dừng vòng lặp với số lần chưa biết trước. Nó đảm bảo được tính chính xác trong thuật toán tổng quát.
2.3.2. Kỹ thuật đặt cờ hiệu (Flag)
– Là kĩ thuật sử dụng 1 biến (mang giá trị đúng/ sai) làm “dấu hiệu” đánh dấu trạng thái.
– Mục đích chính: Kiểm tra một tính chất nào đó.
– Xét một số bài toán cụ thể như sau:
2.3.2.1. Bài toán 1 – Kiểm tra tính chất một số
Cho số nguyên dương N. Hãy cho biết N có phải là số nguyên tố hay không? a. Ý tưởng của thuật toán
– Ta dùng biến kt có kiểu logic (true, false) để đặt cờ hiệu, ban đầu ta đặt cho lá cờ này một giá trị mặc định là true.
– Kiểm tra, nếu N <=1 thì gán lại kt=false.
– Nếu N > 1 thì  ta sẽ kiểm tra xem N có ước nào thuộc đoạn [2; N/2] hay không? Trong lúc kiểm tra nếu thấy có ước thì cập nhật lại giá trị cờ hiệu (kt=false) rồi dừng kiểm tra.
– Cuối cùng, kiểm tra: nếu kt=true thì thông báo N là số nguyên tố, ngược lại thì N không phải nguyên tố.
b. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật:
B1. Nhập số nguyên dương N;
B2. kt ← true;
B3. Nếu N = 1 thì kt ← false rồi chuyển đến bước 8;
B3. i ←2;
B4. Nếu i > [N/2] thì chuyển đến bước 8;
B6. Nếu N chia hết cho i thì kt ← false rồi chuyển đến bước 8;;
B7. i ← i + 1 rồi quay lại bước 4;
B8. Nếu kt= true thì thông báo N là số nguyên tố rồi kết thúc;
B9. Nếu kt=false  thì thông báo N không nguyên tố rồi kết thúc.
Cài đặt chương trình:
C++ Python
#include<bits/stdc++.h> #include<fstream> using namespace std;
long long n; import sys fi=open(“snt.inp”,encoding=”utf-8″) fo=open(“snt.out”,”w”,encoding=”utf8″)

bool kt; void doctep()
{ ifstream fi (“snt.inp”); fi>>n;
fi.close();
} bool ktnt(long long n)
{ kt=true; if (n<=1) kt=false;//dung co hieu kt else
{ for (int i=2;i<n/2;i++)  if (n%i==0) {kt=false; break;} return kt;
}
} void ghitep()
{
ofstream fo (“snt.out”);    if (ktnt(n)) fo<<“yes”;//neu la so nguyen to thi ghi yes   else fo<<“no” ;//nguoc lai ghi no fo.close();
}
int main()
{ doctep();ghitep(); return 0;
} sys.stdin=fi sys.stdout=fo
#đọc dữ liệu từ tệp n=int(input())            kt=True             # Đánh dấu cờ hiệu if n<=1: kt=False   # Cập nhật cờ hiệu else:     for i in range(2,n//2+1):         if n%i==0:             kt=False             break            if kt: print(“yes”) else: print(“no”) fo.close()