Tài liệu Bồi dưỡng học sinh giỏi môn tin học chuyên đề ngăn xếp (stack)

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