TRƯỜNG THPT CHUYÊN TỈNH LÀO CAI
TỔ TOÁN - TIN
-----------------*@*---------------------
CHUYÊN ĐỀ
NGĂN XẾP (STACK) VÀ HÀNG ĐỢI (QUEUE)
NĂM HỌC: 2015 - 2016
1
A, MỞ ĐẦU
1. Lý do chọn đề tài
Ngăn xếp và hàng đợi là hai kiểu dữ liệu trừu tượng rất quan trọng và được sử
dụng nhiều trong thiết kế thuật toán. Về bản chất, ngăn xếp và hàng đợi là danh sách
tức là một tập hợp các phần tử cùng kiểu có tính thứ tự. Ngăn xếp được sử dụng rất
nhiều trong việc giải quyết các bài toán về đồ thị trong các đề thi học sinh giỏi. Tuy
nhiên trong quá trình giảng dạy tôi thấy học sinh vẫn còn khó khăn trong việc phân
tích bài toán để có thể áp dụng được thuật toán và cài đặt giải bài toán. Vì vậy tôi
chọn chuyên đề này để giúp học sinh có cái nhìn tổng quan hơn về ngăn xếp và ứng
dụng của ngăn xếp trong giải các bài toán cụ thể.
2. Mục đích của đề tài
Về nội dung kiến thức ngăn xếp và hàng đợi đã có rất nhiều tài liệu đề cập đến, trong
chuyên đề này chúng tôi chỉ tổng hợp lại các nội dung kiến thức đã có và chủ yếu là
đưa vào áp dụng để giải một số bài toán cụ thế, để làm tài liệu tham khảo cho học
sinh và giáo viên trong quá trình học tập và giảng dạy các đội tuyển học sinh giỏi
2
B. NỘI DUNG
I, DỮ LIỆU KIỂU NGĂN XẾP (STACK)
1, Khái niệm:
Stack là một kiểu danh sách tuyến tính đặc biệt mà phép
bổ sung và loại bỏ luôn thực hiện ở một đầu gọi là đỉnh (Top).
Có thể hình dung nó như cơ cấu của một hộp chứa đạn súng
Top
trường hoặc súng tiểu liên. Khi lắp đạn hay lấy đạn ra cũng chỉ
ở đầu hộp. Viên đạn vừa lắp vào sẽ ở trên đỉnh hộp và viên đạn
Bottom
lắp vào đầu tiên sẽ ở đáy hộp (Bottom). Viên đạn nạp vào sau
cùng lại là viên đạn bắn đầu tiên.
Với nguyên tắc hoạt động của stack “vào sau ra trước” nên nó còn được gọi với tên danh
sách kiểu LIFO (Last - In - First - Out).
2, Cài đặt stack
Ta dùng mảng Stack[I. Nmax] mà ″đáy″ của Stack là ở đầu tức chỉ số là 1. Việc đưa vào
(Push) hay lấy ra (Pop) được thực hiện phần đuôi của mảng nhờ một con trỏ P. Các thao
tác đưa vào hay lấy ra đó ứng với các thủ tục hàm thích hợp. Giả sử Stack chứa các phần
tử là các số nguyên thì ta sẽ có các thủ tục và hàm sau:
3, Các phép xử lý trên stack
a. Khởi tạo stack rỗng: P := 0;
b. Kiểm tra một stack có rỗng hay không:
Function StackEmpty:Boolean; {Kiểm tra stack có rỗng không}
Begin
StackEmpty:=P=0;
End;
c. Thủ tục lấy một phần tử ở đỉnh stack
Function Pop: Integer; {Lấy 1 phần tử ra khởi stack}
Begin
Pop:=Stack[P];
Dec(P);
End;
d. Thủ tục đẩy một phần tử vào stack:
Procedure Push (N:Integer); {Đưa số N vào Stack}
Begin
Inc (P);
Stack[P]:=N;
End;
4, Ứng dụng của ngăn xếp:
3
a, Khử đệ quy thuật toán sắp xếp Quicksort;
Const
Nmax=5000;
Var
n, i, j, x, l, r, tg:Integer;
s: 0.. Nmax;
A: Array[1..Nmax] of Integer;
Stack: Array [1..Nmax] of Record l,
r : Integer;
End;
Procedure Sort;
Begin
S:=1; Stack [s].l:=1;
Stack [s].r:=n ;
Repeat
l:=Stack[s].1; r:=Stack[s].r;
Dec(s);
Repeat
i:=1; j:=r;
x:=A[(1+r)div 2]
Repeat
While a[i] < x
Do Inc(i);
While a [j] > x
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;
If i < r then
Begin
S: = s +1 ;
Stack [s].l: = 1;
Stack [s].r:= r ;
End; r : = j;
Until 1> r ;
Until S= 0;End;
b, Chuyển biểu thức từ dạng trung tố sang dạng hậu tố
Để minh hoạ ta xét biểu thức trung tố sau đây: 7 + 2 * 3. Khi đọc biểu thức này từ
trái sang phải, giá trị 7 được hiển thị ngay lập tức. Tiếp theo là toán tử +, nhưng nó được
4
lưu trữ vì toán hạng bên phải của nó chưa được hiển thị, vì vậy nó được đẩy vào ngăn xếp
các toán tử:
Đầu ra
Ngăn xếp
7
+
Tiếp theo là toán hạng 2 được đọc và được hiển thị. Lúc này nó phải được xác
định là toán hạng bên phải của toán tử + hay là toán hạng bên trái của toán tử tiếp theo.
Để xác định điều này ta so sánh toán tử + ở đỉnh ngăn xếp với toán tử tiếp theo *. Bởi vì
* được ưu tiên hơn +, toán hạng 2 là toán hạng bên trái của toán tử *. Vì vậy ta đẩy * vào
ngăn xếp và tìm toán hạng bên phải của nó:
Đầu ra
Ngăn xếp
*
72
+
Toán hạng 3 được đọc và hiển thị. Bởi vì lúc này ta đạt đến kết thúc biểu thức,
toán hạng bên phải của toán tử * ở đỉnh ngăn xếp được tìm ra, toán tử * có thể lấy ra từ
ngăn xếp và hiển thị:
Đầu ra
Ngăn xếp
723*
+
Dấu kết thúc biểu thức cũng chỉ ra rằng toán hạng bên phải của toán tử còn lại +
trong ngăn xếp được tìm ra, vì vậy nó được lấy ra và hiển thị, ta được biểu thức RPN: 7 2
3*+
Các dấu ngoặc trong biểu thức trung tố không gây khó khăn thực sự nào cả. Dấu
ngoặc bên trái chỉ ra bắt đầu một biểu thức con và khi đọc nó được đẩy vào ngăn xếp.
Đến khi gặp dấu ngoặc phải, các toán tử được lấy ra từ ngăn xếp cho đến khi dấu ngoặc
trái tương ứng xuất hiện ở đỉnh. Lúc này, biểu thức con ban đầu trong các dấu ngoặc đã
được chuyển sang dạng RPN, vì vậy có thể bỏ qua chúng, vì vậy phép chuyển đổi tiếp
tục.
Thuật toán chuyển từ dạng trung tố sang dạng RPN:
1. Khởi động một ngăn xếp rỗng các toán tử.
2. While do
a. Đọc phần tử x (hằng số, biến số, toán tử số học, các dấu ngoặc trái và ngoặc phải)
tiếp theo trong biểu thức trung tố.
b. Nếu phần tử x là:
- Dấu ngoặc trái: đẩy nó vào ngăn xếp.
- Dấu ngoặc phải: lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi dấu
ngoặc trái được đọc. Nếu ngăn xếp rỗng thì xảy ra lỗi.
5
Toán tử: nếu ngăn xếp rỗng hay x được ưu tiên hơn phần tử ở đỉnh ngăn xếp,
đẩy x vào ngăn xếp.
Nếu khác, lấy ra và hiển thị phần tử ở đỉnh ngăn xếp; Lặp lại việc so sánh x với
phần tử ở đỉnh ngăn xếp. (Dấu ngoặc trái được xem ưu tiên thấp hơn các toán
tử).
- Toán hạng: hiển thị nó.
3. Khi đạt đến kết thúc của biểu thức trung tố, lấy ra và hiển thị các phần tử của ngăn
xếp cho đến khi ngăn xếp rỗng.
-
Cài đặt: chương trình này giả sử các toán hạng, toán tử chỉ gồm 1 kí tự và giả sử biểu
thức trung tố là hợp lệ và chỉ kiểm tra rất ít tính đúng đắn của biểu thức trung tố.
Program Infix_to_rpn;
Uses crt;
Const
MaxSize = 100;
EndMask = ';';
{ dau ket thuc bieu thuc trung to }
Var
infix, rpn : string;
top : integer;
stack : array[1..MaxSize] of char;
Function Pop : char;
Begin
Pop := stack[top];
top := top - 1;
End;
Procedure Push(x : char);
Begin
top := top + 1;
stack[top] := x;
End;
Function Priority(operator : char) : integer;
{ ham tra lai do uu tien cua cac toan tu }
Begin
case operator of
'('
: Priority:=0;
'+', '-' : Priority := 1;
'*', '/' : Priority := 2;
end;
End;
Procedure Convert_to_rpn;
6
Var
i : integer;
x, symbol : char;
error, donePop : boolean;
Begin
write('Bieu thuc dang RPN la: ');
rpn := '';
top := 0;
error := false;
i := 1;
x := infix[1];
while (x <> EndMask) and not error do
begin
while infix[i] = ' ' do i := i + 1; { nhay qua cac dau cach }
x := infix[i];
if x = EndMask then break;
case x of
'(' : Push(x);
')' : begin
donePop := false;
repeat
if top = 0 then error := true
else begin
symbol := Pop;
if symbol = '(' then donePop := true
else rpn := rpn + symbol;
end;
until donePop or Error;
end;
'+', '-', '*', '/':
begin
donePop := false;
while (top <> 0) and (not donePop) do
begin
symbol := Pop;
if Priority(x) <= Priority(symbol) then rpn:=rpn+symbol
else begin
Push(symbol);
donePop := true;
end;
end;
Push(x);
end;
7
else rpn := rpn + x; { x la toan hang}
end; { of case }
i := i + 1;
end; { of while }
while (top <> 0) and (not error) do
begin
symbol := Pop;
if symbol = '(' then error := true
else rpn := rpn + symbol;
end;
if error then writeln('')
else writeln(rpn);
End;
Procedure Read_data;
Begin
write('Vao bieu thuc dang trung to: '); readln(infix);
infix := infix + EndMask;
End;
Begin
clrscr;
Read_data;
Convert_to_rpn;
readln;
End.
II, DỮ LIỆU KIỂU HÀNG ĐỢI (QUEUE)
1. Khái niệm hàng đợi (Queue)
Khác với stack, queue là một danh sách tuyến tính mà phép bổ sung thực hiện ở một đầu,
gọi là lối sau (rear) và phép loại bỏ thực hiện ở một đầu khác, gọi là lối trước (front).
Như vậy cơ cấu của queue giống như một hàng đợi (như là một hàng người chờ tính tiền
ở siêu thị, một dãy các máy bay chờ hạ cánh ở một sân bay, ...) vào ở một đầu, ra ở đầu
khác, nghĩa là vào trước thì ra trước. Vì vậy queue được gọi là danh sách kiểu FIFO (First
- In - First - Out).
Quầy bán vé
Lối ra
8
Lối vào
2. Cài đặt queue
Có thể dùng mảng làm cấu trúc lưu trữ queue. Để truy nhập vào queue ta phải dùng 2
biến trỏ: font trỏ đầu hàng đợi và rear trỏ cuối hàng đợi. Một phần tử được lấy ra khỏi
queue bằng cách tìm phần tử của mảng tại vị trí font và tăng font thêm 1. Một phần tử
được thêm vào queue bằng cách lưu trữ nó tại vị trí rear của mảng, giả sử rear không
vượt quá độ dài lớn nhất MaxSize của mảng, sau đó tăng rear thêm 1. Sau đây ta xét một
vài cấu hình cụ thể của queue với MaxSize = 5:
rear = 4
7
-8
5
font = 1
Giả sử 2 phần tử được lấy ra:
rear = 4
5
font = 3
và phần tử 9 và 6 được thêm vào:
5
9
dQ = 3
rear = 6
6
Cài đặt:
Const
SizeQ = 5000;
Type
Td = Record d,c: Integer; End;
Var
Q: Array [1.. SizeQ ] of Td;
L,R: Integer;F: Text;
Procedure Put (NewOb:Td); {Đưa vào hàng đợi }
Begin
Inc (R);
9
Q[r-1) div Sizequ +1]: = NewOb;
End;
Procedure Get(Var FistOb :Td); {lấy ra khỏi hàng đợi }
Begin
Inc(L);
FistOb:=Q[L Mod SizeQư1];
End;
Function Qempty:Boolean;{Kiểm tra hàng đợi có rỗng hay không }
Begin
Qempty:=L – R >0;
End;
Function Qfull: Boolean; {Kiểm tra xem hàng đợi đã đầy hay chưa }
Begin
QFull : = r – 1 > SizeQ;
End;
3, Ứng dụng của Queue:
Ứng dụng của hàng đợi điển hình là thuật toán tìm kiếm theo chiều rộng
Trên bàn cờ vua quốc tế N*N ( n≤ 50) trong đó có một số ô có mìn. Từ một ô không có
mìn cho trước con mã có thể đi đến một ô khác được hay không. Nếu được hãy chỉ ra
đường đi ngắn nhất.
File dữ liệu:
- Dòng 1 là N (kích thước bàn cờ).
- Dòng thứ nhất trong số N dòng tiếp theo:
* đầu tiên là K số mìn trên dòng đó, tiếp theo là K số, mỗi số là chỉ số cột có mìn.
- Dòng cuối ghi 4 số d1, c1,d2, c2:
* (d1,c1): toạ độ ô xuất phát.
* (d2,c2): Toạ độ ô đích.
Nhận xét: Với bài này ta có thể ứng dụng loang theo chiều rộng như sau:
Dùng một mảng A[i,j]:
+ A[i,j] = 0 nếu ô (i,j) có mìn.
+ A[i,j] = 1 nếu ô (i,j) không có mìn và mã chưa đến.
+ A[i,j]= k (k>1) nếu ô (i,j) là bước thứ k của con mã.
Put(ô xp); {đưa vào hàng đợi toạ độ ô xuất phát}.
Nhan { ô xp }: = 0; {khởi tạo nhãn của ô xuất phát}
Repeat
For { ô kề ô 1} do
if {ô để không có mình} then
if { ô kề chưa đến} then
Begin
Nhan [ôkề]: = Nhan [ô] +1;
Put (ô kề)
End;
10
Until QuEmpty;
if Nhan [ô đích] = vô cùng Then { thông báo không đến}
Else
Repeat
Tìm lật ngược kể từ ô đích;
Until Nhan [ô i] = 0;
III. BÀI TẬP ÁP DỤNG
Bài 1. Chiến trường Ô qua – Nguồn bài: vn.spoj.com
Lại nói về Lục Vân Tiên, sau khi vượt qua vòng loại để trở thành Tráng Sỹ, anh đã
gặp được Đôrêmon và được chú mèo máy cho đi quá giang về thế kỷ 19. Trở lại quê
hương sau nhiều năm xa cách, với tấm bằng Tráng Sỹ hạng 1 do Liên Đoàn Type Thuật
cấp, anh đã được Đức Vua cử làm đại tướng thống lãnh 3 quân chống lại giặc Ô Qua xâm
lăng.
Đoàn quân của anh sẽ gồm N đại đội, đại đội i có A[i] (A[i] > 0) người. Quân sỹ
trong 1 đại đội sẽ đứng thành 1 cột từ người 1 -> người A[i] , như vậy binh sỹ sẽ đứng
thành N cột. Vì Vân Tiên quyết 1 trận sẽ đánh bại quân Ô Qua nên đã cử ra 1 quân đoàn
hùng mạnh nhất. Trong sử cũ chép rằng, quân đoàn của Vân Tiên cử ra lúc đó là một
nhóm các đại đội có chỉ số liên tiếp nhau (tức là đại đội i , i + 1 , … j) - Vì sử sách thì
mối mọt hết cả nên chỉ biết được mỗi thế. Ngoài ra theo giang hồ đồn đại thì sức mạnh
của 1 quân đoàn = số người của đại đội ít người nhất * số đại đội được chọn.
Nhiệm vụ của bạn là dựa trên các thông số của các nhà khảo cổ có được , hãy cho
biết quân đoàn mà Vân Tiên đã chọn ra là từ đại đội nào đến đại đội nào. Chú ý nếu có
nhiều phương án thì ghi ra phương án mà chỉ số của đại đội đầu tiên được chọn là nhỏ
nhất .
Input
Dòng 1 : Số T là số bộ test .
T nhóm dòng tiếp theo , mỗi nhóm dòng mô tả 1 bộ test . Nhóm dòng thứ i :
o Dòng 1: N (N <= 30000)
11
o Dòng 2: N số nguyên mô tả N số A[1], A[2], … A[N] (các số nguyên
dương <= 30000).
.
Output
Kết quả mỗi test ghi ra trên 1 dòng, gồm 3 số: sức mạnh quân đoàn mạnh nhất, chỉ
số của đại đội đầu tiên và chỉ số của đại đội cuối cùng được chọn.
Ví dụ:
Input
Output
2
4
3431
4
1213
913
414
Hướng dẫn thuật toán:
Xin tóm tắt lại đề bài như sau:
Trong tất cả các đoạn phần tử liên tiếp, hãy chọn ra đoạn [i … j] sao cho tích:
min{A[i],…,A[j]} * (j – i + 1) đạt giá trị lớn nhất.
- Với đặc điểm của bài toán, rõ ràng với phần tử A[i] ta sẽ phải tìm hai chỉ số j và k
(trong đó A[j] phía trước A[i] và A[k] phía sau A[i]) sao cho A[j] gần với A[i] nhất và
A[j] < A[i], A[k] gần với A[i] nhất và A[k] < A[i]. Từ đó cập nhật giá trị lớn nhất vơi
A[i] * (k – j – 1).
- Để tìm A[j] ta có thể duyệt từ A[i] ngược về 1, để tìm A[k] ta sẽ duyệt từ A[i] tiếp
tục đến N, tuy nhiên cách này sẽ bị lỗi quá thời gian. Ta có thể sử dụng STACK để
làm giảm thời gian tìm kiếm A[j] và A[k]:
+ Gọi L[i] là chỉ số của phần tử A[L[i]] sao cho L[i] < i và L[i] gần với i nhất để
A[L[i]] <= A[i].
Với ví dụ: A ={ 3 4 3 1}
thì mảng L = {0,1,0,0}
12
Sử dụng STACK để lưu lại các chỉ số của các phần tử trong dãy sao cho luôn duy trì
STACK ở trạng thái A[STACK[i]] tăng dần tử đáy lên trên.
Xét A[i]: so sánh A[i] với phần tử A[STACK[top]] (trong đó top là phần tử ở đỉnh của
STACK).
- Nếu A[i] > A[STACK[top]] thì bổ sung i vào STACK và L[i] = STACK[top]
- Nếu A[i] <= A[STACK[top]] thì loại dần các phần tử ở đỉnh STACK cho đến
khi A[i] > A[STACK[top]]. Lúc đó gán L[i] = STACK[top]
+ Tương tự gọi R[i] là chỉ số của phần tử A[R[i]] sao cho i < R[i] và R[i] gần với i
nhất để A[R[i]] < A[i].
Cách tìm mảng R tương tự như với việc tìm mảng L nhưng theo chiều ngược lại.
KQ cuối cùng = max{A[i] * (R[i] – L[i] + 1)}
Bài 2. KIỂM TRA TIN HỌC (PREVNOI 2013- Nguyễn Thế Hùng)
Dạy tin học cơ sở luôn là công việc vất vả ngay cả với những giáo viên nhiều kinh
nghiệm như thầy HUNGNT. Trong giờ bài tập tin học, có
học sinh ngồi quanh một bàn
tròn, các học sinh được đánh số từ 1 tới theo chiều kim đồng hồ. Xuất phát từ một vị trí
từ đầu buổi học, thầy HUNGNT phải đi một vòng quanh bàn theo chiều kim đồng hồ để
hướng dẫn từng bạn theo đúng thứ tự thầy đi qua. Mỗi bạn được thầy hướng dẫn đúng
micro giây (μs) và sau đó bắt tay vào lập trình ngay trong khi thầy chuyển sang hướng
dẫn bạn kế tiếp theo chiều kim đồng hồ…, thời gian di chuyển của thầy coi như không
đáng kể.
Do biết rõ kỹ năng lập trình của từng bạn, thầy HUNGNT có thể ước lượng chính xác
rằng bạn học sinh thứ
sau khi được thầy hướng dẫn sẽ cần đúng 𝑎𝑖 μs để viết xong
chương trình của mình (∀𝑖 = 1,2,… , 𝑛). Vấn đề là thầy muốn kết thúc buổi học càng sớm
càng tốt, muốn vậy, việc chọn học sinh nào hướng dẫn đầu tiên phải được tính toán kỹ
lưỡng…
Yêu cầu: Bạn được cho biết số , giá trị , dãy 𝐴 = (𝑎1, 𝑎2,… , 𝑎𝑛). Hãy giúp thầy
HUNGNT chọn vị trí xuất phát sao cho thời gian từ lúc bắt đầu buổi học cho tới khi tất cả
các học sinh viết xong chương trình của mình là nhỏ nhất.
Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy
dương 𝑝, 𝑞, 𝑚, trong đó mỗi phần tử
sẽ được cho bởi ba số nguyên
được xác định theo công thức:
13
𝑎𝑖 = (𝑝 ∗ 𝑖) mod 𝑚 + 𝑞 (∀𝑖: 1 ≤ 𝑖 ≤ 𝑛)
Dữ liệu: Vào từ file văn bản PERIOD.INP
Dòng 1 chứa hai số nguyên dương 𝑛, Δ (𝑛 ≤ 5.10 6 ; Δ ≤ 10 9 )
Dòng 2 chứa ba số nguyên dương 𝑝, 𝑞, 𝑚 xác định dãy (𝑝, 𝑞,
𝑚 ≤ 10 9) Các số trên một dòng của input file được ghi cách
nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản PERIOD.OUT một số nguyên duy nhất là thời gian (tính
bằng μs) từ lúc bắt đầu buổi học cho tới khi tất cả các học sinh viết xong chương trình
theo phương án tìm được.
Ví dụ
PERIOD.INP
53
219
PERIOD.OUT
18
Giải thích: Δ = 3; Dãy 𝐴 = (3,5,7,9,2).
Phương án tối ưu: Thầy bắt đầu với học sinh 2,
Thời điểm viết xong chương trình của từng học sinh như sau:
Học sinh 2: 3 + 5 = 8
Học sinh 3: 6 + 7 = 13
Học sinh 4: 9 + 9 = 18
Học sinh 5: 12 + 2 = 14
Học sinh 1: 15 + 3 = 18
40% số điểm ứng với các test có 𝑛 ≤ 10 3
30 % số điểm ứng với các test có
30% số điểm ứng với các test có 𝑛 ∈ [10 6,5.10 6 ]
Hướng dẫn giải thuật :
Xây dựng dãy 𝑏1,𝑏2,…,𝑏2𝑛−1 từ dãy
như sáu:
𝑏1 =𝑎1 +Δ
𝑏2 =𝑎2 +2Δ
…
14
𝑏𝑛 =𝑎𝑛 +𝑛Δ
𝑏𝑛+1 =𝑎1 +(𝑛+1)Δ
𝑏𝑛+2 =𝑎2 +(𝑛+2)Δ
…
𝑏2𝑛−1 =𝑎𝑛−1 +( 𝑛−1)Δ
Có thể hiểu là 𝑏𝑖 được tính bằng phần tử thứ trong dãy theo vòng tròn cộng thêm 𝑖Δ.
Dễ thấy rằng nếu HUNGNT bắt đầu từ học sinh 1 thì thời gian giờ học kéo dài là
max{𝑏[1…𝑛]}. Nếu bắt đầu từ học sinh 2 thì thời gian giờ học kéo dài là
max{𝑏[2…𝑛+1]}−Δ… Tổng quát: nếu bắt đầu từ học sinh thì thời gian giờ học kéo dài
là
Từ đây có thể tóm tắt thuật toán như sáu: Với mỗi vị trí , ta cần nhánh chóng xác định
𝑀[𝑖] là giá trị lớn nhất trong phần tử tính từ . Khi đó đáp số là
.
Việc xác định giá trị lớn nhất trong các đoạn gồm phần tử liên tiếp trong dãy có thể
thực hiện trong thời gian Ο(𝑛) bằng cách sử dụng hàng đợi hái đầu chứa các chỉ số
trong với các phép toán:
GetFront: Trả về phần tử đầu
GetRear: Trả về phần tử cuối
PopFront: Hủy phần tử đầu
PopRear: Hủy phần tử cuối
Push( ): Đẩy phần tử vào cuối hàng đợi .
Q := ;
for i := 1 to 2n – 1
do begin
while (Q ≠ ) & (a[GetRear] ≤ a[i]) do
PopRear;
Push(i);
if GetFront + n
≤ i then
PopFront; if i ≥
n then
M[n – i + 1] :=
GetFront end;
return
Các phép toán của hàng đợi hai đầu có thể cài đặt bằng mảng với hai chỉ số đầu cuối hoặc
STL’s deque. Tất cả các phép toán đó có độ phức tạp Ο(1). Thuật toán sử dụng lệnh
Push vì vậy có tổng cộng không quá lệnh PopRear và PopFront. Từ đó suy ra thời gian
thực hiện giải thuật là Ο(𝑛).
Bài 3: Optimal Programs
15
File vào
File ra
File chương trình
Giới hạn thời gian
OPTIMAL.INP
OPTIMAL.OUT
OPTIMAL.PAS
1 giây
Như bạn đã biết, viết chương trình thường là việc không dễ dàng. Mọi việc thậm trí
trở nên khó khăn nếu chương trình của bạn cần được hoàn thành nhanh nhất có thể. Và
đôi khi cũng có lý do để làm việc đó. Rất nhiều chương trình lớn như hệ điều hành hoặc
cơ sở dữ liệu gặp phải sự “tắc nghẽn” - các đoạn mã được thực hiện đi và thực hiện lại,
và chiếm một phần lớn thời gian chạy. ở đây người ta thường phải viết lại đoạn mã đó
bằng hợp ngữ (assembly), từ đó thời gian chạy đạt được nhỏ nhất và sẽ rất quan trọng nếu
đoạn mã này được thực hiện hàng tỉ lần.
Trong bài toán này, chúng ta xem xét nhiệm vụ tự động sinh ra mã hợp ngữ tối ưu.
Cho trước một hàm số (như là một dãy các cặp vào/ra), bạn phải tạo ra một chương trình
hợp ngữ ngắn nhất để tính hàm số này.
Các chương trình bạn tạo ra sẽ phải chạy trên một stack cơ sở, nó chỉ hỗ trợ 5 câu
lệnh: ADD, SUB, MUL, DIV và DUP. Bốn câu lệnh đầu lấy ra 2 phần tử trên đỉnh stack
và đẩy vào stack tương ứng tổng, hiệu, tích hoặc thương nguyên của phép chia (giống
phép toán div trong Pascal) của chúng. Câu lệnh DUP đẩy thêm vào một phần tử giống
phần tử trên đỉnh stack. Như vậy, nếu các câu lệnh được áp dụng trên một stack với 2
phần tử trên đỉnh là a và b thì kết quả của stack như sau:
Stack
lúc đầu
a
b
c
...
...
AD
D
a+b
c
...
...
SU
B
MU
L
b-a
c
...
...
a*b
c
...
...
DIV
b div a
c
...
...
DU
P
a
a
b
c
...
...
Tại thời điểm bắt đầu thực hiện chương trình, stack sẽ chỉ chứa 1 số nguyên: số
vào. Tại thời điểm kết thúc tính toán, stack cũng phải chứa duy nhất một số nguyên, số
này là kết quả của sự tính toán.
Có 3 trường hợp mà stack rơi vào trạng thái lỗi:
Câu lệnh DIV được thực hiện và phần tử trên đỉnh stack là 0.
Các lệnh ADD, SUB, MUL hoặc DIV được thực hiện trong khi stack chỉ chứa 1 phần
tử.
Một phép tính sinh ra giá trị có giá trị tuyệt đối lớn hơn 30000.
16
Dữ liệu: File vào bao gồm các mô tả một dãy các hàm số. Mỗi mô tả bắt đầu với một
dòng chứa một số nguyên n (n 10), là số các cặp vào/ra tiếp theo. Hai dòng tiếp theo:
dòng thứ nhất chứa n số nguyên x1 , x2 , ..., xn (tất cả khác nhau) và dòng thứ hai chứa y1,
y2, ..., yn . Các số có giá trị tuyệt đối không vượt quá 30000.
Kết thúc file vào bằng một trường hợp kiểm tra bắt đầu với n = 0. Trường hợp kiểm tra
này là không phải xử lý.
Kết quả: Bạn phải tìm chương trình ngắn nhất tính hàm f, sao cho f(xi) = yi với mọi i
1, ..., n. Điều này nghĩa là chương trình bạn đưa ra có thể không vào trạng thái lỗi nếu
thực hiện các dữ liệu vào xi (mặc dù nó có thể rơi vào trạng thái lỗi đối dữ liệu vào khác).
Chỉ xem xét các chương trình có nhiều nhất 10 câu lệnh.
Với mỗi một mô tả hàm, đầu tiên ghi ra số thứ tự của mô tả đó. Sau đó ghi ra dãy các câu
lệnh làm nên chương trình ngắn nhất tính hàm cho trước này. Nếu có nhiều hơn một
chương trình như vậy, thì hãy đưa ra chương trình nhỏ nhất theo thứ tự sắp xếp từ điển.
Nếu không có chương trình có tối đa 10 câu lệnh thì in ra dòng chữ “Impossible”. Nếu
chương trình ngắn nhất có không câu lệnh thì in ra “Empty Sequence”.
Ghi một dòng trắng sau mỗi trường hợp kiểm tra.
Ví dụ:
OPTIMAL.INP
OPTIMAL.OUT
4
Program 1
1234
DUP DUP MUL
0 -2 -6 -12
SUB
3
123
Program 2
1 11 2003
Impossible
1
2003
Program 3
2003
Empty sequence
0
Program Optimal_program;
Uses crt;
Const
fi = 'Optimal.inp';
fo = 'Optimal.out';
max = 10;
max_value = 30000;
cmd : array[1..5] of string[3]
= ('ADD', 'DIV', 'DUP', 'MUL', 'SUB');
{ sap theo thu tu tu dien }
Type
Sequence = array[1..max] of longint;
Var
n, d, best : integer;
a, b, x, y : Sequence;
17
stack : array[1..max] of Sequence;
inp, out : text;
Function Read_data : integer;
Var i : integer;
Begin
d := d + 1;
read(inp, n);
for i := 1 to n do read(inp, a[i]);
for i := 1 to n do read(inp, b[i]);
Read_data := n;
End;
Procedure Try(i, top : integer);
Var
j, k : integer;
s, t, z : Sequence;
Begin
if i >= best then exit; { cat nhanh }
if top = 1 then
{ kiem tra phuong an hien tai }
begin
j := 1;
while (j <= n) and (b[j] = stack[top, j]) do j := j + 1;
if j > n then
{ tim thay phuong an tot hon }
begin
best := i - 1;
y := x;
exit;
end;
end;
if i > max then exit;
{ vuot qua 10 cau lenh }
for j := 1 to 5 do
begin
if (j <> 3) and (top < 2) then continue;
if (j = 3) and (top = max) then continue;
x[i] := j;
case j of
1 : { ADD }
for k := 1 to n do
s[k] := stack[top - 1, k] + stack[top, k];
2 : { DIV }
18
begin
k := 1;
while (k <= n) and (stack[top, k] <> 0) do
begin
s[k] := stack[top - 1, k] div stack[top, k];
k := k + 1;
end;
if k <= n then continue;
end;
3 : { DUP }
begin
for k := 1 to n do
stack[top + 1, k] := stack[top, k];
Try(i + 1, top + 1);
continue;
end;
4 : { MUL }
for k := 1 to n do s[k] := stack[top - 1, k] * stack[top, k];
5 : { SUB }
for k := 1 to n do s[k] := stack[top - 1, k] - stack[top, k];
end;
k := 1;
while (k <= n) and (abs(s[k]) <= max_value) do k := k + 1;
if k <= n then continue;
t := stack[top - 1];
z := stack[top];
stack[top - 1] := s;
Try(i + 1, top - 1);
stack[top - 1] := t;
stack[top] := z;
end;
End;
Procedure Xu_ly;
Var i : integer;
Begin
best := max_value;
for i := 1 to n do stack[1, i] := a[i];
Try(1, 1);
End;
19
Procedure Ghi_kq;
Var i : integer;
Begin
writeln(out, 'Program ', d);
if best > max then writeln(out, 'Impossible')
else
if best = 0 then writeln(out, 'Empty sequence')
else
begin
for i := 1 to best do write(out, cmd[y[i]], ' ');
writeln(out);
end;
writeln(out);
End;
Begin
assign(inp, fi); reset(inp);
assign(out, fo); rewrite(out);
d := 0;
repeat
if Read_data = 0 then break;
Xu_ly;
Ghi_kq;
until false;
close(inp); close(out);
End.
Bài 4: THU THẬP CỔ VẬT
Sau khi phát hiện ra kinh thành Thăng Long xưa ngay giữa thủ đô Hà Nội, các nhà
sử học muốn thu thập tất cả các cổ vật vô giá. Để đơn giản ta coi khu vực khai quật là
một hình chữ nhật kích thước M*N được chia thành các ô vuông đơn vị 1*1. Mỗi ô có
thể là vật cản, ô trống hoặc có cổ vật. Có thể đi từ một ô đến ô không có vật cản kề cạnh
với nó. Khi các nhà sử học đến một ô có cổ vật, tất cả các cổ vật tại ô đó được thu thập.
Ban đầu có hơn 100 nhà sử học cùng đứng tại một ô nào đó. Tại thời điểm này hoặc
sau mỗi lần tới một ô có cổ vật, các nhà sử học có thể tách ra làm nhiều nhóm đi theo các
20
- Xem thêm -