CHUYÊN ĐỀ DUYỆT CÓ TÍNH TOÁN
A. MỤC ĐÍCH
Chuyên đề này cung cấp cho học sinh những kiến thức và kĩ năng trọng tâm về ứng
dụng duyệt có tính toán. Cụ thể:
a) Về kiến thức: Cung cấp, hệ thống cho học sinh các kiến thức cơ bản, trọng tâm về
những ứng dụng của phương pháp duyệt có tính toán trong lập trình, đáp ứng yêu cầu
của kì thi chọn học sinh giỏi các cấp.
b) Về kĩ năng:
- Nhận biết được bài toán cụ thể có thể giải bằng duyệt có tính toán.
- Rèn luyện cho học sinh kĩ năng duyệt có tính toán áp dụng để giải một số bài
toán ứng dụng phương pháp duyệt.
B. NỘI DUNG
I. Tư tưởng
Duyệt toàn bộ. Sau đó có thể tính toán trước một phần để giảm độ phức tạp của
thuật toán.
II. Bài toán cơ bản
A
1. Bài toán 1. Cho dãy số nguyên A1,A2,…,AN ( i <=109; N<=106) và một số nguyên
dương k (k<=106) là số cặp chỉ số(i, j) (1 ≤ i < j < N; k ≤ 10 6). Yêu cầu: với mỗi cặp
j
chỉ số (i,j) hãy tính
h i
Ah
(Tính tổng của k đoạn với mỗi cặp chỉ số (i,j) khác nhau).
Input: Vào từ file văn bản BT1.INP có cấu trúc như sau:
-
Dòng đầu gồm hai số nguyên N, S.
Dòng thứ 2 gồm N số nguyên A1,A2,…,AN .
k dòng tiếp theo chứa k cặp (i, j) theo yêu cầu.
Output: Ghi ra file văn bản BT1.OUT gồm k dòng ghi tổng k đoạn .
Ví dụ:
BT1.INP
BT1.OUT
10 3
16 12 4 5 8 8 5 32 23 12
14
25
69
37
29
68
Ràng buộc:
-
Có 60% test ứng với 40% điểm của bài có n, k ≤ 5000.
Có 40% test ứng với 30% điểm của bài có n, k ≤ 106.
Hướng dẫn
1
+ Mức độ 1. Duyệt toàn bộ k cặp (i, j).
for i:=1 to k do
begin
read(f1,x,y);
sum:=0;
for h:=i to j do sum:=sum+a[j];
end;
Độ phức tạp O(k,n);
+ Mức độ 2.
Ta có thể giảm độ phức tạp của thuật toán bằng cách tính trước mảng sum.
Gọi sum[i] là tổng các phần tử từ A1,A2,…,AN. Mảng sum được tính như sau:
s[0]:=0;
for i:=1 to n do s[i]:=s[i-1]+a[i];
Sau đó, tổng đoạn được tính như sau:
for l:=1 to k do sum: =sum[j] - s[i-1]);
Độ phức tạp (O(max(n,k)).
Chương trình mẫu
CONST fi='BT2.inp';
fo='BT2.out';
maxN=trunc(1e6)+1;
TYPE
data=longint;
VAR
a:array[1..maxN] of data;
s:array[0..maxN] of int64;
f1,f2:text;
n,k:data;
procedure
var
enter;
i:data;
begin
read(f1,n,k);
for i:=1 to n do read(f1,a[i]);
end;
procedure
var
sub1;
i,j,x,y:data;
sum:int64;
begin
2
for i:=1 to k do
begin
read(f1,x,y);
sum:=0;
for j:=x to y do
sum:=sum+a[j];
writeln(f2,sum);
end;
end;
procedure
var
chuanbi;
i:data;
begin
s[0]:=0;
for i:=1 to n do
s[i]:=s[i-1]+a[i];
end;
procedure
var
sub2;
x,y,i,j:data;
begin
chuanbi;
for i:=1 to k do
begin
read(f1,x,y);
writeln(f2,s[y]-s[x-1]);
end;
end;
procedure
main;
begin
assign(f1,fi); reset(f1);
assign(F2,fo); rewrite(f2);
enter;
if n<=5000 then sub1
else sub2;
close(f1); close(F2);
end;
3
BEGIN
main;
END.
A
2. Bài toán 2. Cho dãy số nguyên A1,A2,…,AN ( i <=109; N<=105) và một số nguyên
dương S (S<=109). Yêu cầu: Đếm số lượng dãy con liên tiếp của dãy A1,A2,…,AN có
số phần tử lớn hơn 3 và có tổng bằng S.
Input: Vào từ file văn bản BT2.INP có cấu trúc như sau:
-
Dòng đầu gồm hai số nguyên N, S.
Dòng thứ 2 gồm N số nguyên A1,A2,…,AN .
Output: Ghi ra file văn bản BT2.OUT một số nguyên duy nhất là số lượng dãy con
liên tiếp có số phần tử lớn hơn 3 và có tổng bằng S.
Ví dụ:
BT2.INP
BT2.OUT
10 45
16 12 4 5 8 8 5 32 23 12
2
Ràng buộc:
-
Có 40% test ứng với 40% điểm của bài có n ≤ 400.
Có 30% test ứng với 30% điểm của bài có n ≤ 5000.
Có 30% test ứng với 30% điểm của bài có n ≤ 105.
Hướng dẫn
*. Thuật toán 1:
- Lần lượt liệt kê tất cả các khả năng của nghiệm (Gọi là phần thử - duyệt).
- Với mỗi vector nghiệm ta kiểm tra xem nghiệm đó của thỏa mãn điều kiện
của đầu bài hay không.
Function kiemtra(i,j:longint):Boolean;
Var sum:int64;
k:longint;
Begin
Sum:=0;
For k:= i to j do sum:=sum+a[k];
Exit(sum=S);
End;
****************
Procedure try;
Var i,j:longint;
Begin
Count:=0;
For i:= 1 to n -3 do
For j:= i+3 to n do
If kiemtra(i,j) then inc(count);
End;
4
Nhận xét: Với thuật toán trên thì độ phức tạp là O(n3) nên chỉ chạy được với n<=400.
*. Thuật toán 2: Cài tiến việc kiểm tra từ O(n) về O(1).
- Ta tính toán tổng tất cả các phần tử a[i] đến a[j]. Như vậy khi kiểm tra chỉ việc
lấy ra chứ không phải tính toán nữa.
- Gọi mảng L là mảng một chiều mà L[i] là tổng các phần tử từ phần tử 1 đến
phần tử thứ i.
Procedure chuanbi;
Var i:longint;
Begin
Fillchar(L,sizeof(L),0);
For i:= 1 to n do
L[i]:=L[i-1]+a[i];
End:
****************
Function kiemtra(i,j:longint):Boolean;
Begin
Exit(L[j]-L[i-1]=S);
End;
****************
Procedure try;
Var i,j:longint;
Begin
Count:=0;
For i:= 1 to n -3 do
For j:= i+3 to n do do
If kiemtra(i,j) then inc(count);
End;
Nhận xét:
- Với thuật toán trên do ta tính trước được tổng các phần tử từ a[i] đến a[j] nên
với mỗi lần duyệt ở thủ tục Try thì ta chỉ cần lấy kết quả ra để kiểm tra => Độ phức tạp
của thuật toán là O(n2). Với độ phức tạp này ta có thể chạy được với n<=5000.
(Ta cũng có thể làm bằng cách tính tổng cộng dồn sau mỗi khi tăng j)
*. Thuật toán 3: Ta tối ưu thuật toán ở phần thử (Phần duyệt).
- Với mỗi phần tử thứ i: Ta tìm kiếm xem có bao nhiêu chỉ số j mà (j>i+3, L[i1] + S =L[j])
- Việc tìm j thỏa mãn điều kiện trên ta có thể tìm bằng thuật toán tìm kiếm nhị
phân với độ phức tạp là O(log n).
- Để tìm kiếm được ta phải sắp xếp tăng dần mảng Q (Chính là mảng L nhưng
có thêm phần chỉ số).
5
Cụ thể ta làm như sau:
- Tính mảng L - Độ phức tạp O(n).
- Tính mảng Q.
For i:= 1 to n do
Begin
Q[i].GT:=L[i];
Q[i].CS:=i;
End;
- Sắp xếp (Quicksort) mảng Q theo trường GT - Độ Phức tạp O(nlogn)
- Duyệt:
Với mỗi i ta tìm Q[j] mà Q[j].GT = S + L[i-1] và Q[i].CS>i+3.
Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phẩn kiemtra
có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Có thể chạy được
với n<=105).
Muốn viết được thuật toán trên ta phải viết được thuật toán tìm kiếm nhị phân và thuật
sắp xếp quicksort:
*. Thuật toán tìm kiếm nhị phân:
Function Nhiphan(L,H:Longint):Longint;
Var Dau,Cuoi,Giua;Longint;
Begin
Dau:=L;
Cuoi:=H;
Giua:=(Dau+Cuoi) Div 2;
While (a[Giua]<>K ) and (Dau<=Cuoi) do
Begin
If A[giua]>K then Cuoi:=giua-1
Else Dau:=Giua+1;
Giua:=(Dau+Cuoi) Div 2;
End;
If a[giua]=K then Exit(Giua) else Exit (0);
End;
*. Thuật toán sắp xếp nhanh (Quicksort).
Procedure Quicksort(L,H:Longint);
Var i,j:Longint;
x,tg:Longint;
Begin
i:=L;
j:=H;
x:=a[(L+H) Div 2];
Repeat
6
While a[i].keyx.key do dec(j);
If i<=j then
Begin
Đỗi chỗ a[i] và a[j]
Inc(i);
Dec(j);
End;
Until i>j;
If Ly.gt then Exit (1)
Else Exit(-1);
End;
Procedure Quicksort(L,H:Longint);
Var i,j:Longint;
x,tg:Longint;
Begin
i:=L;
j:=H;
x:=a[(L+H) Div 2];
Repeat
7
While a[i].keyx.key do dec(j);
If i<=j then
Begin
Đỗi chỗ a[i] và a[j]
Inc(i);
Dec(j);
End;
Until i>j;
If Li+3.
Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phần kiemtra
có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Có thể chạy được
với n<=105).
Chương trình tham khảo
CONST fi='BT2.inp';
fo='BT2.out';
maxN=trunc(1e5)+1;
TYPE data=longint;
logs=record
gt:int64;
cs:data;
end;
VAR f1,f2:text;
a:array[1..maxN] of data;
n,s,kq:data;
l:array[0..maxN] of int64;
q:array[1..maxN] of logs;
procedure
enter;
var i:data;
begin
read(f1,n,s);
l[0]:=0;
for i:=1 to n do
begin
read(f1,a[i]);
l[i]:=l[i-1]+a[i];
8
end;
end;
function
kiemtra(i,j:data):boolean;
var sum:int64;
k:data;
begin
sum:=0;
for k:=i to j do
sum:=sum+a[k];
exit(sum=s);
end;
procedure
sub1;
var i,j:data;
begin
for i:=1 to n-3 do
for j:=i+3 to n do
if kiemtra(i,j) then inc(kq);
write(f2,kq);
end;
procedure
sub2;
var i,j:data;
begin
for i:=1 to n-3 do
for j:=i+3 to n do
if l[j]-l[i-1]=s then inc(kq);
write(F2,kq);
end;
procedure
chuanbi;
var i:data;
begin
for i:=1 to n do
begin
q[i].gt:=l[i];
q[i].cs:=i;
end;
end;
function
check(a,b:logs):boolean;
begin
if a.gtj;
if i=i+3 then
begin
res:=mid; c:=mid-1;
end
else d:=mid+1;
end
else if q[mid].gt>s+l[i-1] then c:=mid-1
else d:=mid+1;
end;
exit(res);
end;
function
find2(i:data):data;
var d,c,mid,res:data;
10
begin
d:=1; c:=n; res:=0;
while (d<=c) do
begin
mid:=(d+c) div 2;
if q[mid].gt=s+l[i-1] then
begin
if q[mid].cs>=i+3 then
begin
res:=mid; d:=mid+1;
end
else d:=mid+1;
end
else if q[mid].gt>s+l[i-1] then c:=mid-1
else d:=mid+1;
end;
exit(res);
end;
procedure
sub3;
var tmp1,tmp2,i:data;
begin
chuanbi;
sort(1,n);
for i:=1 to n do
begin
tmp1:=find1(i);
tmp2:=find2(i);
if (tmp1<>0) and (tmp2<>0) then kq:=kq+tmp2-tmp1+1;
end;
write(f2,kq);
end;
procedure
main;
begin
assign(F1,fi); reset(F1);
assign(F2,fo); rewrite(F2);
enter;
kq:=0;
if n<=400 then sub1
else if n<=5000 then sub2
else sub3;
close(F1); close(F2);
end;
11
BEGIN
main;
END.
3. Bài tập 3: ESEQ
Cho dãy số nguyên A gồm N phần tử A1, A2, .., AN, tìm số cặp chỉ số i, j thỏa mãn:
i
p 1
Ap
N
q j
Aq
với 1 ≤ i < j ≤ N
Input: Vào từ file vãn bản ESEQ.INP có dạng:
-
Dòng ðầu là số nguyên dýõng N (2 ≤ N ≤ 105)
Dòng tiếp theo chứa N số nguyên A1, A2, .., AN (|Ai|<109), các số cách nhau một
dấu cách.
Output: Ghi ra file vãn bản ESEQ.OUT gồm một số là số cặp tìm ðýợc.
Ví dụ:
ESEQ.INP
3
101
ESEQ.OUT
3
Hýớng dẫn
- Duyệt i,j: Với i là phần tử cuối cùng của ðoạn 1 và j là phần tử ðầu tiên của ðoạn 2.
- Với mỗi i,j ta tìm tổng của ðoạn 1 va tổng của ðoạn 2. mất O(n).
=> Ðộ phức tạp của cả thuật toán là O(n3).
Mã code nhý sau:
For i:=1 to n-1 do
For j:=i+1 to n do
Begin
S1:=0;
For k:=1 to i do S1:=S1+a[k];
S2:=0;
For k:=j to n do S2:=S2+a[k];
If S1=S2 then inc(kq);
End;
Cải tiến 1: ta cải tiến phần kiểm tra từ O(n) về O(1) Bằng cách tính trýớc mảng cộng
dồn.
- Gọi mảng L. Trong ðó L[i] là tổng các phần tử từ phần tử 1 ðến phần từ i.
- Gọi mảng R. Trong ðó L[j] là tổng các phần tử từ phần tử j ðến phần từ n.
Thuật toán trên trở thành.
For i:=1 to n-1 do
For j:=i+1 to n do
Begin
If L[i]=R[j] then inc(kq);
End;
12
Cải tiến 2: Cải tiến phần duyệt.
Với mỗi i Ta tìm kiếm nhị phân trên mảng R=L[i]. Ðể ðếm ðýợc có bao nhiêu
R[j]=L[i] ta phải sắp xếp mảng R theo giá trị ðồng thời cũng phải lýu chỉ số ban ðầu
ðể kiểm tra thỏa mãn ðiều kiện (ix do Dec(j);
13
if i<=j then
Begin
tg:=sp[i];
sp[i]:=sp[j];
sp[j]:=tg;
inc(i);
dec(j);
end;
until i>j;
if il then quicksort(l,j);
end;
Function Lan(k,l:longint):longint;
Var tg,l1:longint;
Begin
tg:=0;
l1:=l;
While (l1>0) and (sp[l1].gt=st[k]) do
Begin
if sp[l1].cs>k then tg:=tg+1;
Dec(l1);
end;
l1:=l+1;
While (l1<=n) and (sp[l1].gt=st[k]) do
Begin
if sp[l1].cs>k then tg:=tg+1;
inc(l1);
end;
Exit(tg);
end;
Function tknp(k:longint):longint;
Var dau,cuoi,giua:longint;
Begin
dau:=1;
cuoi:=n;
while (dau<=cuoi) do
Begin
giua:=(dau+cuoi) Div 2;
if sp[giua].gt=st[k] then exit(giua);
if sp[giua].gt0 then Kq:=kq+Lan(i,tg);
end;
end;
Procedure ghikq;
Var f:text;
Begin
Assign(f,fo);
rewrite(f);
Write(f,kq);
Close(f);
end;
BEGIN
Docdl;
quicksort(1,n);
Xuli;
Ghikq;
END.
Lýu ý:
- Phải có hàm Lan sang hai bên vì ðiều kiện ðầu bài ix do dec(j);
if i<=j then
Begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
inc(i);
Dec(j);
end;
until i>j;
16
if il then quicksort(l,j);
end;
Function lan(l,k:longint):longint;
Var kq1:longint;
l1:longint;
Begin
if k=0 then exit(0);
kq1:=0;
l1:=k;
While (l1>l) and (a[l1]=a[k]) do
Begin
inc(kq1);
dec(l1);
end;
l1:=K+1;
While (l1<=n) and (a[l1]=a[k]) do
Begin
inc(kq1);
inc(l1);
end;
Exit(kq1);
end;
Function tknp(l,h,x:longint):longint;
Var dau,cuoi,giua:longint;
Begin
Dau:=l;
cuoi:=h;
While dau<=cuoi do
Begin
giua:=(dau+cuoi) div 2;
if a[giua]=x then exit(giua);
if a[giua]0 then kq:=kq+lan(i,kq1);
end;
end;
procedure ghikq;
Var f:text;
Begin
Assign(f,fo);
rewrite(f);
Write(f,kq);
Close(f);
end;
BEGIN
Docdl;
Quicksort(1,n);
Xuli;
Ghikq;
END.
5.Bài tập 5. Cam sành Hàm Yên (đề thi trại hè Hùng Vương năm 2017 môn Tin
lớp 10).
Nhân dịp Trại hè Hùng Výõng nãm nay tổ
chức tại tỉnh Tuyên Quang, ðýợc biết ở huyện
Hàm Yên có loại cam sành rất nổi tiếng nên các
ðoàn cùng nhau ðến thãm nông trang trồng cam
sành của gia ðình ông Nghiệp. Nông trang trồng
cam nhà ông ðýợc trồng trên núi cao, khí hậu
mát mẻ và ðýợc týới bằng nýớc nguồn từ ðỉnh
núi nên cam có vị ngọt mát và giá trị dinh dýỡng
cao.
Trong các ðoàn ðến tham quan có N ngýời muốn mua cam. Do mọi ngýời
muốn nhýờng nhau nên mỗi ngýời chỉ mua một quả, ngýời thứ i cho biết sẵn sàng trả
pi(ðồng) cho một quả cam.
Ông Nghiệp quyết ðịnh lựa chọn ðýa ra một mức giá cố ðịnh là (ðồng) cho
mỗi quả cam trong výờn. Vì rất thích tính cách hào phóng của khách nên ông sẽ bán
với giá cho tất cả những ngýời sẵn sàng trả giá lớn hõn . Ngoài ra, nếu có những
ngýời trả giá ðúng bằng , ông chỉ bán duy nhất cho một ngýời khách ðến sớm nhất.
Tuy hiếu khách nhýng vì miếng cõm manh áo nên ông Nghiệp vẫn muốn thu
ðýợc số tiền nhiều nhất có thế. Hãy giúp ông Nghiệp lựa chọn mức giá là một số
18
nguyên ðể có thể thu ðýợc nhiều tiền nhất từ việc bán cam cho vị khách nói trên. Biết
số cam trong výờn ðảm bảo ðủ cho tất cả khách tới thãm.
Input: Vào từ file vãn bản ORANGE.INP có cấu trúc nhý sau:
-
Dòng ðầu chứa số nguyên dýõng N là số lýợng khách muốn mua cam;
Dòng sau ghi N số nguyên dýõng p1, p2, … ,pN ( pi≤ 106) mỗi số cách nhau
bởi một dấu cách.
Output: Ghi ra file vãn bản ORANGE.OUT một số nguyên duy nhất là số tiền nhiều
nhất mà ông Nghiệp có thể thu ðýợc.
Ví dụ:
ORANGE.INP
4
1254
ORANGE.OUT
8
Ràng buộc:
- Có 30% số test ứng với 30% số ðiểm của bài có N, pi ≤ 1000, pi ≠ pj ,∀i ≠ j;
- Có 30% số test khác ứng với 30% số ðiểm của bài có N≤ 1000, pi ≠ pj ,∀i ≠ j;
- Có 20% số test khác ứng với 20% số ðiểm của bài có N ≤ 105, pi ≠ pj , ∀i ≠ j;
- Có 20% số test còn lại ứng với 20% số ðiểm của bài có N ≤ 105.
Hýớng dẫn
- Có 30% số test ứng với 30% số ðiểm của bài có N, pi ≤ 1000, pi ≠ pj ,∀i ≠ j;
Duyệt từng giá trị k = 1 → 1000, kiểm tra trực tiếp từng khách.
- Có 30% số test khác ứng với 30% số ðiểm của bài có N≤ 1000, pi ≠ pj ,∀i ≠ j;
Duyệt từng giá trị k= p1, … ,pN .
- Có 20% số test khác ứng với 20% số ðiểm của bài có N ≤ 105, pi ≠ pj , ∀i ≠ j;
Sắp xếp, thử từng giá trị = p1, … , pN . Với k=pi , số ngýời mua ðýợc là n−i + 1
- Có 20% số test còn lại ứng với 20% số ðiểm của bài có N ≤ 105.
Sắp xếp tãng dần. Giả sử từ ngýời thứ tới ngýời thứ ðýợc phép mua. Nếu trong những
ngýời này có nhiều ngýời cùng giá (hay p i=pi+1 ), giá mua sẽ là pi − 1. Nếu có duy nhất
1 ngýời có giá pi, giá mua sẽ là pi .
Chýõng trình tham khảo
USES math;
CONST fi='ORANGE.inp';
fo='ORANGE.out';
oo=trunc(1e5)+1;
maxN=trunc(1e6);
TYPE data=longint;
VAR a:array[0..maxN] of data;
f1,f2:text;
n,tmp:data;
19
procedure
enter;
var i:Data;
begin
readln(F1,n);
tmp:=0;
for i:=1 to n do
begin
read(f1,a[i]);
tmp:=max(tmp,a[i]);
end;
end;
procedure
sort(l,h:data);
var tmp,mid,i,j:data;
begin
i:=l; j:=h;
mid:=a[(l+h) div 2];
repeat
while a[i]mid do dec(J);
if i<=j then
begin
tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
inc(I); dec(J);
end;
until i>j;
if ii then c:=mid-1
else d:=mid+1;
end;
exit(res);
end;
20
- Xem thêm -