Giáo trình lập trình nâng cao - Chương 5: Hướng dẫn chi tiết

Trư

ng ði hc Nông nghip 1

áo

ình

p

ình

ng cao

..............................................................



Chương 5

Gii thut ñ quy

Ni dung ca chương này ñ cp ñn nhng bài toán có tính ñ quy. Không phi bài

toán nào cũng có tính ñ quy và không phi các bài toán có tính ñ quy thì ñu phi gii b(ng

gii thut ñ quy. Các vn ñ c%n quan tâm trong chương này:

 Bài toán có tính ñ quy không

 Có c%n dùng gii thut ñ quy không

 ð quy có mang li hiu qu hơn các phương pháp thông thưng hay không

Trư

ng ði hc Nông nghip 1

áo

ình

p

ình

ng cao

..............................................................



1. Khái nim ñ quy



Trong thân mt chương trình con có th ñưa li gi ti chính chương trình con ñó, tính

cht này ñưc gi là tính "ð qui ca chương trình con".

Trong toán hc khái nim giai th a ñưc ñ"nh nghĩa như sau:

0! = 1

Nu n > 0 thì n! = 1*2*3*...*n

T ñ"nh nghĩa trên d, dàng thy r(ng

n! = n*(n-1)!

(n-1)! = (n-1)*(n-2)!

......

1! = 1*0! =1

Cách thc lp lun như trên ñưa chúng ta ti mt nhn xét t!ng quát là: li gii ca bài

toán A có th ñưc thc hin bi li gii ca bài toán A' có dng ging như A. Tht vy, vic

tính n! có th ñưc thc hin bi vic tính (n-1)!.

ðiu quan trng ñ bài toán có li gii là tuy A' ging như A song thc cht A' phi

nh/ hơn A và quá trình "thu nh/" phi có ñim d ng. Trong bài toán tính giai th a t ch' c%n

tính giai th a ca n chúng ta ñi tính giai th a ca (n-1), ñ tính giai th a ca (n-1) chúng ta ñi

tính giai th a ca (n-2)... kt thúc là giai th a ca 0.

Mt ñi tưng ñưc gi là ñ quy nu nó ñưc ñ"nh nghĩa dưi dng ca chính nó.

Gii thut ca bài toán A ñưc gi là ñ quy nu nó dn ti vic gii bài toán A' ging

như A nhưng nh/ hơn A và quá trình phi có ñim d ng.

Xét bài toán tính giai th a vi n = 5:

Ô nh cui 1! = 1

2! = 2*1!

3! = 3*2!

4! = 4*3!

Ô nh ñ%u 5! = 5*4!

Hình 5.1

Như vy khi bit 1! thì tính ñưc 2!, bit 2! Thì tính ñưc 3!,...

B(ng cách s dng b nh ngăn xp theo nguyên t&c LIFO ( Last In - First Out) (Hình

1.3) nhng gì gi vào cui cùng thì ñưc ly ra trưc tiên. Bóc ô nh trên ñ)nh ta có 1! = 1 và

l ra ô tip theo 2! = 2*1!. Vì 1! ñã bit nên tính ñưc 2! = 2, bóc tip ô nh phía dưi ta có

3! = 3*2!, vì 2! ñã bit nên 3! = 3*2 = 6 quá trình tip tc cho ñn khi bóc ô nh dưi cùng và

chúng ta nhn ñưc 5! = 120. Dưi ñây là chương trình tính giai th a

5! = 5*4!

4! = 4*3!

3! = 3*2!

2! = 2*1!

1! = 1

Trư

ng ði hc Nông nghip 1

áo

ình

p

ình

ng cao

..............................................................



Ví d 5.1:

Program Giaithua;

Uses crt;

Var n: integer;

Function GT(m: integr): integer; (* Hàm GT tính giai th a ca n*)

Begin

if m=0 then GT:=1 else GT:= m*GT(m-1); (*Gi ñ qui ca GT *)

End;

Begin

Clrscr;

write ('Tinh giai thua cua n = '); Readln (n) (*ðc giá tr" n*)

write('Gia thua cua ',n, ' = ',GT(n)); (* Vit giá tr" hàm GT *)

Repeat until keypressed;

End.

Ví d 5.1 có mt s! ñi u ñáng lưu ý sau ñây:

1. Hàm GT ñưc xây dng ñ tính giai th a vi tham s hình thc m, kiu ca m là kiu

Integer. Giá tr" m sau này s$ ñưc thay th b(ng tham s thc n qua li gi GT(n) trong

chương trình m+.

2. Khi ñ"nh nghĩa kiu ca GT là Integer thì giá tr" ca n ch) ñưc chn nh/ hơn 8 vì 8!

= 40320 vưt quá giá tr" cc ñi ca Integer (32767). ð có th tính giai th a vi n>=8 ta phi

ñ"nh nghĩa function GT có kiu Longint ho#c Real. Vi kiu Real lnh vit giá tr" ca giai

th a phi là vit s thc vi ph%n l0 b(ng 0, ví d:

Write (GT(n):12:0);

3. S dng thut toán ñ quy ñng nghĩa vi vic phi xây dng chương trình con, vì

vy nu s dng các vòng l#p có th gii ñưc bài toán thì nên dùng vòng l#p. Tr trưng hp

b&t buc phi gii bài toán không có tính l#p ho#c bài toán có kh năng truy hi.

Vi bài toán tính giai th a có th dùng vòng l#p và chúng ta thy chương trình s$ ñơn

gin hơn nhiu so vi cách dùng tính ñ quy:

Ví d 5.2

Program Tinh_GT;

Uses crt;

Var i,n:byte; gt:longint;

Begin

Clrscr;

Write(' Nhap gia tri n '); Readln(n);

if (n = 0) or (n=1) then gt:=1;

if n > 1 then gt:=1;

For i:= 1 to n do gt:=gt*i;

Writeln('Giai thua cua ',n,' = ',gt);

Trư

ng ði hc Nông nghip 1

áo

ình

p

ình

ng cao

..............................................................



Readln;

End.

Ví d 5.3: Lp chương trình tìm ưc s chung ln nht ca hai s nguyên n, m.

Ưc s chung ln nht ca hai s n và m tính theo công thc :

n nu m = 0

USC(n,m) =

USC(m, n mod m ) nu m <> 0

Ví d n= 4, m=8

USC(4,8) = USC(8, 4) = USC(4,0) = 4

Chương trình ñưc xây dng như sau:

Program timUSC ;

Uses crt;

Var n,m : word; Lam: Char;

FUNCTION USC(a,b:word): word;

Begin

If b=0 then USC := a Else USC := USC(b,a mod b);

End;

BEGIN

Repeat

Clrscr;

Write(' Hay cho hai so "n" va "m" can tim uoc so chung ');

Readln(n,m);

Writeln(' Uoc so chung lon nhat cua ',n,' va ',m, ' la ',USC(n,m):5);

Writeln;

Write('Tim tiep hay thoi ? C/K '); read(lam);

Until Upcase(lam)='K';

END.

Bài toán kinh ñin ng dng gii thut ñ quy là bài toán Tháp Hanoi. Ni dung bài

toán như sau:

Có n chic ñĩa tròn ñưng kính khác nhau, các ñĩa có l'  gia. Ngưi ta xp lng các

ñĩa này vào mt cc theo th t trên nh/ dưi to. Yêu c%u phi xp các ñĩa này sang cc mi

theo nguyên t&c:

1. M'i l%n ch) ñưc chuyn 1 ñĩa

2. Không ñưc ñ xy ra tình trng ñĩa to  trên, ñĩa nh/  dưi dù là tm thi

3. ðưc phép dùng mt cc trung gian

Trư

ng ði hc Nông nghip 1

áo

ình

p

ình

ng cao

..............................................................



Gi s cc ñ%u tiên là cc A, cc trung gian là B và cc c%n xp ñĩa sang là cc C.

Chúng ta s$ xét mt s trưng hp ñơn gin ñ tìm quy lut (Hình 5.2)

* n =1: cc A ch) có mt ñĩa

Chuyn ñĩa t cc A sang cc C

Kt thúc

A B C

Hình 5.2

* n = 2: cc A có 2 ñĩa (Hình 5.3)

Chuyn ñĩa trên sang B

Chuyn ñĩa dưi sang C

Chuyn ñĩa t B sang C

Kt thúc

A B C C

Hình 5.3

* n = 3: cc A có 3 ñĩa

Vi trưng hp 3 ñĩa nu chúng ta coi 2 ñĩa trên là mt ñĩa thì bài toán quy v trưng

hp n = 2, khi ñó li gii s$ là: (Hình 5.4)

Chuyn 2 ñĩa trên sang B

Chuyn ñĩa dưi cùng sang C

Chuyn 2 ñĩa t B sang C

Kt thúc

Giáo trình lập trình nâng cao - Chương 5

Tài liệu tham khảo Giáo trình lập trình nâng cao trên ngôn ngữ Pascal soạn theo chương trình đã được Bộ giáo dục và đào tạo phê chuẩn - Chương 5 Giải thuật đệ quy

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi