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.
BÀI TẬP CHƯƠNG 8
Bài 8.1: Phân biệt biến địa phương và biến toàn cục? Có thể đặt tên biến địa phương và biến toàn cục cùng tên không? Điều gì sẽ xảy ra? Giải thích?
Bài 8.2: Tên các tham số hình thức có thể trùng tên với biến toàn cục hay biến địa phương của chường trình con đó hay không? Điều gì sẽ xảy ra? Giải thích vì sao?
Bài 8.3: Có bao nhiêu phương thức truyền tham số cho chương trình con? Hãy phân biệt chúng? Lấy một ví dụ ?
Bào 8.4: Cho các khai báo sau:
Const max = 1000;
Var x,y,z: real;
m,n: integer;
Procedure CTC_1(var x, y: real; z: integer);
Function CTC_2(i,n: integer):real;
Trong các lời gọi sau, lời gọi nào sai? Vì sao? Nếu có thể hãy sửa lại cho đúng.
CTC_1(x,y,m);
CTC_1(x,y,z);
CTC_1(x-y,x+y,5);
CTC_1(x,y,max);
CTC_1(2.5,y,3);
CTC_1(x,y,5,10);
CTC_1(x,y,m+2)
|
Writeln(CTC_1(x,y,m));
m = CTC_1(x,y,5);
m = CTC_2(m,n);
x = CTC_2(m,5);
CTC_2(m,3);
x = y + CTC_2(x,m);
writeln(CTC_2(m,n));
|
Bài 8.5: Viết chương trình tạo một bảng chọn đơn giản gồm các mục sau:
1. Giải phương trình bậc nhất
2. Giải phương trình bậc hai
3. Giải hệ phương trình bậc nhất
0. Kết thúc chương trình.
Gõ các sô 0, 1, 2, 3 để lựa chọn công việc tương ứng. Mỗi công việc sẽ được xây dựng bằng chương trình con và chỉ cần gọi ra trong chương trình chính.
Bài 8.6: Viết chương trình nhập vào một số n. In lên màn hình các số nguyên tố nhỏ hơn n.
Bài 8.7: Viết thủ tục nhập vào và in ra màn hình theo hàng dãy số thực có n phần tử. In lên màn hình các số chính phương có mặt trong dãy số.
Bài 8.8:Viết một thủ tục nhập hai ma trận vuông A, B cấp N có các phần tử là các số nguyên.
Viết một thủ tục tính ma trận C= A+2B
Viết một thủ tục in các ma trận A, B và C lên màn hình
Viết một hàm kiểm tra A, B, C có phải là ma trận đối xứng khôngBài 8.9: Viết một hàm kiểm tra hàng thứ k của một ma trận A cấp MxN có lập thành một dãy tăng không?.
Nhập ma trận A và cho biết những hàng nào của A lập thành một dãy tăng ?
Bài 8.10: Viết chương trình giải phương trình bậc hai ax2 + bx + c = 0 yêu cầu tạo hai chương trình con một chương trình con giải phương trình bậc nhất trong trường hợp hệ số a = 0 và một chương trình con giải phương trình bậc hai thực sự trong trường hợp hệ số a khác 0.
Bài 8.11: Viết một hàm để chuẩn hóa một chuỗi: xóa bỏ mọi ký tự trắng thừa ở đầu và cuối chuỗi, và giữa hai từ chỉ giữ lại đúng một ký tự trắng.
Bài 8.12: Viết một hàm để đổi một ký tự từ chữ hoa ra chữ thường. Dùng hàm đó đổi tất cả các ký tự của một chuỗi St nhập từ bàn phím ra chữ thường hết.
Bài 8.13: Nhập vào một chuỗi số nhị phân, đổi ra số hệ thập phân tương ứng.
Ví dụ : nhập chuỗi ‘1111’ , đổi ra số 15.
Bài 8.14: Viết chương trình sử dụng chương trình con tính các tổng sau với n là số nguyên dương, x là số thực bất kỳ nhập từ bàn phím khi thực hiện chương trình:
a) S = 1 + x + x2 + x3 + ... + xn
b) S = 1 + x + x2 + x3+ ... + (-1)nxn
c) S = 1 + x/1! + x2/2! + x3/3! + ...+ xn/n!
Bài 8.15: Viết một hàm đệ qui tính S= xn (x thực, n nguyên dương).
Bài 8.16:V iết một hàm đệ qui tính Sn:
Chia sẻ với bạn bè của bạn: |