MỤC LỤC
1. Mở đầu………………………………………………………………………….1
1.1. Lý do chọn đề tài…………………………………………………………...1
1.2. Mục đich nghiên cứu……………………………………………………….1
1.3. Đối tượng nghiên cứu………………………………………………………1
1.4. Phương pháp nghiên cứu…………………………………………………...1
2. Nội dung sáng kiến kinh nghiệm…………………………………………….2
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm…………………………………..2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm……………...2
2.3. Các giải pháp đã sử dụng để giải quyết vấn đề……………….....................3
2.3.1 Cung cấp lý thuyết về chuyên đề dãy con liên tiếp…..…………….....3
2.3.2 Viết chương trình cho 4 bài tập cơ bản…….........................................4
2.3.3 Làm các bài tập thực tế để vận dụng, cải tiến, hiệu chỉnh và nâng cấp
chương trình ……………………………………………………………………8
2.3.4 Giao bài tập về nhà…………………………………………………..18
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản
thân, đồng nghiệp và nhà trường…………………………………………………..19
3. Kết luận, kiến nghị.........................................................................................20


1. Mở đầu
1.1. Lý do chọn đề tài
Trong chương trình Tin học lớp 11, nội dung kiến thức về mảng một chiều trang bị
cho học sinh chỉ bao gồm 2 tiết lí thuyết và 1 tiêt bài tập và 4 tiết thực hành. Vì vậy,
lượng kiến thức và thời lượng đó đó chưa đủ để học sinh có thể vận dụng vào giải
các bài tập liên quan đến các dãy con liên tiếp khi biểu diễn dãy bằng mảng một
chiều. Rèn luyện tư duy , kỹ năng và tác phong lập trình có vai trò đặc biệt trong
khi bỗi dưỡng học sinh giỏi môn tin học ở trường phổ thông. Hiệu quả của việc
rèn luyện tư duy, kỹ năng và tác phong lập trình là động lực giúp học sinh nắm
vững kiến thức, phát triển tư duy, hình thành kỹ năng và kỹ xảo. T ừ đó có khả
năng thích ứng khi đứng trước một vấn đề cần giải quyết. Học sinh cũng thấy được


2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
- Cơ sở tâm lý học:

+ Đặc điểm nhận thức của học sinh đối với môn Tin học:
Đối với khối THPT, hiện nay phần lớn học sinh coi bộ môn Tin học là môn học
phụ, không quan tâm cho lắm, vẫn còn có một vài học sinh có hứng thú với môn
Tin học. Từ số lượng ít ỏi đó vẫn có cơ hội để người giáo viên tìm ra các học sinh
cho đội tuyển học sinh giỏi của mình.
+ Tư duy của học sinh:

Thông thường những học sinh có kỹ năng lập trình khá, giỏi là những em có kiến
thức Toán học khá, giỏi, xong điều ngược lại thì chưa hẳn, lý do rất đơn giản là khả
năng vận dụng kiến thức vào để giải quyết vấn đề khi giải quyết bài toán Tin học.
Chẳng hạn, khi học giải bài tập môn toán các em có thể học theo dạng 1, dạng 2…
nhưng trong tin học thì một bài toán có thể là sự kết hợp của nhiều bài toán cơ bản
khác nhau.
Ở các em học sinh khối THPT thì môn lập trình Pascal các em bước đã làm
quen nhưng không chú trọng nên khả năng tư duy vẫn còn hạn chế nên việc phân
tích để hiểu được bản chất của vấn đề là rất khó.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
- Thực trạng công tác bồi dưỡng học sinh giỏi môn Tin học hiện nay.

Thực tế đa số học sinh rất lúng túng về phương pháp cho loại toán này bởi vì trong
sách giáo khoa hay sách bài tập không có nhiều bài tập loại này nhưng lại có trong
đề thi học sinh giỏi những năm gần đây khiến cho học sinh rất bối rối về phương
pháp. Một số học sinh tham khảo một số code về các bài toán liên quan đến dãy
con trên mạng nhưng học sinh cũng khó hiểu và dẫn đến có thói quen lập trình thụ
động, không tự nhiên. Điều đó làm giảm đi hứng thú với môn học.

dãy hoặc chỉ số đầu và chỉ số cuối (chỉ nơi kết thúc dãy con).
- Dãy con có thể có 1, 2, … N phần tử (tuỳ vào định nghĩa dãy con và yêu cầu đề
bài). Nếu dãy mẹ có N phần tử thì ta có 2n dãy con.
- Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn
gồm 3 vòng For như sau:
For i:=1 to N do
{1}
For j:=1 to N-i+1 do
{2}
For k:=j to i+j-1 do
{3}
(xử lý dãy con bắt đầu từ vị trí j đến vị trí i+j-1); {4}
Giải thích:
{1} Vòng for 1: Cho biết độ dài của dãy con có i phần tử;
{2} Vòng for 2: Cho biết dãy con bắt đầu từ vị trí j, vậy vị trí bắt đầu của dãy con
cuối cùng có độ dài i sẽ là n-i+1;
{3} Vòng for 3: Dùng để duyệt qua các phần tử của dãy con bắt đầu từ vị trí đầu là
j đến vị trí cuối là i+j-1 để xử lý.
{4} Các thao tác xử lý có thể là: Tính tổng của dãy con; Kiểm tra tính tăng, giảm;
Kiểm tra tính đối xứng; ….
* Nếu dãy con đang xét cần lưu lại thì: Lưu lại độ dài, chỉ số đầu dãy. Xác
định lại độ dài, chỉ số đầu của dãy mới.
* Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu
của dãy mới.
Khi dạy chuyên đề này ta có thể rèn luyện thêm cho học sinh cách viết và sử dụng
các chương trình con, để các chương trình con này tham gia vào nhiệm vụ xử lý ở
phần xử lý {4}, ví dụ chương trình con kiểm tra tính đối xứng của đoạn con từ j
đến j+i-1, chương trình con kiểm tra tính tăng, giảm của đoạn con, chương trình
con kiểm tra xem đoạn con đó có lập thành cấp số cộng hay không, …


Dc11 5 6
Dc12 1 2 3
Dc13 2 3 4
Dc14 3 4 5
Dc15 4 5 6
Dc16 1 2 3 4
Dc17 2 3 4 5
Dc18 3 4 5 6
Dc19 1 2 3 4 5
Dc20 2 3 4 5 6
Dc21 1 2 3 4 5 6
Với bài tập này học sinh chỉ cần vận dụng lý thuyết đã được cung cấp để giải quyết,
mục đích của bài tập này là để học sinh đưa ra được cũng như thấy được hình ảnh
cụ thể các dãy con của một dãy số cho trước.
Chương trình tham khảo như sau:
Trang

5


CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
N,I,J,T: INTEGER;
BEGIN
WRITELN('NHAP N= ');
READLN(N);
FOR I:=1 TO N DO
BEGIN
WRITE('NHAP PHAN TU THU ',I);
READLN(A[I]);

Trang

6


Dc13 3 4
Dc14 4 5
Dc15 5 6
Dc16 1
Dc17 2
Dc18 3
Dc19 4
Dc20 5
Dc21 6
Mục đích của bài tập 2 này là rèn luyện thêm kỹ năng chuyển đổi giữa câu lệnh For
tiến và For lùiviệc làm này có lợi khi giáo viên đưa ra yêu cầu tìm một dãy con
ngắn nhất hoặc dài nhất thỏa mãn một điều kiện nào đó, khi đó học sinh sẽ biết nên
chọn câu lệnh for nào để khi tìm thấy một dãy con như vậy thì thoát luôn không cần
tìm tiếp.
Chương trình tham khảo như sau:
CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
N,I,J,T: INTEGER;
BEGIN
WRITELN('NHAP N= ');
READLN(N);
FOR I:=1 TO N DO
BEGIN
WRITE('NHAP PHAN TU THU ',I);
READLN(A[I]);

vì đề bài cũng yêu cầu đưa ra các dãy con nhưng chỉ khác là các dãy con có độ dài
từ 1 đến N chỉ được đưa ra đúng một lần và các dãy con đó đều bắt đầu từ phần tử
thứ 1 của dãy.
Từ đó có thể tự phân tích được cách làm, nếu học sinh còn lúng túng giáo viên có
thể hướng dẫn học sinh để đưa ra nhận xét sau:
- Có N lần duyệt, vậy ta dùng biến i là biến duyệt số lần, với i chạy từ 1 đến N
- Với mỗi lần duyệt i, ta in ra các dãy con từ 1 đến N-i+1
Vậy khi đó chỉ cần có 2 vòng for là đủ để in ra các dãy con này, vậy so với thuật
toán vét cạn đã được giới thiệu ở phần lý thuyết thì ta bỏ bớt đi vòng lặp thứ 3.
Chương trình tham khảo như sau:
CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
N,I,J,T: INTEGER;
BEGIN
WRITELN('NHAP N= ');
READLN(N);
FOR I:=1 TO N DO
BEGIN
WRITE('NHAP PHAN TU THU ',I);
READLN(A[I]);
END;
FOR I:=1 TO N DO
BEGIN
FOR J:=1 TO N-I+1 DO
WRITE(A[J],' ');
WRITELN;
END;
READLN;
END.
Trang

Ở mức độ này dựa vào vào các đặc điểm của dữ liệu, dữ kiện mà đê bài yêu cầu,
giáo viên có thể hướng dẫn thêm học sinh các kỹ thuật khác để giúp học sinh nâng
cấp chương trình nhưng chưa phải là chạy hết được các test. Chẳng hạn kỹ thuật
dùng biến định vị (lính canh), kỹ thuật trượt cửa sổ, kỹ thuật đặ cờ hiệu…
Mức độ 3: Tùy vào năng lực tiếp thu của học sinh giáo viên có thể hướng dẫn học
sinh sử dụng các kỹ thuật lập trình khác để xử lý các bộ test lớn của bài toán.
Chẳng hạn như quy hoạch động…
Dưới đây là một số bài tập tôi đã sử dụng để rèn luyện kỹ năng cho học sinh:
Bài tập 1: Cho một mảng số nguyên gồm n phần tử. Tìm dãy con gồm m phần tử
(m≤ n ≤ 1000) sao cho dãy con này có tổng lớn nhất. (Dãy con là dãy các phần tử
liên tiếp nhau trong mảng).
Ví dụ: nhập vào từ bàn phím
N=6
1 -3 2 -5 4 3
Trang

9


M=4
In ra màn hình: 2 -5 4 3
Khi làm bài tập này, dựa vào lý thuyết học sinh đã được cung cấp thuật toán vét
cạn:
For i:=1 to N do
{1}
For j:=1 to N-i+1 do
{2}
For k:=j to i+j-1 do
{3}
(xử lý dãy con bắt đầu từ vị trí j đến vị trí i+j-1); {4}

{ Thay vị trí đầu tiên của dãy con mới }
End;
Trang 10


End;
Writeln('Day con co tong lon nhat la:');
For i:=vt To vt+m-1 Do Write(A[i]:5);
Readln;
End.
Sau khi đã viết được chương trình giáo viên có thể yêu cầu học sinh tự cải tiến
chương trình nếu có thể, nếu học sinh còn lúng túng thì giáo viên mới đưa ra nhận
xét để học sinh cải tiến chương trình của mình.
Hướng dẫn cải tiến chương trình: Giống như trong bài toán tìm giá trị lớn nhất
của dãy số, ban đầu ta giả sử Max = A[1], thì ở đây ta cũng giả sử tổng Max ban
đầu là tổng các phần tử từ 1 đến M, các lần sau ta chỉ tìm và so sánh tổng Max với
các dãy con bắt đầu từ vị trí thứ 2 trở đi, chương trình tham khảo như sau:
Type M1C=ARRAY[1..1000] Of Integer;
Var A : M1C;
n,m,i,j,k,vt:integer;
S,Max:longint;
Begin
Write('Nhap so phan tu cua mang: n= '); Readln(n);
For i:=1 To n Do
Begin
Write('a[',i,']='); Readln(a[i]);
End;
Write('Nhap so phan tu cua day con: m= '); Readln(m);
vt:=1; {Vị trí phần tử đầu tiên của dãy con}
{Giả sử m phần tử đầu tiên của mảng A là dãy con có tổng lớn nhất}

• Dòng đầu ghi N.
• Dòng tiếp ghi các số A1, A2, ..., AN.
Kết quả: ghi ra file văn bản DAY.OUT gồm một dòng ghi giá trị K và chỉ số của số
hạng đầu tiên được lấy ra.
Giới hạn: N và các Ai ≤ 32767.
Ví dụ:
DAY.INP
DAY.OUT
5
24
12214
Khi làm bài tập này với thuật toán vét cạn để đưa ra các dãy con đã được cung cấp,
học sinh có thể viết được chương trình ở mức độ chưa chính xác như sau:
program Bt2;
Type m1c = array[1..10000] of integer;
Var a:m1c;
i, j, t,n, kmax,jmax:integer;
tong:longint;
thay:boolean;
f1,f2:text;
BEGIN
Assign(f1,'DAY.INP'); Reset(f1);
readln(f1,n);
for i:= 1 to n do Read(f1,a[i]);
Close(f1);
Assign(f2,'DAY.OUT'); Rewrite(f2);
{xu ly}
for i:=1 to N do
for j:=1 to N- i+1 do
begin

Close(f1);
Assign(f2,'DAY.OUT'); Rewrite(f2);
for i:=1 to N do
begin
thay:=false;
for j:=1 to N- i+1 do
begin
tong:=0;
for t:=j to j+i-1 do
tong:=tong+a[t];
if tong mod n =0 then
begin
kmax:=i;
jmax:=j;
thay:=true; end;
if thay then break;
end;
if thay then break;
end;
Write(f2,kmax, ' ', jmax);
Close(f2);
END.
Trang 13


Với bài này đề bài không cho giới hạn của N nên giáo viên cũng chưa cần yêu cầu
chương trình của học sinh phải chạy được nhiều test.
Bài tập 3: Đoạn con
Cho dãy số nguyên a1, a2,..., aN (|ai| < 109, N < 105). Một tập hợp khác rỗng các
số hạng liên tiếp {ai, ai+1,..., ak} (i ≤ k) gọi là một đoạn con của dãy đó. Với mỗi

tong,kq:int64;
f1,f2:text;
BEGIN
Assign(f1,'SUBSEQ.INP'); Reset(f1);
readln(f1,n);
for i:= 1 to n do Readln(f1,a[i]);
Close(f1);
Assign(f2,'SUBSEQ.OUT'); Rewrite(f2);
{xu ly}
kq:=-200000000000000000;
for i:=1 to N do
for j:=1 to N- i+1 do
Trang 14


begin
tong:=0;
for t:=j to j+i-1 do
tong:=tong+a[t];
if tong > kq then
kq:=tong;
end;
Write(f2,kq);
Close(f2);
END.
Tuy nhiên gáo viên cần cho học sinh chạy một vài test sau đó thử chạy các test lớn
(theo đề bài N
tong:=tong+x;
b[i]:=tong;
end;
close(f1);
kq:=-20000000000000000;
for i:=1 to n do
for j:=i to n do
if b[j]-b[i-1]>kq then kq:=b[j]-b[i-1];
writeln(f2,kq);
close(f2);
end.
Mức độ 2: Sau khi cải tiến chương trình trên đã chạy được tương đối, nhưng với
test lớn thì chương trình vẫn chạy hơi chậm. Từ đó giáo viên có thể hướng dẫn học
sinh vận dụng thêm kỹ thuật tìm giá trị lớn nhất trên mảng B để so sánh với kết
quả, khi đó thay vì phải vét cạn tất cả các trường hợp trên mảng B bằng 2 vòng For
thì ta chỉ giải quyết trên một vòng For, đương nhiên là chương trình sẽ chạy nhanh
hơn và chạy hết được các test của bài này.
Cụ thể, ta cải tiến như sau:
- Ban đầu ta đặt Max:=B[N] {là tổng của toàn bộ dãy}, kq:=-200000000000000;
{giả sử kết quả là một số âm rất lớn}
- Cho i chạy từ N-1 về 0, tức là duyệt mảng B từ N-1 về 0 để tìm dãy con có tổng
lớn nhất, mỗi lần duyệt ta so sánh kq với Max-B[i] nếu kq < Max-B[i] thì cập nhật
lại kq = Max-B[i], đồng thời so sánh B[i] với Max nếu B[i]>Max thì cập nhật lại
Max=B[i]
Chương trình tham khảo như sau:
const nmax=round(1e5);
fi='subseq.inp';
fo='subseq.out';
var a:array[1..nmax] of longint;
b:array[0..nmax] of int64;

của đề bài.
Bài tập 4: Dãy số vòng tròn
Trên một vòng tròn người ta đánh dấu n vị trí. Các vị trí được đánh số thứ tự
từ 1 đến n theo chiều kim đồng hồ. Tại vị trí i người ta ghi số nguyên ai (i=1,2,...,n).
Cần tìm cách chọn ra dãy con gồm k số liên tiếp (0
begin
t:=0;
for j:=i to i+k-1 do
if jmax then
begin max:=t;
sl:=k;
vt:=i; end;
end;
writeln(f2,max);
writeln(f2,vt,' ',sl);
close(f1); close(f2);
end.
Trang 18


Sau khi chạy chương trình với một số test giáo viên nên hướng dẫn học sinh tạo ra
một test với giá trị N=106 (giáo viên dùng hàm random để tạo test này, ghi các số
tạo được vào tệp đầu vào theo đề bài) để học sinh chạy thử xem thế nào? Và chỉ ra
bước tiếp theo ta nên cải tiến thuật toán theo hướng nào? Hướng dẫn học sinh dùng
kỹ thuật nào?
Tuy nhiên cũng cần phải thấy rằng phần đông học sinh trung học phổ thông
nếu thầy cô cố gắng hướng dẫn kỹ thuật quy hoạch động để chạy hết test bài này thì
cũng hơi khó khăn. Ở đây ta phải căn cứ vào năng lực của học sinh mình đến đâu
thì mới quyết định đưa ra phương án tiếp theo để học sinh rèn luyện kỹ năng.
Bài tập rèn luyện ở nhà:
2.3.4 Giao bài tập về nhà
BTVN 1: Dãy con
Cho một dãy số gồm N sốnguyên dương a1, a2, …,an , và số nguyên dương M.
Yêu cầu: tìm độ dài lớn nhất của dãy con chứa các phần tử liên tiếp của dãy mà các

1 3 2 4 5 10
Trang 19


BTVN 3: ĐOẠN MAX
Cho chuỗi ký tự S gồm các chữ cái in hoa (A…Z) với độ dài không vượt quá 104.
Yêu cầu: Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào
xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng
chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đâu tiên trong chuỗi S.
Dữ liệu: Vào từ văn bản DOANMAX.INP:
- Gồm một dòng duy nhất chứa chuỗi S.
Kết quả: Ghi ra file văn bản DOANMAX.OUT
- chỉ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiệu dài
của đoạn con dài nhất tìm được.
Ví dụ:
DOANMAX.INP
DOANMAX.OUT
ABABCDAC
34
Lưu ý: Có 80% test có độ dài xâu không vượt quá 255.
Giải thích test ví dụ: Đoạn con dài nhất tìm được là ABCD có vị trí 3 và dộ dài 4
BTVN 4: Dãy con đối xứng dài nhất
Dữ liệu vào: từ tệp DCDX.inp dòng thứ nhất chứa số nguyên N, dòng 2 ghi N số
mỗi số ách nhay 1 dấu cách.
Dữ liệu ra: ghi vào tệp DCDX.out dãy con liên tiếp đối xứng dài nhất
Ví dụ:
BAI2.INP
BAI2.OUT
8
44344

- Giáo viên nên tham khảo thêm các đề thi học sinh giỏi của các tỉnh các năm
trước.
- Tham khảo nhiều sách báo tài liệu có liên quan, giao lưu học hỏi các bạn
đồng nghiệp có nhiều kinh nghiệm, các trường có bề dày thành tích.
- Giáo viên phải khơi dậy niềm say mê, hứng thú của học sinh đối với môn tin
học, luôn phối hợp với giáo viên chủ nhiệm và gia đình để tạo điều kiện tốt nhất
cho các em tham gia học tập.
- Kiến nghị:

- Đối với nhà trường BGH nên chú trọng hơn công tác khảo sát, lựa chọn học
sinh và phân bổ các đối tượng học sinh cho các môn để bồi dưỡng học sinh giỏi. Vì
gần như môn Tin học là môn được chỉ chọn được học sinh đội tuyển sau khi cac
môn tự nhiên khác đã chọn.
- Đối với các cấp cũng nên ra các dạng đề thi phong phú, phù hợp với khả năng
và trình độ của học sinh, không nên ra đề quá sức đối với học sinh.
XÁC NHẬN CỦA THỦ TRƯỞNG
ĐƠN VỊ

Thanh Hóa, ngày28 tháng 05 năm 2016
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.
(Ký và ghi rõ họ tên)

Lê Văn Khánh

TÀI LIỆU THAM KHẢO
1. SGK tin học 11
- NXB Giáo dục Việt Nam
2. Sách bài tập tin học 11
- NXB Giáo dục Việt Nam