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

  • Số trang: 26 |
  • Loại file: PDF |
  • Lượt xem: 1639 |
  • Lượt tải: 0

Mô tả:

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 -