Tài liệu HSG Pascal Phần 1

Chương I : Duyệt không đệ qui

I / Nhận xét :

Các chương trình có thể viết dưới dạng “ Duyệt bằng đệ quy “ khi nó phải thực hiện nhiệm vụ P có hình thức đệ quy sau đây :

P = ( Nếu B 0 thì S ; Nếu Bk thì P )



trong đó S là một số công việc phải thực hiện khi có điều kiện kết thúc B0 của đệ quy , còn Bk là điều kiện cần để thực hiện nhiệm vụ P ở bước thứ k . Trong mỗi bước gọi thực hiện P thì điều kiện Bk được thu hẹp dần để dẫn tới tình trạng kết thúc B0 của quá trình duyệt .
Song do chương trình đệ quy được tổ chức bằng Stack (ngăn xếp) trong bộ nhớ có kích thước tối đa là 16kb nên khi gặp những chương trình đệ quy quá sâu thường bị tràn Stack của bộ nhớ ( ngăn xếp của chương trình đệ quy không đủ chứa các hàm và thủ tục đệ quy của nó ) . Trong những trường hợp như thế , người ta thường chuyển sang chương trình viết dưới dạng “Duyệt không đệ qui “ thay đệ quy bằng vòng lặp , dựa vào công thức sau :
P = ( G 0 ; Trong khi Bk thì Pk )



G 0 : một số lệnh gán trị ban đầu
Bk : điều kiện cần để thực hiện công việc Pk

II / Một số thí dụ :

Thí dụ 1 : Xây dựng hàm Fibonaci bằng đệ quy và không đệ quy

Function Fibonaci(N : Integer) : Integer;
Begin
If N=0 then Fibonaci =1 {N=0 hoặc N=1 là điều kiện B0 }
Else
If N=1 then Fibonaci =1
Else {N>=2 là điều kiện Bk}
Fibonaci := Fibonaci(N-1)+ Fibonaci(N-2)
End;

Function Fibonaci(N : Integer) : Integer;
Var i,p,U0,U1 : Integer;
Begin
i := 0;
U0 := 0;
U1 := 1;
While i< N do
Begin
Inc(i);
p := U1;
U1 := U0+U1;
U0 := p;
End;
Fibonaci := p;
End;

Thí dụ 2 : Sắp xếp mảng bằng thuật toán QuickSort :

Kiểu đệ quy

Program QSort;
{$R-,S-}
Uses Crt;
Const Max = 30000;
Type List = Array[1..Max] of Integer;
Var Data : List;
I : Integer;

Procedure QuickSort(Var A: List; Lo, Hi: Integer);
Procedure Sort(L, r: Integer);
Var i, j, x, y: integer;
Begin
i := L;
j := r;
x := a[(L+r) DIV 2];
Repeat
While a[i] < x do i := i + 1;
While x < a[j] do j := j - 1;
If i <= j then
Begin
y := a[i];
a[i] := a[j];
a[j] := y;
i := i + 1;
j := j - 1;
End;
until i > j;
If L < j then Sort(L, j);
If i < r then Sort(i, r);
End;
Begin
Sort(Lo,Hi);
End;

BEGIN {QSort}
Write(`Hiện đang