Pascal - Sự tham khảo trước và sự ðệ qui - pdf 17

Download miễn phí Pascal - Sự tham khảo trước và sự ðệ qui



Muốn tính k! ta phải tính được (k-1)!, muốn tính (k-1)! lại phải tính (k-2)!, ., suy ra cuối cùng phải tính được 0!, nhưng vì 0!=1 nên qúa trình kết thúc.
Chương trình sau nhập N, tính và in gía trị N!. Trong chương trình có xây
dựng và sử dụng một hàm đệ quy tính k! :



Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

SỰ THAM KHẢO TRƯỚC VÀ SỰ ÐỆ QUI
13.3.1. Tham khảo trước (Forward reference):
Bình thường khi trong chương trình chính có hai chương trình con A, B
được khai báo kế tiếp nhau A trước, B sau, thì B gọi được A nhưng A không
gọi được B. Khi đó để A gọi được B ta phải tiến hành khai báo phần đầu của
B với từ khóa Forward trước khi khai báo B đầy đủ.
Ví dụ 13.6:
PROGRAM VIDU13_6;
Procedure B; Forward ; { khai báo tham khảo B trước}
Procedure A;
Begin
Writeln(‘ Chào chị ‘);
B;
End;
Procedure B;
Begin
Writeln(‘ Chào anh ‘);
End;
BEGIN
A;
Readln;
END.
Chạy
Chép tập tin nguồn
Khi chương trình chạy sẽ in lên màn hình:
Chào chị
Chào anh
Tất nhiên, nếu ta đưa khai báo đầy đủ B lên trước A thì không cần
tham khảo trước. Song đặt giả thiết A gọi B rồi B lại gọi A thì nhất định phải
tham khảo trước thôi.
13.3.2. Sự đệ qui (Recursion):
Một thủ tục hay hàm có thể gọi chính nó, khi đó ta nói có sự đệ qui.
Ví dụ 13.7: Tính S= k! bằng đệ qui. Ta viết :
Muốn tính k! ta phải tính được (k-1)!, muốn tính (k-1)! lại phải tính (k-
2)!, ..., suy ra cuối cùng phải tính được 0!, nhưng vì 0!=1 nên qúa trình kết
thúc.
Chương trình sau nhập N, tính và in gía trị N!. Trong chương trình có xây
dựng và sử dụng một hàm đệ quy tính k! :
PROGRAM VIDU13_7;
{ Tính N! bằng đệ qui}
Var
N : Byte;
Function Gt( k : Byte) : Real;
{ Hàm tính k! bằng đệ qui}
Begin
If k=0 then Gt:= 1
else
Gt:= k* Gt(k-1);
End;
BEGIN
Repeat
Write(‘ Nhập N: ‘);
Readln(N);
Until N>0;
Writeln( N, ‘ != ‘, Gt(N):0:0 );
Readln;
END.
Chạy
Chép tập tin nguồn
Khi nhập N=4, qúa trình gọi các hàm được diễn giải như sau:
Gt(4) =4*Gt(3)
=4*3*Gt(2)
=4*3*2*Gt(1)
=4*3*2*1*Gt(0) { vì k=0 nên Gt=1}
=4*3*2*1* 1
=24.
Ví dụ 13.8:
Tính số hạng U(k) của dãy Fibonaci bằng đệ qui:
U(0)=1, U(1)=1, U(k)=U(k-1) + U(k-2) với k>1.
Ta viết:
U(k) = 1 nếu k=0 hay k=1
= U(k-1) + U(k-2) nếu k>1.
Công thức truy chứng trên là cơ sở để xây dựng hàm đệ qui tính U(k): để
tính được một số hạng ta phải tính được hai số hạng đứng trước nó.
Chương trình sau in ra số Fibonaci thứ N bằng cách gọi hàm đệ qui Fibo.
PROGRAM VIDU13_8;
{ Tính số Fibonaci thứ N }
Var
N : Integer;
Function Fibo( k : Integer) : Integer;
{ Hàm tính số Fibonaci thứ k bằng đệ qui}
Begin
If k=0 then Fibo:= 1
else
if k=1 then Fibo:=1
else
Fibo:=Fibo(k-1) + Fibo( k-2);
End;
BEGIN
Write(‘ Nhập N: ‘);
Readln(N);
Writeln( ‘ Số Fibo thứ ‘, N, ‘ = ‘, Fibo(N) );
Readln;
END.
Chạy
Chép tập tin nguồn
Ghi chú: Việc sử dụng đệ qui đòi hỏi nhiều về bộ nhớ. Lời khuyên là nên
tránh dùng đệ qui nếu có thể được.
...
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status