[Giáo trình Toán rời rạc] - Chương1 - Thuật Toán

Chia sẻ: Trần Bá Trung5 | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

95
lượt xem 46
download

[Giáo trình Toán rời rạc] - Chương1 - Thuật Toán

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu " [Giáo trình Toán rời rạc] - Chương1 - Thuật Toán " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: [Giáo trình Toán rời rạc] - Chương1 - Thuật Toán

http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG I: THU T TOÁN 1.1. KHÁI NI M THU T TOÁN. 1.1.1. M ñ u: Có nhi u l p bài toán t ng quát xu t hi n trong toán h c r i r c. Ch ng h n, cho m t dãy các s nguyên, tìm s l n nh t; cho m t t p h p, li t kê các t p con c a nó; cho t p h p các s nguyên, x p chúng theo th t tăng d n; cho m t m ng, tìm ñư ng ñi ng n nh t gi a hai ñ nh c a nó. Khi ñư c giao cho m t bài toán như v y thì vi c ñ u tiên ph i làm là xây d ng m t mô hình d ch bài toán ñó thành ng c nh toán h c. Các c u trúc r i r c ñư c dùng trong các mô hình này là t p h p, dãy, hàm, hoán v , quan h , cùng v i các c u trúc khác như ñ th , cây, m ng - nh ng khái ni m s ñư c nghiên c u các chương sau. L p ñư c m t mô hình toán h c thích h p ch là m t ph n c a quá trình gi i. ð hoàn t t quá trình gi i, còn c n ph i có m t phương pháp dùng mô hình ñ gi i bài toán t ng quát. Nói m t cách lý tư ng, cái ñư c ñòi h i là m t th t c, ñó là dãy các bư c d n t i ñáp s mong mu n. M t dãy các bư c như v y, ñư c g i là m t thu t toán. Khi thi t k và cài ñ t m t ph n m m tin h c cho m t v n ñ nào ñó, ta c n ph i ñưa ra phương pháp gi i quy t mà th c ch t ñó là thu t toán gi i quy t v n ñ này. Rõ ràng r ng, n u không tìm ñư c m t phương pháp gi i quy t thì không th l p trình ñư c. Chính vì th , thu t toán là khái ni m n n t ng c a h u h t các lĩnh v c c a tin h c. 1.1.2. ð nh nghĩa: Thu t toán là m t b ng li t kê các ch d n (hay quy t c) c n th c hi n theo t ng bư c xác ñ nh nh m gi i m t bài toán ñã cho. Thu t ng “Algorithm” (thu t toán) là xu t phát t tên nhà toán h c R p Al- Khowarizmi. Ban ñ u, t algorism ñư c dùng ñ ch các quy t c th c hi n các phép tính s h c trên các s th p phân. Sau ñó, algorism chuy n thành algorithm vào th k 19. V i s quan tâm ngày càng tăng ñ i v i các máy tính, khái ni m thu t toán ñã ñư c cho m t ý nghĩa chung hơn, bao hàm c các th t c xác ñ nh ñ gi i các bài toán, ch không ph i ch là th t c ñ th c hi n các phép tính s h c. Có nhi u cách trình bày thu t toán: dùng ngôn ng t nhiên, ngôn ng lưu ñ (sơ ñ kh i), ngôn ng l p trình. Tuy nhiên, m t khi dùng ngôn ng l p trình thì ch nh ng l nh ñư c phép trong ngôn ng ñó m i có th dùng ñư c và ñi u này thư ng làm cho s mô t các thu t toán tr nên r i r m và khó hi u. Hơn n a, vì nhi u ngôn ng l p trình ñ u ñư c dùng r ng rãi, nên ch n m t ngôn ng ñ c bi t nào ñó là ñi u ngư i ta không mu n. Vì v y ñây các thu t toán ngoài vi c ñư c trình bày b ng ngôn ng t nhiên cùng v i nh ng ký hi u toán h c quen thu c còn dùng m t d ng gi mã ñ mô t thu t 4
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p toán. Gi mã t o ra bư c trung gian gi a s mô t m t thu t toán b ng ngôn ng thông thư ng và s th c hi n thu t toán ñó trong ngôn ng l p trình. Các bư c c a thu t toán ñư c ch rõ b ng cách dùng các l nh gi ng như trong các ngôn ng l p trình. Thí d 1: Mô t thu t toán tìm ph n t l n nh t trong m t dãy h u h n các s nguyên. a) Dùng ngôn ng t nhiên ñ mô t các bư c c n ph i th c hi n: 1. ð t giá tr c c ñ i t m th i b ng s nguyên ñ u tiên trong dãy. (C c ñ i t m th i s là s nguyên l n nh t ñã ñư c ki m tra m t giai ño n nào ñó c a th t c.) 2. So sánh s nguyên ti p sau v i giá tr c c ñ i t m th i, n u nó l n hơn giá tr c c ñ i t m th i thì ñ t c c ñ i t m th i b ng s nguyên ñó. 3. L p l i bư c trư c n u còn các s nguyên trong dãy. 4. D ng khi không còn s nguyên nào n a trong dãy. C c ñ i t m th i ñi m này chính là s nguyên l n nh t c a dãy. b) Dùng ño n gi mã: procedure max (a1, a2, ..., an: integers) max:= a1 for i:= 2 to n if max
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ki m tra chính t c a các t , tìm ki m các t này trong m t cu n t ñi n, mà t ñi n ch ng qua cũng là m t b ng li t kê s p th t c a các t . Các bài toán thu c lo i này ñư c g i là các bài toán tìm ki m. Bài toán tìm ki m t ng quát ñư c mô t như sau: xác ñ nh v trí c a ph n t x trong m t b ng li t kê các ph n t phân bi t a1, a2, ..., an ho c xác ñ nh r ng nó không có m t trong b ng li t kê ñó. L i gi i c a bài toán trên là v trí c a s h ng c a b ng li t kê có giá tr b ng x (t c là i s là nghi m n u x=ai và là 0 n u x không có m t trong b ng li t kê). 1.2.2. Thu t toán tìm ki m tuy n tính: Tìm ki m tuy n tính hay tìm ki m tu n t là b t ñ u b ng vi c so sánh x v i a1; khi x=a1, nghi m là v trí a1, t c là 1; khi x≠a1, so sánh x v i a2. N u x=a2, nghi m là v trí c a a2, t c là 2. Khi x≠a2, so sánh x v i a3. Ti p t c quá trình này b ng cách tu n t so sánh x v i m i s h ng c a b ng li t kê cho t i khi tìm ñư c s h ng b ng x, khi ñó nghi m là v trí c a s h ng ñó. N u toàn b ng li t kê ñã ñư c ki m tra mà không xác ñ nh ñư c v trí c a x, thì nghi m là 0. Gi mã ñ i v i thu t toán tìm ki m tuy n tính ñư c cho dư i ñây: procedure tìm ki m tuy n tính (x: integer, a1,a2,...,an: integers phân bi t) i := 1 while (i ≤ n and x ≠ ai) i := i + 1 if i ≤ n then location := i else location := 0 {location là ch s dư i c a s h ng b ng x ho c là 0 n u không tìm ñư c x} 1.2.3. Thu t toán tìm ki m nh phân: Thu t toán này có th ñư c dùng khi b ng li t kê có các s h ng ñư c s p theo th t tăng d n. Ch ng h n, n u các s h ng là các s thì chúng ñư c s p t s nh nh t ñ n s l n nh t ho c n u chúng là các t hay xâu ký t thì chúng ñư c s p theo th t t ñi n. Thu t toán th hai này g i là thu t toán tìm ki m nh phân. Nó ñư c ti n hành b ng cách so sánh ph n t c n xác ñ nh v trí v i s h ng gi a b ng li t kê. Sau ñó b ng này ñư c tách làm hai b ng kê con nh hơn có kích thư c như nhau, ho c m t trong hai b ng con ít hơn b ng con kia m t s h ng. S tìm ki m ti p t c b ng cách h n ch tìm ki m m t b ng kê con thích h p d a trên vi c so sánh ph n t c n xác ñ nh v trí v i s h ng gi a b ng kê. Ta s th y r ng thu t toán tìm ki m nh phân hi u qu hơn nhi u so v i thu t toán tìm ki m tuy n tính. Thí d 2. ð tìm s 19 trong b ng li t kê 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 ta tách b ng li t kê g m 16 s h ng này thành hai b ng li t kê nh hơn, m i b ng có 8 s h ng, c th là: 1,2,3,5,6,7,8,10 và 12,13,15,16,18,19,20,22. Sau ñó ta so sánh 19 v i s h ng cu i cùng c a b ng con th nh t. Vì 10
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p l i tách b ng li t kê con g m 8 s h ng này làm hai b ng con, m i b ng có 4 s h ng, c th là 12,13,15,16 và 18,19,20,22. Vì 16am then i:=m+1 else j := m end if x = ai then location := i else location := 0 {location là ch s dư i c a s h ng b ng x ho c 0 n u không tìm th y x} 1.3. ð PH C T P C A THU T TOÁN. 1.3.1. Khái ni m v ñ ph c t p c a m t thu t toán: Thư c ño hi u qu c a m t thu t toán là th i gian mà máy tính s d ng ñ gi i bài toán theo thu t toán ñang xét, khi các giá tr ñ u vào có m t kích thư c xác ñ nh. 7
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p M t thư c ño th hai là dung lư ng b nh ñòi h i ñ th c hi n thu t toán khi các giá tr ñ u vào có kích thư c xác ñ nh. Các v n ñ như th liên quan ñ n ñ ph c t p tính toán c a m t thu t toán. S phân tích th i gian c n thi t ñ gi i m t bài toán có kích thư c ñ c bi t nào ñó liên quan ñ n ñ ph c t p th i gian c a thu t toán. S phân tích b nh c n thi t c a máy tính liên quan ñ n ñ ph c t p không gian c a thu t toán. V c xem xét ñ ph c t p th i gian và không gian c a m t thu t toán là m t v n ñ r t thi t y u khi các thu t toán ñư c th c hi n. Bi t m t thu t toán s ñưa ra ñáp s trong m t micro giây, trong m t phút ho c trong m t t năm, hi n nhiên là h t s c quan tr ng. Tương t như v y, dung lư ng b nh ñòi h i ph i là kh d ng ñ gi i m t bài toán,vì v y ñ ph c t p không gian cũng c n ph i tính ñ n.Vì vi c xem xét ñ ph c t p không gian g n li n v i các c u trúc d li u ñ c bi t ñư c dùng ñ th c hi n thu t toán nên ñây ta s t p trung xem xét ñ ph c t p th i gian. ð ph c t p th i gian c a m t thu t toán có th ñư c bi u di n qua s các phép toán ñư c dùng b i thu t toán ñó khi các giá tr ñ u vào có m t kích thư c xác ñ nh. S dĩ ñ ph c t p th i gian ñư c mô t thông qua s các phép toán ñòi h i thay vì th i gian th c c a máy tính là b i vì các máy tính khác nhau th c hi n các phép tính sơ c p trong nh ng kho ng th i gian khác nhau. Hơn n a, phân tích t t c các phép toán thành các phép tính bit sơ c p mà máy tính s d ng là ñi u r t ph c t p. Thí d 3: Xét thu t toán tìm s l n nh t trong dãy n s a1, a2, ..., an. Có th coi kích thư c c a d li u nh p là s lư ng ph n t c a dãy s , t c là n. N u coi m i l n so sánh hai s c a thu t toán ñòi h i m t ñơn v th i gian (giây ch ng h n) thì th i gian th c hi n thu t toán trong trư ng h p x u nh t là n-1 giây. V i dãy 64 s , th i gian th c hi n thu t toán nhi u l m là 63 giây. Thí d 4:Thu t toán v trò chơi “Tháp Hà N i” Trò chơi “Tháp Hà N i” như sau: Có ba c c A, B, C và 64 cái ñĩa (có l ñ ñ t vào c c), các ñĩa có ñư ng kính ñôi m t khác nhau. Nguyên t c ñ t ñĩa vào c c là: m i ñĩa ch ñư c ch ng lên ñĩa l n hơn nó. Ban ñ u, c 64 ñĩa ñư c ñ t ch ng lên nhau c t A; hai c t B, C tr ng. V n ñ là ph i chuy n c 64 ñĩa ñó sang c t B hay C, m i l n ch ñư c di chuy n m t ñĩa. Xét trò chơi v i n ñĩa ban ñ u c c A (c c B và C tr ng). G i Sn là s l n chuy n ñĩa ñ chơi xong trò chơi v i n ñĩa. N u n=1 thì rõ ràng là S1=1. N u n>1 thì trư c h t ta chuy n n-1 ñĩa bên trên sang c c B (gi yên ñĩa th n dư i cùng c a c c A). S l n chuy n n-1 ñĩa là Sn-1. Sau ñó ta chuy n ñĩa th n t c c A sang c c C. Cu i cùng, ta chuy n n-1 ñĩa t c c B sang c c C (s l n chuy n là Sn-1). Như v y, s l n chuy n n ñĩa t A sang C là: Sn=Sn-1+1+Sn=2Sn-1+1=2(2Sn-2+1)+1=22Sn-2+2+1=.....=2n-1S1+2n-2+...+2+1=2n−1. 8
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Thu t toán v trò chơi “Tháp Hà N i” ñòi h i 264−1 l n chuy n ñĩa (x p x 18,4 t t l n). N u m i l n chuy n ñĩa m t 1 giây thì th i gian th c hi n thu t toán x p x 585 t năm! Hai thí d trên cho th y r ng: m t thu t toán ph i k t thúc sau m t s h u h n bư c, nhưng n u s h u h n này quá l n thì thu t toán không th th c hi n ñư c trong th c t . Ta nói: thu t toán trong Thí d 3 có ñ ph c t p là n-1 và là m t thu t toán h u hi u (hay thu t toán nhanh); thu t toán trong Thí d 4 có ñ ph c t p là 2n−1 và ñó là m t thu t toán không h u hi u (hay thu t toán ch m). 1.3.2. So sánh ñ ph c t p c a các thu t toán: M t bài toán thư ng có nhi u cách gi i, có nhi u thu t toán ñ gi i, các thu t toán ñó có ñ ph c t p khác nhau. Xét bài toán: Tính giá tr c a ña th c P(x)=anxn+an-1xn-1+ ... +a1x+a0 t i x0. Thu t toán 1: Procedure tính giá tr c a ña th c (a0, a1, ..., an, x0: các s th c) sum:=a0 for i:=1 to n sum:=sum+aix0i {sum là giá tr c a ña th c P(x) t i x0} Chú ý r ng ña th c P(x) có th vi t dư i d ng: P(x)=(...((anx+an-1)x+an-2)x...)x+a0. Ta có th tính P(x) theo thu t toán sau: Thu t toán 2: Procedure tính giá tr c a ña th c (a0, a1, ..., an, x0: các s th c) P:=an for i:=1 to n P:=P.x0+an-i {P là giá tr c a ña th c P(x) t i x0} Ta hãy xét ñ ph c t p c a hai thu t toán trên. ð i v i thu t toán 1: bư c 2, ph i th c hi n 1 phép nhân và 1 phép c ng v i i=1; 2 phép nhân và 1 phép c ng v i i=2, ..., n phép nhân và 1 phép c ng v i i=n. V y s phép tính (nhân và c ng) mà thu t toán 1 ñòi h i là: n(n + 1) n(n + 3) (1+1)+(2+1)+ ... +(n+1)= +n= . 2 2 ð i v i thu t toán 2, bư c 2 ph i th c hi n n l n, m i l n ñòi h i 2 phép tính (nhân r i c ng), do ñó s phép tính (nhân và c ng) mà thu t toán 2 ñòi h i là 2n. 9
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p N u coi th i gian th c hi n m i phép tính nhân và c ng là như nhau và là m t ñơn v th i gian thì v i m i n cho trư c, th i gian th c hi n thu t toán 1 là n(n+3)/2, còn th i gian th c hi n thu t toán 2 là 2n. Rõ ràng là th i gian th c hi n thu t toán 2 ít hơn so v i th i gian th c hi n thu t toán 1. Hàm f1(n)=2n là hàm b c nh t, tăng ch m hơn nhi u so v i hàm b c hai f2(n)=n(n+3)/2. Ta nói r ng thu t toán 2 (có ñ ph c t p là 2n) là thu t toán h u hi u hơn (hay nhanh hơn) so v i thu t toán 1 (có ñ ph c t p là n(n+3)/2). ð so sánh ñ ph c t p c a các thu t toán, ñi u ti n l i là coi ñ ph c t p c a m i thu t toán như là c p c a hàm bi u hi n th i gian th c hi n thu t toán y. Các hàm xét sau ñây ñ u là hàm c a bi n s t nhiên n>0. ð nh nghĩa 1:Ta nói hàm f(n) có c p th p hơn hay b ng hàm g(n) n u t n t i h ng s C>0 và m t s t nhiên n0 sao cho |f(n)| ≤ C|g(n)| v i m i n≥n0. Ta vi t f(n)=O(g(n)) và còn nói f(n) tho mãn quan h big-O ñ i v i g(n). Theo ñ nh nghĩa này, hàm g(n) là m t hàm ñơn gi n nh t có th ñư c, ñ i di n cho “s bi n thiên” c a f(n). Khái ni m big-O ñã ñư c dùng trong toán h c ñã g n m t th k nay. Trong tin h c, nó ñư c s d ng r ng rãi ñ phân tích các thu t toán. Nhà toán h c ngư i ð c Paul Bachmann là ngư i ñ u tiên ñưa ra khái ni m big-O vào năm 1892. n(n + 3) Thí d 5: Hàm f(n)= là hàm b c hai và hàm b c hai ñơn gi n nh t là n2. Ta có: 2 n(n + 3) n(n + 3) f(n)= =O(n2) vì ≤ n2 v i m i n≥3 (C=1, n0=3). 2 2 M t cách t ng quát, n u f(n)=aknk+ak-1nk-1+ ... +a1n+a0 thì f(n)=O(nk). Th t v y, v i n>1, |f(n)|| ≤ |ak|nk+|ak-1|nk-1+ ... +|a1|n+|a0| = nk(|ak|+|ak-1|/n+ ... +|a1|/nk-1+a0/nk) ≤ nk(|ak|+|ak-1|+ ... +|a1|+a0). ði u này ch ng t |f(n)| ≤ Cnk v i m i n>1. Cho g(n)=3n+5nlog2n, ta có g(n)=O(nlog2n). Th t v y, 3n+5nlog2n = n(3+5log2n) ≤ n(log2n+5log2n) = 6nlog2n v i m i n≥8 (C=6, n0=8). M nh ñ : Cho f1(n)=O(g1(n)) và f2(n) là O(g2(n)). Khi ñó (f1 + f2)(n) = O(max(|g1(n)|,|g2(n)|), (f1f2)(n) = O(g1(n)g2(n)). Ch ng minh. Theo gi thi t, t n t i C1, C2, n1, n2 sao cho |f1(n)| ≤ C1|g1(n)| và |f2(n)| ≤ C2|g2(n)| v i m i n > n1 và m i n > n2. Do ñó |(f1 + f2)(n)| = |f1(n) + f2(n)| ≤ |f1(n)| + |f2(n)| ≤ C1|g1(n)| + C2|g2(n)| ≤ (C1+C2)g(n) v i m i n > n0=max(n1,n2), ñâyC=C1+C2 và g(n)=max(|g1(n)| , |g2(n)|). |(f1f2)(n)| = |f1(n)||f2(n)| ≤ C1|g1(n)|C2|g2(n)| ≤ C1C2|(g1g2)(n)| v i m i n > n0=max(n1,n2). 10
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ð nh nghĩa 2: N u m t thu t toán có ñ ph c t p là f(n) v i f(n)=O(g(n)) thì ta cũng nói thu t toán có ñ ph c t p O(g(n)). N u có hai thu t toán gi i cùng m t bài toán, thu t toán 1 có ñ ph c t p O(g1(n)), thu t toán 2 có ñ ph c t p O(g2(n)), mà g1(n) có c p th p hơn g2(n), thì ta nói r ng thu t toán 1 h u hi u hơn (hay nhanh hơn) thu t toán 2. 1.3.3. ðánh giá ñ ph c t p c a m t thu t toán: 1) Thu t toán tìm ki m tuy n tính: S các phép so sánh ñư c dùng trong thu t toán này cũng s ñư c xem như thư c ño ñ ph c t p th i gian c a nó. m i m t bư c c a vòng l p trong thu t toán, có hai phép so sánh ñư c th c hi n: m t ñ xem ñã t i cu i b ng chưa và m t ñ so sánh ph n t x v i m t s h ng c a b ng. Cu i cùng còn m t phép so sánh n a làm ngoài vòng l p. Do ñó, n u x=ai, thì ñã có 2i+1 phép so sánh ñư c s d ng. S phép so sánh nhi u nh t, 2n+2, ñòi h i ph i ñư c s d ng khi ph n t x không có m t trong b ng. T ñó, thu t toán tìm ki m tuy n tính có ñ ph c t p là O(n). 2) Thu t toán tìm ki m nh phân: ð ñơn gi n, ta gi s r ng có n=2k ph n t trong b ng li t kê a1,a2,...,an, v i k là s nguyên không âm (n u n không ph i là lũy th a c a 2, ta có th xem b ng là m t ph n c a b ng g m 2k+1 ph n t , trong ñó k là s nguyên nh nh t sao cho n < 2k+1). m i giai ño n c a thu t toán v trí c a s h ng ñ u tiên i và s h ng cu i cùng j c a b ng con h n ch tìm ki m giai ño n ñó ñư c so sánh ñ xem b ng con này còn nhi u hơn m t ph n t hay không. N u i < j, m t phép so sánh s ñư c làm ñ xác ñ nh x có l n hơn s h ng gi a c a b ng con h n ch hay không. Như v y m i giai ño n, có s d ng hai phép so sánh. Khi trong b ng ch còn m t ph n t , m t phép so sánh s cho chúng ta bi t r ng không còn m t ph n t nào thêm n a và m t phép so sánh n a cho bi t s h ng ñó có ph i là x hay không. Tóm l i c n ph i có nhi u nh t 2k+2=2log2n+2 phép so sánh ñ th c hi n phép tìm ki m nh phân (n u n không ph i là lũy th a c a 2, b ng g c s ñư c m r ng t i b ng có 2k+1 ph n t , v i k=[log2n] và s tìm ki m ñòi h i ph i th c hi n nhi u nh t 2[log2n]+2 phép so sánh). Do ñó thu t toán tìm ki m nh phân có ñ ph c t p là O(log2n). T s phân tích trên suy ra r ng thu t toán tìm ki m nh phân, ngay c trong trư ng h p x u nh t, cũng hi u qu hơn thu t toán tìm ki m tuy n tính. 3) Chú ý: M t ñi u quan tr ng c n ph i bi t là máy tính ph i c n bao lâu ñ gi i xong m t bài toán. Thí d , n u m t thu t toán ñòi h i 10 gi , thì có th còn ñáng chi phí th i gian máy tính ñòi h i ñ gi i bài toán ñó. Nhưng n u m t thu t toán ñòi h i 10 t năm ñ gi i m t bài toán, thì th c hi n thu t toán ñó s là m t ñi u phi lý. M t trong nh ng hi n tư ng lý thú nh t c a công ngh hi n ñ i là s tăng ghê g m c a t c ñ và lư ng b nh trong máy tính. M t nhân t quan tr ng khác làm gi m th i gian c n thi t ñ gi i m t 11
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p bài toán là s x lý song song - ñây là k thu t th c hi n ñ ng th i các dãy phép tính. Do s tăng t c ñ tính toán và dung lư ng b nh c a máy tính, cũng như nh vi c dùng các thu t toán l i d ng ñư c ưu th c a k thu t x lý song song, các bài toán vài năm trư c ñây ñư c xem là không th gi i ñư c, thì bây gi có th gi i bình thư ng. 1. Các thu t ng thư ng dùng cho ñ ph c t p c a m t thu t toán: ð ph c t p Thu t ng O(1) ð ph c t p h ng s O(logn) ð ph c t p lôgarit O(n) ð ph c t p tuy n tính O(nlogn) ð ph c t p nlogn b O(n ) ð ph c t p ña th c n O(b ) (b>1) ð ph c t p hàm mũ O(n!) ð ph c t p giai th a 2. Th i gian máy tính ñư c dùng b i m t thu t toán: Kích thư c Các phép tính bit ñư c s d ng c a bài toán n logn N nlogn n2 2n n! 10 3.10-9 s 10-8 s 3.10-8 s 10-7 s 10-6 s 3.10-3 s 102 7.10-9 s 10-7 s 7.10-7 s 10-5 s 4.1013năm * 103 1,0.10-8 s 10-6 s 1.10-5 s 10-3 s * * 104 1,3.10-8 s 10-5 s 1.10-4 s 10-1 s * * 105 1,7.10-8 s 10-4 s 2.10-3 s 10 s * * 106 2.10-8 s 10-3 s 2.10-2 s 17 phút * * 1.4. S NGUYÊN VÀ THU T TOÁN. 1.4.1. Thu t toán Euclide: Phương pháp tính ư c chung l n nh t c a hai s b ng cách dùng phân tích các s nguyên ñó ra th a s nguyên t là không hi u qu . Lý do là ch th i gian ph i tiêu t n cho s phân tích ñó. Dư i ñây là phương pháp hi u qu hơn ñ tìm ư c s chung l n nh t, g i là thu t toán Euclide. Thu t toán này ñã bi t t th i c ñ i. Nó mang tên nhà toán h c c Hy l p Euclide, ngư i ñã mô t thu t toán này trong cu n sách “Nh ng y u t ” n i ti ng c a ông. Thu t toán Euclide d a vào 2 m nh ñ sau ñây. M nh ñ 1 (Thu t toán chia): Cho a và b là hai s nguyên và b≠0. Khi ñó t n t i duy nh t hai s nguyên q và r sao cho a = bq+r, 0 ≤ r < |b|. Trong ñ ng th c trên, b ñư c g i là s chia, a ñư c g i là s b chia, q ñư c g i là thương s và r ñư c g i là s dư. 12
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Khi b là nguyên dương, ta ký hi u s dư r trong phép chia a cho b là a mod b. M nh ñ 2: Cho a = bq + r, trong ñó a, b, q, r là các s nguyên. Khi ñó UCLN(a,b) = UCLN(b,r). ( ñây UCLN(a,b) ñ ch ư c chung l n nh t c a a và b.) Gi s a và b là hai s nguyên dương v i a ≥ b. ð t r0 = a và r1 = b. B ng cách áp d ng liên ti p thu t toán chia, ta tìm ñư c: r0 = r1 q1 + r2 0 ≤ r2 < r1 r1 = r2 q2 + r3 0 ≤ r3 < r2 .................. rn-2 = rn-1qn-1 + rn 0 ≤ rn < rn-1 rn-1 = rnqn . Cu i cùng, s dư 0 s xu t hi n trong dãy các phép chia liên ti p, vì dãy các s dư a = r0 > r1 > r2 >... ≥ 0 không th ch a quá a s h ng ñư c. Hơn n a, t M nh ñ 2 trên ta suy ra: UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = ... = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn. Do ñó, ư c chung l n nh t là s dư khác không cu i cùng trong dãy các phép chia. Thí d 6: Dùng thu t toán Euclide tìm UCLN(414, 662). 662 = 441.1 + 248 414 = 248.1 + 166 248 = 166.1+ 82 166 = 82.2 + 2 82 = 2.41. Do ñó, UCLN(414, 662) = 2. Thu t toán Euclide ñư c vi t dư i d ng gi mã như sau: procedure ƯCLN (a,b: positive integers) x := a y := b while y ≠ 0 begin r := x mod y x := y y := r end {UCLN (a,b) là x} Trong thu t toán trên, các giá tr ban ñ u c a x và y tương ng là a và b. m i giai ño n c a th t c, x ñư c thay b ng y và y ñư c thay b ng x mod y. Quá trình này ñư c l p l i ch ng nào y ≠ 0. Thu t toán s ng ng khi y = 0 và giá tr c a x ñi m này, ñó là s dư khác không cu i cùng trong th t c, cũng chính là ư c chung l n nh t c a a và b. 13
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 1.4.2. Bi u di n các s nguyên: M nh ñ 3: Cho b là m t s nguyên dương l n hơn 1. Khi ñó n u n là m t s nguyên dương, nó có th ñư c bi u di n m t cách duy nh t dư i d ng: n = akbk + ak-1bk-1 + ... + a1b + a0. ñây k là m t s t nhiên, a0, a1,..., ak là các s t nhiên nh hơn b và ak ≠ 0. Bi u di n c a n ñư c cho trong M nh ñ 3 ñư c g i là khai tri n c a n theo cơ s b, ký hi u là (akak-1... a1a0)b. Bây gi ta s mô t thu t toán xây d ng khai tri n cơ s b c a s nguyên n b t kỳ. Trư c h t ta chia n cho b ñ ñư c thương và s dư, t c là n = bq0 + a0, 0 ≤ a0 < b. S dư a0 chính là ch s ñ ng bên ph i cùng trong khai tri n cơ s b c a n. Ti p theo chia q0 cho b, ta ñư c: q0 = bq1 + a1, 0 ≤ a1 < b. S dư a1 chính là ch s th hai tính t bên ph i trong khai tri n cơ s b c a n. Ti p t c quá trình này, b ng cách liên ti p chia các thương cho b ta s ñư c các ch s ti p theo trong khai tri n cơ s b c a n là các s dư tương ng. Quá trình này s k t thúc khi ta nh n ñư c m t thương b ng 0. Thí d 7: Tìm khai tri n cơ s 8 c a (12345)10. 12345 = 8.1543 + 1 1543 = 8.192 + 7 192 = 8.24 + 0 24 = 8.3 + 0 3 = 8.0 + 3. Do ñó, (12345)10 = (30071)8. ðo n gi mã sau bi u di n thu t toán tìm khai tri n cơ s b c a s nguyên n. procedure khai tri n theo cơ s b (n: positive integer) q := n k := 0 while q ≠ 0 begin ak := q mod b q q := [ ] b k := k + 1 end 1.4.3. Thu t toán cho các phép tính s nguyên: Các thu t toán th c hi n các phép tính v i nh ng s nguyên khi dùng các khai tri n nh phân c a chúng là c c kỳ quan tr ng trong s h c c a máy tính. Ta s mô t 14
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ñây các thu t toán c ng và nhân hai s nguyên trong bi u di n nh phân. Ta cũng s phân tích ñ ph c t p tính toán c a các thu t toán này thông qua s các phép toán bit th c s ñư c dùng. Gi s khai tri n nh phân c a hai s nguyên dương a và b là: a = (an-1an-2 ... a1 a0)2 và b = (bn-1 bn-2 ... b1 b0)2 sao cho a và b ñ u có n bit (ñ t các bit 0 ñ u m i khai tri n ñó, n u c n). 1) Phép c ng: Xét bài toán c ng hai s nguyên vi t d ng nh phân. Th t c th c hi n phép c ng có th d a trên phương pháp thông thư ng là c ng c p ch s nh phân v i nhau (có nh ) ñ tính t ng c a hai s nguyên. ð c ng a và b, trư c h t c ng hai bit ph i cùng c a chúng, t c là: a0 + b0 = c0.2 + s0. ñây s0 là bit ph i cùng trong khai tri n nh phân c a a+b, c0 là s nh , nó có th b ng 0 ho c 1. Sau ñó ta c ng hai bit ti p theo và s nh a1 + b1 + c0 = c1.2 + s1. ñây s1 là bit ti p theo (tính t bên ph i) trong khai tri n nh phân c a a+b và c1 là s nh . Ti p t c quá trình này b ng cách c ng các bit tương ng trong hai khai tri n nh phân và s nh ñ xác ñ nh bit ti p sau tính t bên ph i trong khai tri n nh phân c a t ng a+b. giai ño n cu i cùng, c ng an-1, bn-1 và cn-2 ñ nh n ñư c cn-1.2+sn-1. Bit ñ ng ñ u c a t ng là sn=cn-1. K t qu , th t c này t o ra ñư c khai tri n nh phân c a t ng, c th là a+b = (sn sn-1 sn-2 ... s1 s0)2. Thí d 8: Tìm t ng c a a = (11011)2 và b = (10110)2. a0 + b0 = 1 + 0 = 0.2 + 1 (c0 = 0, s0 = 1), a1 + b1 + c0 = 1 + 1 + 0 = 1.2 + 0 (c1 = 1, s1 = 0), a2 + b2 +c1 = 0 + 1 + 1 = 1.2 + 0 (c2 = 1, s2 = 0), a3 + b3 + c2 = 1 + 0 + 1 = 1.2 + 0 (c3 = 1, s3 = 0), a4 + b4 +c3 = 1 + 1 + 1 = 1.2 + 1 (s5 = c4 =1, s4 = 1). Do ñó, a + b = (110001)2. Thu t toán c ng có th ñư c mô t b ng cách dùng ño n gi mã như sau. procedure c ng (a,b: positive integers) c := 0 for j := 0 to n-1 begin a j + b j + c d :=    2  sj := aj + bj + c − 2d c := d end sn := c {khai tri n nh phân c a t ng là (sn sn-1 ...s1 s0) 2} 15
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p T ng hai s nguyên ñư c tính b ng cách c ng liên ti p các c p bit và khi c n ph i c ng c s nh n a. C ng m t c p bit và s nh ñòi ba ho c ít hơn phép c ng các bit. Như v y, t ng s các phép c ng bit ñư c s d ng nh hơn ba l n s bit trong khai tri n nh phân. Do ñó, ñ ph c t p c a thu t toán này là O(n). 2) Phép nhân: Xét bài toán nhân hai s nguyên vi t d ng nh phân. Thu t toán thông thư ng ti n hành như sau. Dùng lu t phân ph i, ta có: n−1 n−1 ab = a ∑ b j 2 =j ∑ a(b j 2 j ) . j =0 j =0 Ta có th tính ab b ng cách dùng phương trình trên. Trư c h t, ta th y r ng abj=a n u bj=1 và abj=0 n u bj=0. M i l n ta nhân m t s h ng v i 2 là ta d ch khai tri n nh phân c a nó m t ch v phía trái b ng cách thêm m t s không vào cu i khai tri n nh phân c a nó. Do ñó, ta có th nh n ñư c (abj)2j b ng cách d ch khai tri n nh phân c a abj ñi j ch v phía trái, t c là thêm j s không vào cu i khai tri n nh phân c a nó. Cu i cùng, ta s nh n ñư c tích ab b ng cách c ng n s nguyên abj.2j v i j=0, 1, ..., n-1. Thí d 9: Tìm tích c a a = (110)2 và b = (101)2. Ta có ab0.20 = (110)2.1.20 = (110)2, ab1.21 = (110)2.0.21 = (0000)2, ab2.22 = (110)2.1.22 = (11000)2. ð tìm tích, hãy c ng (110)2, (0000)2 và (11000)2. T ñó ta có ab= (11110)2. Th t c trên ñư c mô t b ng ño n gi mã sau: procedure nhân (a,b: positive integers) for j := 0 to n-1 begin if bj = 1 then cj := a ñư c d ch ñi j ch else cj := 0 end {c0, c1,..., cn-1 là các tích riêng ph n} p := 0 for j := 0 to n-1 p := p + cj {p là giá tr c a tích ab} Thu t toán trên tính tích c a hai s nguyên a và b b ng cách c ng các tích riêng ph n c0, c1, c2, ..., cn-1. Khi bj=1, ta tính tích riêng ph n cj b ng cách d ch khai tri n nh phân c a a ñi j bit. Khi bj=0 thì không c n có d ch chuy n nào vì cj=0. Do ñó, ñ tìm t t c n s nguyên abj.2j v i j=0, 1, ..., n-1, ñòi h i t i ña là n(n − 1) 0 + 1 + 2 + ... + n−1 = 2 phép d ch ch . Vì v y, s các d ch chuy n ch ñòi h i là O(n2). 16
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ð c ng các s nguyên abj t j=0 ñ n n−1, ñòi h i ph i c ng m t s nguyên n bit, m t s nguyên n+1 bit, ... và m t s nguyên 2n bit. Ta ñã bi t r ng m i phép c ng ñó ñòi h i O(n) phép c ng bit. Do ñó, ñ ph c t p c a thu t toán này là O(n2). 1.5. THU T TOÁN ð QUY. 1.5.1. Khái ni m ñ quy: ðôi khi chúng ta có th quy vi c gi i bài toán v i t p các d li u ñ u vào xác ñ nh v vi c gi i cùng bài toán ñó nhưng v i các giá tr ñ u vào nh hơn. Ch ng h n, bài toán tìm UCLN c a hai s a, b v i a > b có th rút g n v bài toán tìm ƯCLN c a hai s nh hơn, a mod b và b. Khi vi c rút g n như v y th c hi n ñư c thì l i gi i bài toán ban ñ u có th tìm ñư c b ng m t dãy các phép rút g n cho t i nh ng trư ng h p mà ta có th d dàng nh n ñư c l i gi i c a bài toán. Ta s th y r ng các thu t toán rút g n liên ti p bài toán ban ñ u t i bài toán có d li u ñ u vào nh hơn, ñư c áp d ng trong m t l p r t r ng các bài toán. ð nh nghĩa: M t thu t toán ñư c g i là ñ quy n u nó gi i bài toán b ng cách rút g n liên ti p bài toán ban ñ u t i bài toán cũng như v y nhưng có d li u ñ u vào nh hơn. n Thí d 10: Tìm thu t toán ñ quy tính giá tr a v i a là s th c khác không và n là s nguyên không âm. Ta xây d ng thu t toán ñ quy nh ñ nh nghĩa ñ quy c a an, ñó là an+1=a.an v i n>0 và khi n=0 thì a0=1. V y ñ tính an ta quy v các trư ng h p có s mũ n nh hơn, cho t i khi n=0. procedure power (a: s th c khác không; n: s nguyên không âm) if n = 0 then power(a,n) := 1 else power(a,n) := a * power(a,n-1) Thí d 11: Tìm thu t toán ñ quy tính UCLN c a hai s nguyên a,b không âm và a > b. procedure UCLN (a,b: các s nguyên không âm, a > b) if b = 0 then UCLN (a,b) := a else UCLN (a,b) := UCLN (a mod b, b) Thí d 12: Hãy bi u di n thu t toán tìm ki m tuy n tính như m t th t c ñ quy. ð tìm x trong dãy tìm ki m a1,a2,...,an trong bư c th i c a thu t toán ta so sánh x v i ai. N u x b ng ai thì i là v trí c n tìm, ngư c l i thì vi c tìm ki m ñư c quy v dãy có s ph n t ít hơn, c th là dãy ai+1,...,an. Thu t toán tìm ki m có d ng th t c ñ quy như sau. Cho search (i,j,x) là th t c tìm s x trong dãy ai, ai+1,..., aj. D li u ñ u vào là b ba (1,n,x). Th t c s d ng khi s h ng ñ u tiên c a dãy còn l i là x ho c là khi dãy còn l i ch có m t ph n t khác x. N u x không là s h ng ñ u tiên và còn có các s h ng khác thì l i áp d ng th t c này, nhưng dãy tìm ki m ít hơn m t ph n t nh n ñư c b ng cách xóa ñi ph n t ñ u tiên c a dãy tìm ki m bư c v a qua. 17
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p procedure search (i,j,x) if ai = x then loacation := i else if i = j then loacation := 0 else search (i+1,j,x) Thí d 13: Hãy xây d ng phiên b n ñ quy c a thu t toán tìm ki m nh phân. Gi s ta mu n ñ nh v x trong dãy a1, a2, ..., an b ng tìm ki m nh phân. Trư c tiên ta so sánh x v i s h ng gi a a[(n+1)/2]. N u chúng b ng nhau thì thu t toán k t thúc, n u không ta chuy n sang tìm ki m trong dãy ng n hơn, n a ñ u c a dãy n u x nh hơn giá tr gi a c a c a dãy xu t phát, n a sau n u ngư c l i. Như v y ta rút g n vi c gi i bài toán tìm ki m v vi c gi i cũng bài toán ñó nhưng trong dãy tìm ki m có ñ dài l n lư t gi m ñi m t n a. procedure binary search (x,i,j) m := [(i+j)/2] if x = am then loacation := m else if (x < am and i < m) then binary search (x,i,m-1) else if (x > am and j > m) then binary search (x,m+1,j) else loacation := 0 1.5.2. ð quy và l p: Thí d 14. Th t c ñ quy sau ñây cho ta giá tr c a n! v i n là s nguyên dương. procedure factorial (n: positive integer) if n = 1 then factorial(n) := 1 else factorial(n) := n * factorial(n-1) Có cách khác tính hàm giai th a c a m t s nguyên t ñ nh nghĩa ñ quy c a nó. Thay cho vi c l n lư t rút g n vi c tính toán cho các giá tr nh hơn, ta có th xu t phát t giá tr c a hàm t i 1và l n lư t áp d ng ñ nh nghĩa ñ quy ñ tìm giá tr c a hàm t i các s nguyên l n d n. ðó là th t c l p. procedure iterative factorial (n: positive integer) x := 1 for i := 1 to n x := i * x {x là n!} Thông thư ng ñ tính m t dãy các giá tr ñư c ñ nh nghĩa b ng ñ quy, n u dùng phương pháp l p thì s các phép tính s ít hơn là dùng thu t toán ñ quy (tr khi dùng các máy ñ quy chuyên d ng). Ta s xem xét bài toán tính s h ng th n c a dãy Fibonacci. procedure fibonacci (n: nguyên không âm) 18
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p if n = 0 the fibonacci(n) := 0 else if n = 1 then fibonacci(n) := 1 else fibonacci(n) := fibonacci(n - 1) + fibonacci(n - 2) Theo thu t toán này, ñ tìm fn ta bi u di n fn = fn-1 + fn-2. Sau ñó thay th c hai s này b ng t ng c a hai s Fibonacci b c th p hơn, c ti p t c như v y cho t i khi f0 và f1 xu t hi n thì ñư c thay b ng các giá tr c a chúng theo ñ nh nghĩa. Do ñó ñ tính fn c n fn+1-1 phép c ng. Bây gi ta s tính các phép toán c n dùng ñ tính fn khi s d ng phương pháp l p. Th t c này kh i t o x là f0 = 0 và y là f1 = 1. Khi vòng l p ñư c duy t qua t ng c a x và y ñư c gán cho bi n ph z. Sau ñó x ñư c gán giá tr c a y và y ñư c gán giá tr c a z. V y sau khi ñi qua vòng l p l n 1, ta có x = f1 và y = f0 + f1 = f2. Khi qua vòng l p l n n-1 thì x = fn-1. Như v y ch có n – 1 phép c ng ñư c dùng ñ tìm fn khi n > 1. procedure Iterative fibonacci (n: nguyên không âm) if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y là s Fibonacci th n} Ta ñã ch ra r ng s các phép toán dùng trong thu t toán ñ quy nhi u hơn khi dùng phương pháp l p. Tuy nhiên ñôi khi ngư i ta v n thích dùng th t c ñ quy hơn ngay c khi nó t ra kém hi u qu so v i th t c l p. ð c bi t, có nh ng bài toán ch có th gi i b ng th t c ñ quy mà không th gi i b ng th t c l p. BÀI T P CHƯƠNG I: 1. Tìm m t s nguyên n nh nh t sao cho f(x) là O(xn) ñ i v i các hàm f(x) sau: a) f(x) = 2x3 + x2log x. b) f(x) = 2x3 + (log x)4. x4 + x2 +1 c) f(x) = x3 + 1 19
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p x 5 + 5 log x d) f(x) = . x4 +1 2. Ch ng minh r ng a) x2 + 4x + 7 là O(x3), nhưng x3 không là O(x2 +4x + 17). b) xlog x là O(x2), nhưng x2 không là O(xlog x). 3. Cho m t ñánh giá big-O ñ i v i các hàm cho dư i ñây. ð i v i hàm g(x) trong ñánh giá f(x) là O(g(x)), hãy ch n hàm ñơn gi n có b c th p nh t. a) nlog(n2 + 1) + n2logn. b) (nlogn + 1)2 + (logn + 1)(n2 + 1). n 2 c) n 2 + n n . 4. Cho Hn là s ñi u hoà th n: 1 1 1 Hn = 1 + + + ... + 2 3 n Ch ng minh r ng Hn là O(logn). 5. L p m t thu t toán tính t ng t t c các s nguyên trong m t b ng. 6. L p thu t toán tính xn v i x là m t s th c và n là m t s nguyên. 7. Mô t thu t toán chèn m t s nguyên x vào v trí thích h p trong dãy các s nguyên a1, a2, ..., an x p theo th t tăng d n. 8. Tìm thu t toán xác ñ nh v trí g p ñ u tiên c a ph n t l n nh t trong b ng li t kê các s nguyên, trong ñó các s này không nh t thi t ph i khác nhau. 9. Tìm thu t toán xác ñ nh v trí g p cu i cùng c a ph n t nh nh t trong b ng li t kê các s nguyên, trong ñó các s này không nh t thi t ph i khác nhau. 10. Mô t thu t toán ñ m s các s 1 trong m t xâu bit b ng cách ki m tra m i bit c a xâu ñ xác ñ nh nó có là bit 1 hay không. 11. Thu t toán tìm ki m tam phân. Xác ñ nh v trí c a m t ph n t trong m t b ng li t kê các s nguyên theo th t tăng d n b ng cách tách liên ti p b ng li t kê ñó thành ba b ng li t kê con có kích thư c b ng nhau (ho c g n b ng nhau nh t có th ñư c) và gi i h n vi c tìm ki m trong m t b ng li t kê con thích h p. Hãy ch rõ các bư c c a thu t toán ñó. 12. L p thu t toán tìm trong m t dãy các s nguyên s h ng ñ u tiên b ng m t s h ng nào ñó ñ ng trư c nó trong dãy. 20
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 13. L p thu t toán tìm trong m t dãy các s nguyên t t c các s h ng l n hơn t ng t t c các s h ng ñ ng trư c nó trong dãy. 14. Cho ñánh giá big-O ñ i v i s các phép so sánh ñư c dùng b i thu t toán trong Bài t p 10. 15. ðánh giá ñ ph c t p c a thu t toán tìm ki m tam phân ñư c cho trong Bài t p 11. 16. ðánh giá ñ ph c t p c a thu t toán trong Bài t p 12. 17. Mô t thu t toán tính hi u c a hai khai tri n nh phân. 18. L p m t thu t toán ñ xác ñ nh a > b, a = b hay a < b ñ i v i hai s nguyên a và b d ng khai tri n nh phân. 19. ðánh giá ñ ph c t p c a thu t toán tìm khai tri n theo cơ s b c a s nguyên n qua s các phép chia ñư c dùng. 20. Hãy cho thu t toán ñ quy tìm t ng n s nguyên dương l ñ u tiên. 21. Hãy cho thu t toán ñ quy tìm s c c ñ i c a t p h u h n các s nguyên. 22. Mô t thu t toán ñ quy tìm xn mod m v i n, x, m là các s nguyên dương. n 23. Hãy nghĩ ra thu t toán ñ quy tính a 2 trong ñó a là m t s th c và n là m t s nguyên dương. 24. Hãy nghĩ ra thu t toán ñ quy tìm s h ng th n c a dãy ñư c xác ñ nh như sau: a0=1, a1 = 2 và an = an-1 an-2 v i n = 2, 3, 4, ... 25. Thu t toán ñ quy hay thu t toán l p tìm s h ng th n c a dãy trong Bài t p 24 là có hi u qu hơn? 21

CÓ THỂ BẠN MUỐN DOWNLOAD