TRƯỜNG THPT CHUYÊN TỈNH LÀO CAI
TỔ TOÁN - TIN
-----------------*@*---------------------
CHUYÊN ĐỀ
NGĂN XẾP (STACK)
NĂM HỌC: 2014 - 2015
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 đã có rất nhiều tài liệu đề cập đến, trong
chuyên đề này 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
B. NỘI DUNG
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
Top
chứa đạn súng trường hoặc súng tiểu liên. Khi lắp đạn hay
Bottom
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 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 cài đặt ngăn xếp như một mảng chứa các phần tử của ngăn xếp và
một biến top để lưu trữ vị trí của phần tử đỉnh trong ngăn xếp.
Const
MaxSize = 100;
Type
ElementType = integer;
}
{ độ dài cực đại của stack }
{ kiểu các phần tử của stack
2
StackType = array[1..MaxSize] of ElementType;
Var
top : integer;
stack : StackType;
3, Các phép xử lý trên stack
a. Khởi tạo stack rỗng: top := 0;
b. Kiểm tra một stack có rỗng hay không:
if top = 0 then < stack rỗng >
else < stack không rỗng >;
c. Thủ tục lấy một phần tử ở đỉnh stack
Function Pop : ElementType; { Trả lại phần tử ở trên đỉnh
stack }
Begin
if top = 0 then writeln('STACK can!')
else begin
Pop := stack[top];
top := top - 1;
end;
End;
d. Thủ tục đẩy một phần tử vào stack:
Procedure Push(x : ElementType); { Đẩy phần tử x vào ngăn
xếp }
Begin
if top = MaxSize then writeln('STACK tran!')
else begin
top := top + 1;
stack[top] := x;
end;
End;
4, Ứng dụng của ngăn xếp: ký pháp nghịch đảo Ba Lan (RPN- Reverse
Polish Notation)
Nhiệm vụ của bộ dịch (compiler) là tạo ra các chỉ thị máy cần thiết để
thực hiện các lệnh của chương trình gốc viết trong một ngôn ngữ lập trình
cấp cao. Một phần của nhiệm vụ này là tạo ra các chỉ thị máy để đánh giá
biểu thức số học. Chẳng hạn như trong lệnh gán x := a b + c; bộ dịch phải
tạo ra các chỉ thị máy tương tự như sau:
Loa a
; nạp giá trị của ô nhớ a vào thanh ghi dự trữ
3
; nhân giá trị của ô nhớ b với giá trị trong thanh ghi dự trữ
; cộng thêm giá trị của thanh ghi dự trữ với giá trị trong ô nhớ c
; lưu trữ giá trị trong thanh ghi dự trữ vào ô nhớ x
Trong đa số các ngôn ngữ lập trình, các biểu thức số học được viết
như dạng thông thường của toán học, nghĩa là theo kí pháp trung tố (Infix
notation): mỗi toán tử 2 ngôi được đặt giữa 2 toán hạng và có thể thêm dấu
ngoặc. Nhiều bộ dịch trước hết chuyển các biểu thức trung tố này sang kí
pháp hậu tố (Postfix notation) hay tiền tố (Prefix notation). ở dạng hậu tố các
toán tử đi sau toán hạng và ở dạng tiền tố thì các toán tử đi trước toán hạng.
Ví dụ:
Infix
2(3+4)
Postfix 2 3 4 +
Prefix
2+34
Mul b
Add c
Sto x
Những năm đầu 1950, nhà lôgíc học Ba Lan: Jan Lukasiewicz đã phát
hiện rằng các dấu ngoặc là không cần thiết trong kí pháp hậu tố cũng như
tiền tố. Sau đây ta chỉ xét đối với kí pháp hậu tố, còn gọi là kí pháp nghịch
đảo Ba Lan RPN - Reverse Polish Notation (ta có thể suy ra hoàn toàn tương
tự với kí pháp tiền tố).
5, 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 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
*
4
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.
- 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.
5
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;
Var
i : integer;
x, symbol : char;
error, donePop : boolean;
Begin
write('Bieu thuc dang RPN la: ');
rpn := '';
top := 0;
6
error := false;
i := 1;
x := infix[1];
while (x <> EndMask) and not error do
begin
while infix[i] = ' ' do i := i + 1;
dau cach }
x := infix[i];
if x = EndMask then break;
{ nhay qua cac
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;
else rpn := rpn + x; { x la toan hang}
end; { of case }
i := i + 1;
end;
{ of while }
while (top <> 0) and (not error) do
7
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.
Tính giá trị của biểu thức hậu tố
Để minh hoạ cách tính giá trị biểu thức RPN, ta xét biểu thức sau: 1 5 + 8 4
1 , tương ứng với biểu thức infix: (1+5) (8 (4 1)).
Biểu thức này sẽ được đọc từ trái sang phải cho đến khi gặp một toán tử (ở
ví dụ này là: +). Khi đó hai toán hạng cuối cùng được đọc (1 và 5) và kết
hợp với toán tử này:
15+841
thay biểu thức con này bằng giá trị 6 cho ta biểu thức rút gọn RPN:
6841
Lại tiếp tục đọc từ trái sang phải, toán tử tiếp theo là và ta xác định được
hai toán hạng của nó:
6841
áp dụng toán tử này cho ra:
683
toán tử tiếp theo là và hai toán hạng là 8 và 3:
683
tính hiệu này ta được:
65
8
toán tử cuối cùng là
65
và nhận được giá trị 30 cho biểu thức này.
Phương pháp đánh giá các biểu thức RPN đòi hỏi phải lưu trữ các
toán hạng cho đến khi có 1 toán tử được đọc từ trái qua phải. Lúc đó 2 toán
hạng cuối cùng phải được lấy ra và được kết hợp với toán tử này. Điều này
cho ta nghĩ đến cấu trúc stack cần được sử dụng để lưu trữ các toán hạng. Cứ
mỗi lần đọc 1 toán tử, hai giá trị sẽ được lấy ra từ đỉnh ngăn xếp để áp dụng
toán tử này cho chúng và kết quả sẽ đẩy vào ngăn xếp.
Thuật toán tính giá trị biểu thức RPN
1. Khởi động ngăn xếp rỗng.
2. Lặp lại các bước sau đây cho đến khi gặp dấu kết thúc biểu thức được
đọc:
2.1. Đọc phần tử x tiếp theo trong biểu thức RPN (x có thể là hằng, biến,
toán tử số học).
2.2. Nếu x là toán hạng thì đẩy nó vào ngăn xếp, còn nếu nó là toán tử thì
thực hiện các bước sau:
- Lấy ra từ đỉnh ngăn xếp hai giá trị (nếu ngăn xếp không chứa 2
phần tử, xảy ra lỗi biểu thức không đúng dạng RPN và thuật toán
kết thúc).
- áp dụng toán tử trên vào hai giá trị vừa lấy ra.
- Đẩy giá trị kết quả vào ngăn xếp.
3. Khi gặp dấu kết thúc biểu thức, giá trị của nó là giá trị ở đỉnh của ngăn
xếp (và nó phải là giá trị duy nhất trong ngăn xếp).
Cài đặt: chương trình sau tính giá trị của biểu thức hậu tố. Giả sử biểu thức
hậu tố là hợp lệ, các toán hạng là các số nguyên chỉ gồm 1 ký tự và chỉ gồm
các toán tử +, -, *, /. Giả thiết phép chia hai số nguyên cho kết quả nguyên
giống như phép toán div.
Program Tinh_gia_tri_bieu_thuc_rpn;
Uses crt;
Const
MaxSize = 100;
Var
rpn : string;
top : integer;
stack : array[1..MaxSize] of integer;
Function Pop : integer;
9
Begin
Pop := stack[top];
top := top - 1;
End;
Procedure Push(x : integer);
Begin
top := top + 1;
stack[top] := x;
End;
Procedure Express_value;
Var i, t, a, b : integer;
Begin
top := 0;
for i := 1 to length(rpn) do
if not (rpn[i] in ['+', '-', '*', '/']) then
begin
t := ord(rpn[i]) - 48;
Push(t)
end
else
begin
b := Pop; a := Pop;
case rpn[i] of
'+' : t := a + b;
'-' : t := a - b;
'*' : t := a * b;
'/' : t := a div b;
end;
Push(t);
end;
writeln('Gia tri cua bieu thuc: ', Pop);
End;
Procedure Read_data;
Begin
write('Vao bieu thuc hau to: '); readln(rpn);
End;
Begin
clrscr;
Read_data;
Express_value;
readln;
End.
10
I. BÀI TẬP
Bài 1: Tính giá trị của biểu thức
File vào
EXPRESS.INP
File ra
EXPRESS.OUT
File chương trình EXPRESS.PAS
Giới hạn thời gian
1 giây
Cho một biểu thức số học gồm các số nguyên dương với các phép
toán cộng, trừ, nhân, chia (viết là +, -, *, /) và các dấu mở ngoặc ‘(‘,
đóng ngoặc ‘)’. Kết quả phép chia hai số nguyên cũng là nguyên (giống như
phép toán div trong Pascal). Thứ tự ưu tiên các phép toán hiểu như bình
thường, nghĩa là biểu thức trong cặp ngoặc ( ) có độ ưu tiên cao nhất, sau đó
đến phép nhân và chia, cuối cùng là phép cộng và trừ.
Hãy tính giá trị của một biểu thức cho trước.
Dữ liệu: Dòng đầu tiên trong file vào chứa số nguyên dương n là số lượng
biểu thức cần tính. Mỗi dòng trong số n dòng tiếp theo chứa một biểu thức
có độ dài không vượt quá 250 ký tự, không có dấu cách trong biểu thức.
Kết quả: Với mỗi biểu thức trong file vào, ghi ra file ra một dòng tương ứng
chứa giá trị của biểu thức.
Giả thiết tất cả các số liệu và kết quả tính toán kể cả kết quả trung gian chỉ
nằm trong giới hạn cho phép của kiểu longint.
Ví dụ:
EXPRESS.INP
3
3+4
(12+8)*2/(27-23)
6*((27-12)/(4245))+20/(4+3*2)
EXPRESS.OUT
7
10
-28
Chương trình
PROGRAM Tinh_gia_tri_bieu_thuc;
USES crt;
CONST
11
Max=250;
EndMask=';';
Dau=['(',')'];
ToanTu=['+','-','*','/'];
fi='BIEUTHUC.INP';
fo='BIEUTHUC.OUT';
TYPE
Kpt=string[10];
VAR
s:string;
i,Top,n:integer;
rpn:array[1..Max] of Kpt;
{bieu thuc dang hau
to}
stack:array[1..Max] of Kpt;
f,g:text;
(* ---------------------------------------------------*)
PROCEDURE NhapBT;
Begin
readln(f,s);
i:=1;
while i<=length(s) do { loai bo cac dau cach trong bieu
thuc }
if s[i]=' ' then delete(s,i,1)
else inc(i);
s:=s+EndMask;
End;
(* ---------------------------------------------------*)
PROCEDURE Push(pt:Kpt);
Begin
inc(Top);stack[Top]:=pt;
End;
(* ---------------------------------------------------*)
PROCEDURE Pop(var pt:Kpt);
Begin
pt:=stack[Top];dec(Top);
End;
(* ---------------------------------------------------*)
FUNCTION UuTien(tt:char):integer;
{ Ham tim do uu tien cua toan tu so hoc hay dau ( }
Begin
case tt of
'(':UuTien:=0;
'+','-':UuTien:=1;
12
'*','/':UuTien:=2;
end;
End;
(* ---------------------------------------------------*)
PROCEDURE Doc(Var i,kieu:integer;Var t:Kpt);
{ Doc tu vi tri thu i cua bieu thuc lay ra toan tu hoac
toan hang
hoac dau '(' hoac dau ')' }
Begin
if s[i] in Dau then
begin
kieu:=0;t:=s[i];inc(i);
end
else
if s[i] in ToanTu then
begin
kieu:=1;t:=s[i];inc(i);
end
else
begin
kieu:=2;
t:='';
while (s[i]<>EndMask) and not(s[i] in ToanTu) and
not(s[i] in Dau) do
begin
t:=t+s[i];inc(i);
end;
end;
End;
(* ---------------------------------------------------*)
PROCEDURE XulyDau(d:char);
Var
pt:Kpt;
Stop:boolean;
Begin
if d='(' then Push(d)
else begin
Stop:=false;
repeat
Pop(pt);
if pt<>'(' then
begin
inc(n);rpn[n]:=pt
end
else Stop:=true;
13
until Stop;
end
End;
(* ---------------------------------------------------*)
PROCEDURE XulyToanTu(tt:char);
Var
pt:Kpt;
Stop:boolean;
Begin
Stop:=false;
while (Top<>0) and not Stop do
begin
Pop(pt);
if UuTien(tt)<=UuTien(pt[1]) then
begin
inc(n);rpn[n]:=pt
end
else
begin
Push(pt);Stop:=true;
end;
end;
Push(tt);
End;
(* ---------------------------------------------------*)
PROCEDURE XulyToanHang(th:string);
Begin
inc(n);rpn[n]:=th;
End;
(* ---------------------------------------------------*)
PROCEDURE ConvertToRPN;
Var
kieu:integer;
t,pt:Kpt;
Stop:boolean;
Begin
Top:=0;i:=1;n:=0;
while s[i]<>EndMask do
begin
Doc(i,kieu,t);
case kieu of
0:XulyDau(t[1]);
1:XulyToanTu(t[1]);
2:XulyToanHang(t);
14
end;
end;
while Top<>0 do
begin
Pop(pt);
inc(n);rpn[n]:=pt;
end;
End;
(* ---------------------------------------------------*)
PROCEDURE TinhGT;
Var
pt,pt1,pt2:Kpt;
t,t1,t2:longint;
code:integer;
Begin
Top:=0;
for i:=1 to n do
begin
if rpn[i][1] in ToanTu then
begin
Pop(pt2);Pop(pt1);
Val(pt2,t2,code);Val(pt1,t1,code);
case rpn[i][1] of
'-':t:=t1-t2;
'+':t:=t1+t2;
'*':t:=t1*t2;
'/':t:=t1 div t2;
end;
Str(t,pt);
Push(pt);
end
else Push(rpn[i]);
end;
Pop(pt); { Gia tri cua bieu thuc chinh la phan tu duy
nhat con lai trong stack}
writeln(g,pt);
End;
(* ---------------------------------------------------*)
BEGIN
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
while not EOF(f) do
begin
NhapBT;
ConverttoRPN;
15
TinhGT;
end;
close(f);close(g);
END.
Bài 2: Optimal Programs
File vào
OPTIMAL.INP
File ra
OPTIMAL.OUT
File chương trình OPTIMAL.PAS
Giới hạn thời gian
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
...
...
ADD
a+b
c
...
...
SUB
b-a
c
...
...
MUL
a*b
c
...
...
16
DIV
DUP
b div a
c
...
...
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.
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
1 2 3 4
0 -2 -6 -12
3
1 2 3
1 11 2003
1
2003
Program 1
DUP DUP MUL
SUB
Program 2
Impossible
Program 3
17
2003
0
Empty sequence
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;
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
18
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 }
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;
19
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;
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;
20
- Xem thêm -