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
Nội dung trích xuất từ tài liệu:
Giáo trình lập trình nâng cao - Chương 5 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 - Giáo trình L p trình nâng cao ..............................................................- 133 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 5! = 5*4! 2! = 2*1! 4! = 4*3! 3! = 3*2! 3! = 3*2! 4! = 4*3! 2! = 2*1! Ô nh ñ u 5! = 5*4! 1! = 1 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 Trư ng ð i h c Nông nghi p 1 - Giáo trình L p trình nâng cao ..............................................................- 134 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 l 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 - Giáo trình L p trình nâng cao ..............................................................- 135 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 : nn um=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; Writ ...