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 = ai1 ta tăng đồng thời dt và dg 1 đơn vị. Nếu ai > ai1 ta tăng dt thêm 1
đơn vị và đặt lại dg = 1.
- Nếu ai < ai1 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;
dg := dg + 1;
end
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.
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
8
Bài 3. Chuỗi ốc
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.
Dữ liệu: Vào từ file BEADS.INP
Dòng 1 chứa số nguyên dƣơng N ≤ 105
Dòng 2 chứa N số nguyên dƣơng a1, a2,…, an
BEADS.INP BEADS.OUT
5
4
44531
(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;
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
9
begin
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
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
12
u:=x ; v:=m+1 ;
for i :=x to y do
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
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.
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
Thuật toán
Xét đoạn a[i..j] 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.
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
14
+ 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.
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;
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
15
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;
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ử a1 , 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;
Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ
20