8.4.2. Truyền theo tham trị
Các tham trị hay các tham số thực sự truyền cho các tham số hình thức theo phương hướng truyền tham trị được khai báo:
:
Đối với các tham trị khi có lời gọi chương trình con, hệ thống sẽ cấp phát một vùng nhớ khác và sao giá trị của tham số thực sự vào đó. Chương trình con thao tác với tham số hình thức tương ứng sẽ thực hiện với dữ liệu trên bản sao này và không ảnh hưởng đến tham số thực sự.
Như vậy khi kết thúc chương trình con các bản sao bị xóa đi và giá trị của tham thực sự là giữ nguyên như trước khi truyền vào chương trình.
Việc truyền theo tham trị có những đăc điểm sau:
- Giá trị của biến được truyền theo tham trị ở đầu vào sẽ không bị thay đổi sau lời gọi chương trình con.
- Tốn thêm bộ nhớ khi thực hiện chương trình con do tạo bản sao.
- Khi gọi chương trình con cho phép giá trị ở đầu vào có thể là những giá trị của hằng, biến, hàm hoặc biểu thức.
Ví dụ 8.6:
Program vidu_8_6;
Var t,k: integer;
Procedure test(t,k: integer);
Begin
k:=k+5;
t:=t+5;
End;
Begin
k:=5; t:=5;
writeln(‘k=‘,k,’ va t=‘,t);
test(i,k);
writeln(‘k=‘,k,’ va t=‘,t);
readln;
End.
|
{Khai báo 2 biến t, k là hai biến toàn chương trình chính.}
{Khai báo tham số hình thức của chương trình con: t, k đều là tham trị.}
{In ra giá trị k = 5 và t = 5}
{Lời gọi thủ tục test}
{In ra màn hình k = 5 và t = 5}
| 8.4.3. Truyền theo tham biến
Các tham biến được khai báo trong tiêu đề của chương trình con.
Var :;
Đối với các tham biến, chương trình con thao tác với các tham số thực sự sẽ được thực hiện trực tiếp với dữ liệu trên chính bộ nhớ của tham số thực sự nên khi kết thúc chương trình con thì giá trị của tham số thực sự chính là giá trị đã được chương trình con thay đổi.
Truyền theo tham biến có những đặc điểm sau:
- Giá trị của biến được truyền theo tham biến ở đầu vào sẽ bị thay đổi sau lời gọi chương trình con.
- Không tốn thêm bộ nhớ khi thực hiện chương trình con do không tạo bản sao.
- Khi gọi chương trình con giá trị ở đầu vào chỉ có thể là biến.
Ví dụ 8.7:
Program vidu_8_7;
Var t,k: integer;
{Khai báo biến của chương trình chính: 2 biến t, k là hai biến toàn chương trình chính.}
Procedure test(k:integer; var t: integer);
{Khai báo biến hình thức của chương trình con:
k là tham trị, t là tham biến.}
Begin
k:=k+5;
t:=t+5;
End;
Begin
k:=5; t:=5;
writeln(‘k = ‘,k,’ va t = ‘,t);{In ra giá trị k=5 và t=5}
test(i,k); {Lời gọi thủ tục test}
writeln(‘k = ‘,k,’ va t = ‘,t);{In ra màn hình k=5 và t=10}
readln;
End.
Khi nào thì nên dùng tham biến?
- Nếu cần thay đổi giá trị thực sự theo quản lý của chương trình con
- Tránh sao lưu dữ liệu lớn.
Ví dụ 8.8: Viết chương trình hoán vị giá trị của hai biến a, b.
Program vidu_8_8;
Var a,b: real;
Procedure hoanvi(var a,b: real); {a, b là tham biến}
Var tg: real;
Begin
tg:=a;
a:=b;
b:=tg;
End;
Begin
Write(‘ nhap hai so a, b: ’);readln(a,b);
Writeln(‘Hai so truoc hoan vi la: ’, a:8:2, b:8:2);
Hoanvi(a,b);
Writeln(‘Hai so sau hoan vi la: ’, a:8:2, b:8:2);
Readln;
End.
Trong ví dụ trên nếu khai báo tham số hình thức a, b ở đầu chương trình con là tham trị thì sẽ không thể hoán đổi giá trị của hai biến đó cho nhau.
8.5. Tính đệ qui của chương trình con 8.5.1. Khái niệm về đệ qui
Các chương trình mà chúng ta đã xem xét đều có chung cấu trúc dạng chương trình gọi các chương trình con khác dưới dạng mô hình phân cấp. Tuy nhiên đối với một số bài toán, việc dùng chương trình con gọi ngay chính nó rất hữu dụng. Có thể định nghĩa chương trình con đệ qui là chương trình con sẽ gọi đến chính nó trực tiếp hay gián tiếp thông qua các chương trình con khác.
Cách tiến hành giải một bài toán đệ qui nhìn chung có những điểm chung sau: Trước tiên gọi chương trình con đệ qui để giải bài toán, chương trình con đệ qui thực ra chỉ biết cách giải bài toán trong trường hợp đơn giản nhất (hay còn gọi là trường hợp cơ sở). Nếu chương trình con đệ qui được gọi trong trường hợp cơ sở, chương trình con chỉ cần đơn giản trả lại kết quả. Nếu chương trình con được gọi trong các trường hợp phức tạp hơn, chương trình con đệ qui sẽ chia công việc cần giải quyết thành hai phần. Một phần hàm biết cách giải quyết như thế nào, còn phần kia vẫn không biết cách giải quyết như thế nào tuy nhiên để được gọi là có khả năng đệ qui, phần sau phải giống với bài toán ban đầu nhưng đơn giản hơn hay nhỏ hơn bài toán ban đầu. Bởi vì bài toán mới giống với bài toán ban đầu nên chương trình con sẽ thực hiện gọi chính nó để giải quyết công việc đơn giản hơn này - đây chính là lời gọi đệ qui hay còn gọi là một bước đệ qui. Để đảm bảo việc đệ qui có kết thúc, mỗi một lần gọi đệ qui thì bài toán phải đảm bảo đơn giản hơn và các bước đệ qui này còn thực hiện tiếp cho đến khi nào bài toán đơn giản dần, đơn giản tới mức trở thành trường hợp cơ sở. Có thể nhận thấy hàm đệ qui xử lý trường hợp cơ sở để trả lại kết quả tính được cho các chương trình con mức phức tạp hơn, rồi đến lượt các chương trình con này lại tính trả lại kết quả cho các chương trình con phức tạp hơn nữa ... cứ như vậy cho đến lời gọi chương trình con ban đầu.
8.5.2. Cách dùng đệ qui
8.5.2.1. Các bài toán có thể dùng Đệ Qui
Thường áp dụng cho các bài toán phụ thuộc tham số có hai đặc điểm sau:
Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Ta gọi đây là trường hợp suy biến.
Trong trường hợp tổng quát, bài toán có thể qui về một bài toán cùng dạng nhưng giá trị tham số thì bị thay đổi. Và sau một số hữu hạn bước biến đổi Đệ Qui sẽ dẫn đến trường hợp suy biến.
8.5.2.2. Cách xây dựng hàm Đệ Qui
Hàm Đệ Qui thường được viết theo thuật toán sau:
if ( trường hợp suy biến) then
begin
trình bầy cách giải bài toán
(giả định đã có cách giải)
end
else { trường hợp tổng quát }
begin
gọi đệ qui tới hàm (đang lập) với
giá trị khác của tham số
end;
8.5.2.3. Một số ví dụ
V í dụ 8.9: 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 đệ qui tính k! :
PROGRAM VIDU_8_9;
{ 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):8:2 );
Readln;
END.
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ụ 8.10: 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 hoặc k=1
= U(k-1) + U(k-2) nếu k>1.
Công thức truy hồi 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 VIDU_8_10; { 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.
Ghi chú: Việc sử dụng đệ qui đòi hỏi nhiều về bộ nhớ. Do đó tránh dùng đệ qui nếu có thể được.
Ví dụ 8.11:
Tam giác Pascal là một bảng các số có n+1 hàng (từ hàng 0 đến hàng n), mỗi một số hạng trong hàng i là tổ hợp chập k của i (với định nghĩa tổ hợp chập k của n là
= n!/(k!*(n-k)!). Bằng cách tạo tính tổ hợp (trong đó có sử dụng hàm tính giai thừa). Hãy in ra màn hình tam giác Pascal theo dạng:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
..................................
Program Tam_giac_Pascal;
VAR n, i, k: Integer;
Function Giai_thua(n: integer): longint;
VAR gt : LongInt;
BEGIN
gt := 1;
FOR i :=1 TO n DO
gt := gt*i;
Giai_thua := gt;
END;
Function To_hop(n,k: integer):LongInt;
BEGIN { Than chuong trinh con To_hop }
To_hop := Giai_thua(n) div ( Giai_thua(k)*Giai_thua(n-k) );
END;
BEGIN { Chuong trinh chinh }
WRITE('Nhap n: '); READLN(n);
FOR i:=0 TO n DO
BEGIN
FOR k:= 0 TO i DO
WRITE(To_hop(i,k):5);{In 1 hang cua tam giac Pascal}
WRITELN; { xuong dong }
END;
READLN;
END.
Ví dụ 8.12: Bài toán Tháp Hà Nội: Có một cái tháp bao gồm n tầng, tầng trên nhỏ hơn tầng dưới. Hãy tìm cách chuyển cái tháp này từ vị trí A sang vị trí B nhờ vị trí trung gian C. Yêu cầu mỗi lần chỉ được chuyển một tầng và không được để tầng lớn trên tầng nhỏ.
Program Thap_Ha_Noi;
USES Crt;
VAR n : Integer;
Procedure Chuyen(n:Integer; VT1, VT2, VT3:Char);
BEGIN
IF n = 1 THEN WRITELN('Chuyen tu ', VT1, ' sang ', VT2)
ELSE
BEGIN
Chuyen(n-1, VT1, VT3, VT2);
Chuyen(1, VT1, VT2, VT3);
Chuyen(n-1, VT3, VT2, VT1);
END;
END;
BEGIN
ClrScr;
WRITE('Thap co bao nhieu tang? '); READLN(n);
WRITELN('Qua trinh dich chuyen nhu sau: ');
Chuyen(n, 'A', 'B', 'C');
READLN;
END.
Chia sẻ với bạn bè của bạn: |