Mapcon
15-09-2002, 11:36 PM
* Để tôi bắt đâu chủ đề thuật toán trước nhé ! Mong là mọi người ủng hộ ! (mapcon)
[hr]
Ta biết rằng ngoài những kiểu dữ liệu cụ thể như Mảng, bản ghi... còn có hai kiểu dữ liệu trừu tượng mà ứng dụng của chúng cũng rất rộng rãi, đó là Stack (Ngăn xếp) và Queue (Hàng đợi),
Sau đây là một số giới thiệu về hai kiểu dữ liệu này :
+ Stack (Ngăn xếp).
Đây là kiểu dữ liệu mà việc cập nhật và truy nhập nó đều theo nguyên tắc "Vào sau ra trước"( Last . In, Firt . Out). Ta có thể hình dung Stack là một mảng, một chiều mà việc truy nhập và cập nhật nó đều diễn ra ở một đầu của mảng. Sau đây là mô tả quy tắc hoạt động của 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:
(Đưa số N vào Stack)
Procedure Push (N: Integer);
Begin
Inc (P):{tăng vị trí con trỏ}
Stack[P]:=N;
End;
{Lấy ra khỏi Stack}
Function Pop: Integer;
Begin
Pop:=Stack[P];
Dec(P); {Giảm vị trí con trỏ}
End;
{Kiểm tra xem Stack đã rỗng chưa}
Function StackEmpty:Boolean;
Begin
StackEmpty:=P=0;
End;
Ví dụ sẽ sử dụng Stack;
Bài 1:
Một biểu thức toán học Ba Lan hay còn gọi là biểu thức hậu tố(Posfix) là một biểu thức mà toán tử được viết sau toán hạng.
Ví dụ: 523461+*7++*+ {= 5+2*(3+4*(6+1)+7)}
Yêu cầu nhập vào một biểu thức dưới dạng1 xâu kí tự, hãy tính giá trị biểu thức đó. Nhận xét: Gọi S là xâu kí tự của biểu thức. Ta biết rằng toán tử gồm+,*, toán hạng là số nguyên không âm, thủ tục tính toán có thể viết như sau:
{=========}
Procedure Tinh_Gtri;
Var i: Byte;
Tg:Integer;
Begin
Tg:=0; i:=1;
S:=S+Chr(0);
Repeat
While S [i]=' ' do Inc (i);
Case S(i) of
'+' :Begin Tg:=pop+pop;Inc(i) End;
'*' : Begin Tg : =pop*pop; Inc(i) End;
Else
Begin
Tg : =0;
While (S[i]< >' ' )and(S[i]<='9') do
Begin
Tg : = Tg* 10+ord (s[i])-48;
Inc (i);
End;
End;
End;
Push (tg);
Until (P =1) and (i > = Length (s) );
End;
{===============}
[b][/u]Bài 2 :[/u]
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 1 , r : Integer; End;
Procedure Sort;
Begin
S:=1; Stack [s]. 1:=1; Stack [s] . r :=n ;
Repeat
1:=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] . 1 : = 1;
Stack [s] . r : + r ;
End;
r : = j;
Until 1> r ;
Until S= 0;
End;
{===========}
[b]Bài 3:
Khử đệ quy tìm hoán vị của N số.
+ Queue ( Hàng đợi)
Khác với Stack, Queue là một kiểu dữ liệu trừu tượng mà cơ chế cập nhật và truy xuất xảy ra ở hai đầu khác nhau và theo quy tắc vào trước ra trước ( First In - First Out). Nếu có thể xác định được kích cỡ cần đến của Queue ta có thể dùng một mảng tĩnh ( thay cho một xâu liên kết động) để mô phỏng Queue theo đó, đầu trái của mảng là đầu ra ( dùng con trỏ l) và đầu phải của mảng là đầu vào (dùng con trỏ r ) tương ứng với thủ tục Put, hàm Get và một hàm Qfull kiểu Boolean để thông báo Queue đầy hay chưa.
Giả sử mảng mô phỏng Queue là Qu:
Const SizeQu = 5000;
Type
Td = Record d,c : Integer; End;
Var
Qu: Array [ 1 .. Size Qu ]of Td;
L,R: Integer;
F: Text;
{Đưa vào hàng đợi}
Procedure Put (NewOb : Td);
Begin
Inc ®;
Qu [ r-1)div Sizequ +1] : = NewOb;
End;
{Lấy ra khỏi hàng đợi}
Procedure Get(Var FistOb :Td);
Begin
Inc(L) ; FistOb: = Qu [L Mod SizeQu+1];
End;
{Kiểm tra hàng đợi có rỗng hay không}
Function Qfull : Boolean;
Begin
Qempty : =L - R >0;
End;
{Kiếm tra xem hàng đợi đầy chưa}
Function Qfull : Boolean;
Begin
QFull : = r - 1 > SizeQu;
End;
Ứng dụng quan trọng của Queue là giúp giải pháp "Loang" hay tìm kiếm theo chiều rộng.
Ví dụ về ứng dụng của Queue:
Bài Toán : 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ư 1 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.
[b]Nhận xét :[b]
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ìn> then
if < ô kể chưa đến> then
Begin
Nhan [ôkề] : = Nhan [ô] +1;
Put (ô kề)
End;
Until QuEmpty;
If Nhan [ô đích] = vô cùng Then < thông báo không đến được>
Else
Repeat
Tìm lật ngược kể từ ô đích;
Until Nhan [ô i] = 0;
Các bạn tự cài đặt cho bài này nhé !!!
[hr]
Ta biết rằng ngoài những kiểu dữ liệu cụ thể như Mảng, bản ghi... còn có hai kiểu dữ liệu trừu tượng mà ứng dụng của chúng cũng rất rộng rãi, đó là Stack (Ngăn xếp) và Queue (Hàng đợi),
Sau đây là một số giới thiệu về hai kiểu dữ liệu này :
+ Stack (Ngăn xếp).
Đây là kiểu dữ liệu mà việc cập nhật và truy nhập nó đều theo nguyên tắc "Vào sau ra trước"( Last . In, Firt . Out). Ta có thể hình dung Stack là một mảng, một chiều mà việc truy nhập và cập nhật nó đều diễn ra ở một đầu của mảng. Sau đây là mô tả quy tắc hoạt động của 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:
(Đưa số N vào Stack)
Procedure Push (N: Integer);
Begin
Inc (P):{tăng vị trí con trỏ}
Stack[P]:=N;
End;
{Lấy ra khỏi Stack}
Function Pop: Integer;
Begin
Pop:=Stack[P];
Dec(P); {Giảm vị trí con trỏ}
End;
{Kiểm tra xem Stack đã rỗng chưa}
Function StackEmpty:Boolean;
Begin
StackEmpty:=P=0;
End;
Ví dụ sẽ sử dụng Stack;
Bài 1:
Một biểu thức toán học Ba Lan hay còn gọi là biểu thức hậu tố(Posfix) là một biểu thức mà toán tử được viết sau toán hạng.
Ví dụ: 523461+*7++*+ {= 5+2*(3+4*(6+1)+7)}
Yêu cầu nhập vào một biểu thức dưới dạng1 xâu kí tự, hãy tính giá trị biểu thức đó. Nhận xét: Gọi S là xâu kí tự của biểu thức. Ta biết rằng toán tử gồm+,*, toán hạng là số nguyên không âm, thủ tục tính toán có thể viết như sau:
{=========}
Procedure Tinh_Gtri;
Var i: Byte;
Tg:Integer;
Begin
Tg:=0; i:=1;
S:=S+Chr(0);
Repeat
While S [i]=' ' do Inc (i);
Case S(i) of
'+' :Begin Tg:=pop+pop;Inc(i) End;
'*' : Begin Tg : =pop*pop; Inc(i) End;
Else
Begin
Tg : =0;
While (S[i]< >' ' )and(S[i]<='9') do
Begin
Tg : = Tg* 10+ord (s[i])-48;
Inc (i);
End;
End;
End;
Push (tg);
Until (P =1) and (i > = Length (s) );
End;
{===============}
[b][/u]Bài 2 :[/u]
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 1 , r : Integer; End;
Procedure Sort;
Begin
S:=1; Stack [s]. 1:=1; Stack [s] . r :=n ;
Repeat
1:=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] . 1 : = 1;
Stack [s] . r : + r ;
End;
r : = j;
Until 1> r ;
Until S= 0;
End;
{===========}
[b]Bài 3:
Khử đệ quy tìm hoán vị của N số.
+ Queue ( Hàng đợi)
Khác với Stack, Queue là một kiểu dữ liệu trừu tượng mà cơ chế cập nhật và truy xuất xảy ra ở hai đầu khác nhau và theo quy tắc vào trước ra trước ( First In - First Out). Nếu có thể xác định được kích cỡ cần đến của Queue ta có thể dùng một mảng tĩnh ( thay cho một xâu liên kết động) để mô phỏng Queue theo đó, đầu trái của mảng là đầu ra ( dùng con trỏ l) và đầu phải của mảng là đầu vào (dùng con trỏ r ) tương ứng với thủ tục Put, hàm Get và một hàm Qfull kiểu Boolean để thông báo Queue đầy hay chưa.
Giả sử mảng mô phỏng Queue là Qu:
Const SizeQu = 5000;
Type
Td = Record d,c : Integer; End;
Var
Qu: Array [ 1 .. Size Qu ]of Td;
L,R: Integer;
F: Text;
{Đưa vào hàng đợi}
Procedure Put (NewOb : Td);
Begin
Inc ®;
Qu [ r-1)div Sizequ +1] : = NewOb;
End;
{Lấy ra khỏi hàng đợi}
Procedure Get(Var FistOb :Td);
Begin
Inc(L) ; FistOb: = Qu [L Mod SizeQu+1];
End;
{Kiểm tra hàng đợi có rỗng hay không}
Function Qfull : Boolean;
Begin
Qempty : =L - R >0;
End;
{Kiếm tra xem hàng đợi đầy chưa}
Function Qfull : Boolean;
Begin
QFull : = r - 1 > SizeQu;
End;
Ứng dụng quan trọng của Queue là giúp giải pháp "Loang" hay tìm kiếm theo chiều rộng.
Ví dụ về ứng dụng của Queue:
Bài Toán : 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ư 1 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.
[b]Nhận xét :[b]
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ìn> then
if < ô kể chưa đến> then
Begin
Nhan [ôkề] : = Nhan [ô] +1;
Put (ô kề)
End;
Until QuEmpty;
If Nhan [ô đích] = vô cùng Then < thông báo không đến được>
Else
Repeat
Tìm lật ngược kể từ ô đích;
Until Nhan [ô i] = 0;
Các bạn tự cài đặt cho bài này nhé !!!