SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN
TRƯỜNG THPT DIỄN CHÂU 5
SÁNG KIẾN KINH NGHIỆM
ĐỀ TÀI
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
Lĩnh vực: Tin học
Nhóm người thực hiện:
Số điện thoại :
Số điện thoại :
Nguyễn Thị Luận – Trường THPT Diễn Châu 5
0989868255
Email: nguyenluan.dc5@gmail.com
Trần Thị Thủy – Trường THPT Nghi Lộc 4
0848919111
Email: tttpdl@gmail.com
Năm thực hiện :
2022
NGHỆ AN, NĂM 2022
1
1. MƠ
ĐÂ
U
1.1. Ly do cho
n đê tai
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 ly do trên chúng tôi đã mạnh dạn trinh bay sang 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. Mu
c đich 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 pha
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
2. NÔI DUNG NGHIÊN CƯ
U
2.1. Cơ sơ
ly luâ
n
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.
3
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)
4
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: