SỞ GD - ĐT NAM ĐỊNH
TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG
SÁNG KIẾN DỰ THI CẤP TỈNH
BÁO CÁO SÁNG KIẾN:
CÁC DẠNG BÀI VỀ DÃY CON
VÀ HƯỚNG GIẢI QUYẾT
Tác giả: TRẦN THỊ THANH HUYỀN
Trình độ chuyên môn: Thạc sỹ Tin học
Chức vụ: Giáo viên
Nơi công tác: Trường THPT chuyên Lê Hồng Phong
Nam Định, 6/6-2015
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
1
1. Tên sáng kiến: CÁC DẠNG BÀI VỀ DÃY CON VÀ HƯỚNG GIẢI QUYẾT
2. Lĩnh vực áp dụng: Giảng dạy trong môn Tin cho học sinh khối chuyên Tin, đội
tuyển HSG đồng bằng Bắc bộ khối 10, khối 11, bồi dưỡng đội tuyển HSG Quốc gia.
3. Thời gian áp dụng:
- Từ năm 2012 đến nay
4. Tác giả:
Họ tên : TRẦN THỊ THANH HUYỀN
Ngày sinh: 09-10-1978
Nơi thường trú: 2/24/131 TRẦN THÁI TÔNG- TP NAM ĐỊNH
Trình độ chuyên môn: Thạc sỹ Tin học
Chức vụ công tác: Giảng dạy bộ môn Tin học
Nơi làm việc: Trường THPT chuyên Lê Hồng Phong- Tp Nam Định
Địa chỉ: 76 Vị Xuyên
Điện thoại: 03503. 640.297
5. Đơn vị áp dụng sáng kiến
Tên đơn vị: Trường THPT chuyên Lê Hồng Phong- Tp Nam Định
Địa chỉ: 76 Vị Xuyên
Điện thoại: 03503. 640.297
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
2
BÁO CÁO SÁNG KIẾN
I. ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN
Một công việc quen thuộc của giáo viên khi giảng dạy Tin trong các lớp
chuyên đó là: bên cạnh việc thường xuyên phải hệ thống lại các dạng bài tập, lựa
chọn các dạng bài phù hợp để học sinh rèn kỹ năng cài đặt bài tập sau khi đã được
trang bị về lý thuyết thì một mục tiêu tối quan trọng là phân loại và phát hiện năng
khiếu về môn chuyên của học sinh.
Trong quá trình khai thác các dạng bài tập để dạy học và tự nghiên cứu, tôi gặp phải
rất nhiều dạng bài tập liên quan đến “dãy con” và nhận thấy chúng rất đa dạng và ở
nhiều mức độ khác nhau: từ dễ đến khó. Để giải quyết các bài toán về “dãy con” này
có thể phải vận dụng linh hoạt các chiến lược thiết kế thuật toán như: quay lui - vét
cạn, chặt nhị phân và đặc biệt là phương pháp quy hoạch động trên mảng một chiều,
hai chiều được vận dụng rất nhiều để giải quyết. Đây cũng là những phương pháp
thiết kế thuật toán mà học sinh chuyên cần phải được rèn luyện nhiều khi làm bài
tập
II. MÔ TẢ GIẢI PHÁP
1. Mô tả giải pháp trước khi tạo ra sáng kiến
Trước đây, khi ôn tập cho học sinh chuyên Tin và dạy các đội tuyển, tôi đã
đưa ra một số bài tập nói trong tài liệu này song đưa ra một cách riêng lẻ, không có
hệ thống và theo từng chuyên đề thuật toán. Ví dụ: Đa số các bài về dãy con thường
có cách giải bằng phương pháp Quy hoạch động nên chúng có trong phần ví dụ áp
dụng của chuyên đề về Quy hoạch động. Tuy nhiên các bài toán về ”dãy con” rất đa
dạng, nhiều thể loại, có thể có nhiều phương pháp giải khác nhau. Vì vậy, tôi thiết
nghĩ: cần phải hệ thống hóa lại các bài tập liên quan đến xử lý “dãy con” và phân
loại chúng thành các dạng cụ thể để qua đó học sinh có thể rút ra được phương pháp
giải quyết phù hợp với từng dạng bài.
2.Mô tả giải pháp sau khi có sáng kiến
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
3
Để góp phần giúp các em vận dụng linh hoạt và nhiều hơn nữa các phương pháp
thiết kế thuật toán vào giải các bài tập cụ thể, phổ biến như các dạng bài tập về dãy
con của học sinh chuyên tin cũng như góp phần xây dựng kho bài tập bồi dưỡng
HSG các cấp, trong tài liệu này tôi xin được trình bày vấn đề “ Các dạng bài toán
về dãy con và hướng giải quyết”
NỘI DUNG
A.Một số khái niệm
Cho một dãy N số nguyên A=(A1, A2, …, AN)
Ví dụ: A= (8 6 5 2 6 4 9) với N=7
+ Dãy con của một dãy A cho trước là một dãy thu được bằng cách xóa đi một số
phần tử của dãy A, các phần tử còn lại vẫn giữ đúng thứ tự. Mỗi dãy số là dãy con
của chính nó. Dãy rỗng là dãy con của mọi dãy bất kỳ.
Ví dụ: Dãy ( 6 5 4 9) là dãy con của A
+ Đoạn con (dãy đoạn con) của một dãy A cho trước là một dãy các phần tử liên tiếp
có trong A
Ví dụ: Dãy ( 6 5 2 6 ) là đoạn con của A
* Các kiến thức cần trang bị:
- Các thuật toán cơ bản: Tìm ước chung của 2 số, kiểm tra tính nguyên tố của một số
nguyên dương, kiểm tra tính nguyên tố cùng nhau của một cặp số, kiểm tra một số
thuộc dãy số Fibonacci,…
- Các thuật toán nâng cao: tìm kiếm nhị phân, sắp xếp nhanh, trộn mảng, thuật toán
sinh hoán vị, thuật toán loang, xử lý bit.
- Các phương pháp thiết kế thuật toán: duyệt-vét cạn, quay lui, quy hoạch động.
B. Các dạng bài tập
Dạng 1: Dãy con tăng dần (giảm dần) dài nhất (ngắn nhất)
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
4
Bài 1. Đoạn con tăng dần dài nhất
Cho dãy gồm N số nguyên. Tìm đoạn con tăng dần có chiều dài lớn nhất.
Dữ liệu vào: tệp văn bản DAYCON.INP
Dòng thứ nhất: số tự nhiên N, 1 N 20000.
Từ dòng thứ hai trở đi: các phần tử của dãy.
Dữ liệu ra: tệp văn bản DAYCON.OUT
DAYCON.INP
DAYCON.OUT
Chứa một dòng duy nhất gồm hai số tự nhiên
12
47
d – chỉ số đầu đoạn và L – số phần tử trong
15513
đoạn (chiều dài đoạn).
33579
Trong các tệp, dữ liệu trên cùng dòng cách
12
nhau qua dấu cách.
Giải thích : Đó là dãy con 1 3 3 3 5 7 9
Thuật toán
- Ta đọc dần các phần tử từ input file và so sánh hai phần tử liên tiếp nhau là x
(phần tử đọc trước tại bước i) và y (phần tử đọc sau tại bước i+1).
- Nếu y < x thì coi như kết thúc một đoạn không giảm, ta cập nhật để ghi nhận lại
đoạn không giảm dài nhất.
Độ phức tạp: cỡ O(N).
Chương trình
program DAYCON;
uses crt;
const
fn = 'DAYCON.INP';
gn = 'DAYCON.OUT';
var f,g: text;
n: longint;
a: mw1;
iLeft, imax: longint;
MaxLen: longint;
procedure Update(i: longint);
begin
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
5
if (MaxLen < i - iLeft) then
begin
MaxLen := i - iLeft;
imax := iLeft; ileft := i;
end;
iLeft := i;
end;
procedure XuLi;
var i, x, y: longint;
begin
assign(f,fn);
reset(f);
readln(f,n);
read(f,x);
iLeft := 1;
MaxLen := 0;
for i := 2 to n do
begin
read(f,y);
if (y < x) then Update(i);
x := y;
end;
Update(n+1);
close(f);
end;
procedure Ghi;
begin
assign(g,gn);
rewrite(g);
writeln(g,imax,’ ‘,MaxLen);
close(g);
end;
BEGIN
XuLi; ghi;
END.
Bài 2. Đoạn đơn điệu dài nhất
Cho dãy gồm N số nguyên. Tìm đoạn đơn điệu (không giảm hoặc không tăng)
có chiều dài lớn nhất.
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
6
Dữ liệu vào: tệp DONDIEU.INP
Dòng thứ nhất: số tự nhiên N,
1N 20000.
Từ dòng thứ hai trở đi: các phần tử của dãy.
Dữ liệu ra:tệp văn bản DONDIEU.OUT
DONDIEU.INP
Chứa một dòng duy nhất gồm hai số tự
nhiên d là chỉ số đầu đoạn và L là số
12
phần tử trong đoạn (chiều dài đoạn).
155133357912
DONDIEU.OUT
47
Thuật toán
Nhận xét:
Đoạn có 1 phần tử là đoạn đơn điệu (tăng, giảm),
Đoạn gồm một dãy liên tiếp các phần tử bằng nhau là đoạn đơn điệu (tăng, giảm).
Ta dùng hai biến đếm các phần tử tăng hoặc bằng nhau liên tiếp: dt và đếm các phần
tử giảm hoặc bằng nhau liên tiếp: dg.
- Nếu ai = ai 1 ta tăng đồng thời dt và dg 1 đơn vị. Nếu a i > ai 1 ta tăng dt thêm 1
đơn vị và đặt lại dg = 1.
- Nếu ai < ai 1 ta tăng dg thêm 1 đơn vị và chỉnh lại dt = 1. Sau mỗi bước ta cập
nhật đoạn đơn điệu dài nhất tìm được.
Độ phức tạp: cỡ O(N).
Chương trình
program DonDieu;
uses crt;
const
fn = 'DONDIEU.INP';
gn = 'DONDIEU.OUT';
var f,g: text;
n: longint;
dt,dg: longint;
iMax, MaxLen: longint;
function Max(a,b,c: longint): longint;
begin
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
7
if (a < b) then a := b;
if (a > c) then Max := a
else Max := c;
end;
procedure XuLi;
var i,m,x,y: longint;
begin
assign(f,fn); reset(f);
readln(f,n); read(f,x);
dt := 1; dg := 1;
MaxLen := 1; iMax := 1;
for i := 2 to n do
begin
read(f,y);
if (y = x) then
begin
dt := dt + 1;
dg := dg + 1; end
else if (y > x) then
begin
dt := dt + 1;
else
begin
dg := 1;
end
dg := dg + 1;
dt := 1;
end;
MaxLen := m; iMax := i - MaxLen + 1;
end;
m := Max(MaxLen, dt, dg);
if (m > MaxLen) then
begin
x := y;
end;
close(f);
end;
procedure Ghi;
begin
assign(g,gn);
rewrite(g);
writeln(g, iMax,’ ‘, MaxLen);
close(g);
end;
BEGIN
XuLi; Ghi;
END.
Bài 3. Chuỗi ốc
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
8
Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý
tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất
thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách
muốn thưởng thức các loại hình dịch vụ giải trí nghỉ dưỡng,
câu cá, lướt ván, lặn ngắm san hô, du thuyền,.. Trong một đợt đi du lịch ở Đà Nẵng,
sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng
lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: Ban đầu từ
chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong
hai đầu của chuỗi hoặc hoặc bỏ đi không lấy; cuối cùng nhận được một chuỗi vỏ ốc
mà tính từ đầu chuỗi đến cuối chuỗi, các vỏ ốc có kích thước tăng dần và gồm càng
nhiều vỏ ốc càng tốt.
Yêu cầu: Cho trước dãy a1, a2,…, an là kích thước của các vỏ ốc mà DONG3D lần
lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm
nhiều vỏ ốc nhất.
BEADS.INP BEADS.OUT
Dữ liệu: Vào từ file BEADS.INP
5
Dòng 1 chứa số nguyên dương N ≤ 105
44531
4
Dòng 2 chứa N số nguyên dương a1, a2,…, an
(i: ai≤ 109) cách nhau bởi dấu cách.
Kết quả: Ghi ra file BEADS.OUT một số nguyên duy nhất là số lượng vỏ ốc trong
chuỗi tạo được.
Thuật toán:
- Tìm dãy con tăng dài nhất F[i] với i là phần tử đầu tiên
- Tìm dãy con giảm dài nhất F2[i] với i là phần tử đầu tiên
- Kết quả cần tìm của bài toán chính là max(F[i]+F2[i]-1);
Chương trình:
var fi,fo:text;
f,a,b,f2:array[1..100000]of longint;
i,n,max,tg,j:longint;
procedure day1;
begin
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
9
f[n]:=1;
for i:=n-1 downto 1 do
begin
max:=0;
for j:=i+1 to n do
if (max
a[i]) then max:=f[j];
f[i]:=max+1;
end;
end;
procedure day2;
begin
f2[n]:=1;
for i:=n-1 downto 1 do
begin
max:=0;
for j:=i+1 to n do
if (maxa[c[i]] then res:=max(res,l[c[i]]+f[v]) ;
End ;
//tron 2 doan da sap xep
u:=x ; v:=m+1 ;
for i :=x to y do
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
12
if(v>y)or((v<=y)and(u<=m)and(a[c[u]])a[i-1]) then l[i] :=l[i-1]+1 ;
End ;
R[n] :=1 ;
For i :=n-1 downto 1 do
begin
R[i] :=1 ;
If (a[i]0 do
begin
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
13
Dec(ntest);enter ;solve ;
Writeln(fo, res);
end ;
Close(fo) ; close(fi);
End.
Dạng 2 : Tổng, tích các phần tử của dãy con
Bài 5. Tổng đoạn ngắn nhất
Cho một dãy số nguyên a1, a2, a3, …, an. Tìm đoạn ngắn nhất các phần tử trong dãy
thỏa ai + ai + 1 + ai + 2 + … + aj = k.
Dữ liệu vào: tệp văn bản TDOAN.INP
Dòng thứ nhất: hai số tự nhiên N và K, 1 N 2000.
Từ dòng thứ hai trở đi: các phần tử của dãy.
Dữ liệu ra: tệp văn bản TDOAN.OUT
Chứa một dòng duy nhất gồm hai số tự nhiên d – chỉ số đầu đoạn và L – số
phần tử trong đoạn (chiều dài đoạn). Nếu vô nghiệm thì ghi 0 0.
Trong các tệp, dữ liệu trên cùng dòng cách nhau qua dấu cách.
Thu
Xét
TDOAN.INP
TDOAN.OUT
21 17
16 3
0 2 3 2 10 1 5 5 6 12 20 30 14 8 0 11 0 6 0 0 5
a[i..j]
ật
toán
đoạn
với
tồng S = a[i] + a[i+1] + … + a[j], i j. Ta cho đoạn này dịch dần sang phải và xét ba
tình huống sau đây.
+ S = K: ta ghi nhận điểm đầu i và độ dài đoạn là ji+1. Nếu độ dài này nhỏ hơn độ
dài LMin thì ta cập nhật lại các giá trị iMin và Lmin (thủ tục Update). Rồi tiếp tục
xét đoạn con mới là a[i+1..j] .
+ S < K: Ta dịch từ j sang j+1, giữ nguyên đầu i (thủ tục Right).
+ S > K: Dịch từ i thành i+1 (thủ tục Left).
Ta đặt phần tử a[n+1] = 0 làm lính canh.
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
14
Chương trình:
program TDoan;
uses crt;
const
mn = 2001;
fn = 'TDOAN.INP';
gn = 'TDOAN.OUT';
type mw1 = array[0..mn] of word;
var f,g: text;
n,k: word;
a: mw1;
iMin, LMin: word;
iLeft,iRight: word;
sum: word;
procedure Doc;
var i: word;
begin
assign(f,fn); reset(f); readln(f,n, k);
for i := 1 to n do read(f,a[i]);
close(f);
end;
procedure Left;
begin
sum := sum - a[iLeft]; iLeft := iLeft + 1;
if (iLeft > iRight) then
begin iRight := iLeft; sum := a[iLeft]; end;
end;
procedure Right;
begin
iRight := iRight + 1;
sum := sum + a[iRight]; end;
procedure Update;
begin
if (LMin > iRight - iLeft + 1) then
begin iMin := iLeft; LMin := iRight - iLeft + 1; end;
Left;
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
15
end;
procedure XuLi;
begin
iLeft := 1; iRight := iLeft;
LMin := n + 1; sum := a[1];
repeat
if (sum = k) then Update
else if (sum < k) then Right
else { sum > k } Left;
until (iRight > n);
if (LMin = n+1) then LMin := 0;
end;
procedure Ghi;
begin
assign(g,gn); rewrite(g); writeln(g,iMin,’ ‘,LMin); close(g);
end;
BEGIN
Doc; XuLi; ghi;
END.
Bài 6. Dãy con dài nhất tổng chia hết cho k
Cho một dãy số nguyên gồm N phần tử a 1 , a2, ..., aN và một số nguyên k. Giả
thiết dãy cho luôn luôn tồn tại một dãy con có tổng các phần tử chia hết cho k.
Yêu cầu : Hãy tìm dãy con có nhiều phần tử nhất có tổng các phần tử chia hết cho k.
Dữ liệu vào: Ghi trong file text, tên file là CK.INP gồm 2 dòng:
- Dòng đầu ghi 2 số nguyên N và k ( 0 2 -> 4 -> 5. Số điểm đạt được là 0 + 3 – 4 + 5 = 4.
Thuật toán:
- Sử dụng phương pháp Quy hoạch động.
- Gọi F[i] là giá trị lớn nhất đạt được khi đến vị trí i.
Khởi tạo: F[1]=max(0,a[1]);
Ta có công thức tổng quát F[i]=max(F[i], F[i-j]+a[i]) với i:2 n, j: 1k
- Kết quả là Max(F[i])
Chương trình
uses math;
var
a,f:array[1..1000001] of longint;
i,n,kq,j,k:longint;
begin
readln(n,k);
for i:=1 to n do
begin
f[i]:=-10000;
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
20