Trường Đại học Điện lực Tập đoàn Điện lực Việt Nam

tải về 1.67 Mb.

trang	47/48
Chuyển đổi dữ liệu	18.07.2016
Kích	1.67 Mb.
	#1821

1 ... 40 41 42 43 44 45 46 47 48

BÀI TẬP CHƯƠNG 8

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 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;

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 ax² + 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 + x² + x³ + ... + xⁿ

b) S = 1 + x + x² + x³+ ... + (-1)ⁿxⁿ

c) S = 1 + x/1! + x²/2! + x³/3! + ...+ xⁿ/n!

Bài 8.15: Viết một hàm đệ qui tính S= xⁿ (x thực, n nguyên dương).
Bài 8.16:V

iết một hàm đệ qui tính Sn:

Каталог: images
images -> Hướng dẫn sử dụng Dropbox Để sử dụng được Dropbox
images -> BÀi thuyết trình cách xáC ĐỊnh và chế ĐỘ pháp lý CỦa các vùng biển theo công ưỚc của liên hiệp quốc về luật biển năM 19821
images -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
images -> Lúa gạo Việt Nam Giới thiệu
images -> Trung Tâm kt tc-đl-cl
images -> Số: 105/2008/QĐ-ttg CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
images -> ChuyêN ĐỀ ĐẠi số TỔ HỢP, XÁc suất kiến thức cơ bản Đại số tổ hợp
images -> BỘ giáo dục và ĐÀo tạo trưỜng đẠi học luật tp. HỒ chí minh dưƠng kim thế nguyên thủ TỤc phá SẢn các tổ chức tín dụng theo pháp luật việt nam
images -> Review of Condor, Sun Grid Engine and pbs

tải về 1.67 Mb.

Chia sẻ với bạn bè của bạn:

1 ... 40 41 42 43 44 45 46 47 48