Luyện thi HSG pascal

                                        PHẦN III, LẬP TRÌNH NÂNG CAO

                                                    CHƯƠNG I. ĐỆ QUY

1, Khái niệm

   Chương trình con đệ quy là chương trình con mà trong thân chương trình con có lời gọi chinh chương trình con đó.

2, Hiêu đệ quy thông qua một số ví dụ.

2.1, Tính N!

Function    gt(n:byte) :  qword ;

Begin

           If n=0 then gt:= 1

           Else gt:= n*gt(n-1);

End;

Nếu khi gọi chương trình con giai thừa 4 thì nó sẽ thực hiện như  thế nào?

+ Đầu tiên chương trình con sẽ truyền giá trị cho n=4

+ Vì 4 ≠ 0 nên gt:= 4*gt(4-1); ở đây có lời gọi hàm gt(3) lúc này nó lại truyền giá trị lên n=3.

+ Vì 3 ≠ 0 nên gt:= 3*gt(3-1); ở đây có lời gọi hàm gt(2) lúc này nó lại truyền giá trị lên n=2.

+ Vì 2 ≠ 0 nên gt:= 2*gt(2-1); ở đây có lời gọi hàm gt(1) lúc này nó lại truyền giá trị lên n=1.

+ Vì 1 ≠ 0 nên g:= 1*gt(1-1); ở đây có lời gọi hàm gt(0) lúc này nó lại truyền lên giá trị n=0.

+ Vì n = 0 nên gt:= 1; Hay nói cách khác là nó trả giá trị 1 lại cho hàm. Lúc này có bao nhiêu lần gọi hàm trong chương trình con thì sẽ nhớ và thực hiện từ dưới lên ( hay nói cách khác là nó quay lui lên).

2.2 Chương trình sau in ra file giaithua.out có nội dung gì? Vì sao?

Const        fo=’giaithua.out’;

Var    n:   byte;

Function    gt(n:byte) :  qword ;

Begin

           If n=0 then gt:= 1

           Else gt:= n*gt(n-1);

           Writeln(n);

End;

BEGIN

    Assign(output,fo); rewrite(output);

    Writeln(gt(5));

   Close(input);   close(output);

END.

2.3 Biểu thức Zero( nguồn bài 4 đề thi hsg Tỉnh Thanh Hóa năm 2009).

Program Zero_sum;
Type MangStr = array[1..15] of string;
Const Fi =’ZERO.INP’;
Fo =’ZERO.OUT’;
Dau : array[1..3] of string[1] = (’-’,’+’,’’);
S : array[1..9] of char =(’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’);
ChuSo = [’1’..’9’];

Var N,k,dem: byte;
D : array[2..9] of string[1];
F : Text;
St : String;
M : MangStr;

Procedure Write_out;
Var i : byte;
Begin
Assign(F,Fo); Rewrite(F);
Writeln(F,dem);
For i:= 1 to dem do writeln(F,M[i],’ = 0’);
Close(F); Halt;
End;

Procedure Read_inp;
Begin
Assign(F,Fi); Reset(F);
Read(F,N); Close(F);
If N < 3 then write_out;
End;

Function DocSo(S : String): longint;
Var M : longint;
t : byte;
Begin
M:= 0; t:= 0;
If S[k] in [’+’,’-’] then
begin
t:= k; Inc(k);
end;
While (k<= length(S)) and (s[k] in ChuSo) do
begin
m:= m*10 + ord(s[k]) - ord(’0’);
Inc(k);
end;
If (t <> 0) and (S[t] = ’-’) then DocSo:= -M
else DocSo:= M;
End;

Procedure Test;
Var St : string;
i : byte;
T : longint;
Begin
St:= ’1’; k:= 1; T:= 0;
For i:= 2 to N do St:= St + D[i] + S[i];
While k < length(St) + 1 do T:= T + DocSo(St);
If T = 0 then
begin
Inc(dem); M[dem]:= St;
end;
End;

Procedure Try(i: byte);
Var j : byte;
Begin
For j:= 1 to 3 do
begin
D[i]:= Dau[j];
If i = N then Test else try(i+1);
end;
End;

BEGIN
Read_inp;
Try(2);
Write_out;
END.
.