Giáo trình Toán rời rạc - Đại học Huế

Nội dung text: Giáo trình Toán rời rạc - Đại học Huế

1. Nu 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 f 1(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 mi 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 n 0 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 mt th k nay. Trong tin hc, 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à n 2. Ta có: 2 n(n + )3 2 n(n + )3 2 f(n)= =O(n ) vì ≤ n v i m i n ≥3 (C=1, n 0=3). 2 2 k k-1 k Mt cách t ng quát, n u f(n)=a kn +a k-1n + +a 1n+a 0 thì f(n)=O(n ). Th t v y, vi n>1, k k-1 k k-1 k |f(n)|| ≤ |a k|n +|a k-1|n + +|a 1|n+|a 0| = n (|ak|+|a k-1|/n+ +|a 1|/n +a 0/n ) k ≤ n (|a k|+|a k-1|+ +|a 1|+a 0). Đ i u này ch ng t |f(n)| ≤ Cn k v i m i n>1. Cho g(n)=3n+5nlog 2n, ta có g(n)=O(nlog 2n). Th t v y, 3n+5nlog 2n = n(3+5log 2n) ≤ n(log 2n+5log 2n) = 6nlog 2n v i m i n ≥8 (C=6, n 0=8). Mnh đ : Cho f 1(n)=O(g 1(n)) và f 2(n) là O(g 2(n)). Khi đ ó (f 1 + f 2)(n) = O(max(|g 1(n)|,|g 2(n)|), (f 1f2)(n) = O(g 1(n)g 2(n)). Ch ng minh. Theo gi thi t, t n t i C 1, C 2, n 1, n 2 sao cho |f 1(n)| ≤ C 1|g 1(n)| và |f 2(n)| ≤ C 2|g 2(n)| v i m i n > n 1 và m i n > n 2. Do đ ó |(f 1 + f 2)(n)| = |f 1(n) + f 2(n)| ≤ |f 1(n)| + |f 2(n)| ≤ C 1|g 1(n)| + C 2|g 2(n)| ≤ (C 1+C 2)g(n) vi m i n > n 0=max(n 1,n 2), đ âyC=C 1+C 2 và g(n)=max(|g 1(n)| , |g 2(n)|). |(f 1f2)(n)| = |f 1(n)||f 2(n)| ≤ C 1|g 1(n)|C 2|g 2(n)| ≤ C 1C2|(g 1g2)(n)| v i mi n > n 0=max(n 1,n 2). 10
2. Đnh ngh ĩa 2: Nu 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)). Nu 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(g 1(n)), thu t toán 2 có đ ph c tp O(g 2(n)), mà g 1(n) có c p th p h ơn g 2(n), thì ta nói rng 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 na làm ngoài vòng lp. Do đ ó, n u x=a i, 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: k Đ đ ơn gi n, ta gi s r ng có n=2 ph n t trong b ng li t kê a 1,a 2, ,a n, 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 2 k+1 ph n t , trong đ ó k là s nguyên nh nh t sao cho n < 2 k+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 ca 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=2log 2n+ 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à k+1 lũy th a c a 2, b ng g c s đ ưc m r ng t i b ng có 2 ph n t , v i k=[log 2n] và s tìm ki m đ òi h i ph i th c hi n nhi u nh t 2[log 2n]+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(log 2n). 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 mt 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 trng khác làm gi m th i gian c n thi t đ gi i m t 11
3. 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 O(n b) Đ ph c t p đ a th c O(b n) (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 ca 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 10 2 7.10 -9 s 10 -7 s 7.10 -7 s 10 -5 s 4.10 13 n ă m * 10 3 1,0.10 -8 s 10 -6 s 1.10 -5 s 10 -3 s * * 10 4 1,3.10 -8 s 10 -5 s 1.10 -4 s 10 -1 s * * 10 5 1,7.10 -8 s 10 -4 s 2.10 -3 s 10 s * * 10 6 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. Mnh đ 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
4. 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. Mnh đ 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 r 0 = a và r 1 = b. B ng cách áp dng liên ti p thu t toán chia, ta tìm đưc: r0 = r 1q1 + r 2 0 ≤ r 2 r 1 > r 2 > ≥ 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(r 0,r 1) = UCLN(r 1,r 2) = = UCLN(r n-2, r n-1) = UCLN(r n-1,r n) = r n. 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 lp 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
5. 1.4.2. Bi u di n các s nguyên: Mnh đ 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: k k-1 n = a kb + a k-1b + + a 1b + a 0. đ ây k là m t s t nhiên, a 0, a 1, , a k là các s t nhiên nh h ơn b và a k ≠ 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à (a kak-1 a 1a0)b. Bây gi ta s mô t thu t toán xây d ng khai tri n c ơ s b ca 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 = bq 0 + a 0, 0 ≤ a 0 < b. S d ư a 0 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 q 0 cho b, ta đ ưc: q0 = bq 1 + a 1, 0 ≤ a 1 < b. S d ư a 1 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
6. đ â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 = (a n-1an-2 a 1 a0)2 và b = (b n-1 b n-2 b 1 b 0)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 + b 0 = c 0.2 + s 0. đ ây s 0 là bit ph i cùng trong khai tri n nh phân c a a+b, c 0 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 + b 1 + c 0 = c 1.2 + s 1. đ ây s 1 là bit ti p theo (tính t bên ph i) trong khai tri n nh phân c a a+b và c 1 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 tng a+b. giai đ o n cu i cùng, c ng a n-1, b n-1 và c n-2 đ nh n đ ưc c n-1.2+s n-1. Bit đ ng đu c a t ng là s n=c n-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 = (s n s n-1 s n-2 s 1 s 0)2. Thí d 8: Tìm t ng c a a = (11011) 2 và b = (10110) 2. a0 + b 0 = 1 + 0 = 0.2 + 1 (c 0 = 0, s 0 = 1), a 1 + b 1 + c 0 = 1 + 1 + 0 = 1.2 + 0 (c 1 = 1, s1 = 0), a 2 + b 2 +c 1 = 0 + 1 + 1 = 1.2 + 0 (c 2 = 1, s 2 = 0), a 3 + b 3 + c 2 = 1 + 0 + 1 = 1.2 + 0 (c 3 = 1, s 3 = 0), a 4 + b 4 +c 3 = 1 + 1 + 1 = 1.2 + 1 (s 5 = c 4 =1, s 4 = 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 cng (a,b: positive integers) c := 0 for j := 0 to n-1 begin + + a j bj c d :=    2  sj := a j + b j + c − 2d c := d end sn := c {khai tri n nh phân c a t ng là (s n s n-1 s 1 s0) 2 } 15
7. Tng 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 j j ab = a ∑b j 2 = ∑ a(b j 2 ). 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 ab j=a n u bj=1 và ab j=0 n u b j=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 ca 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 j ca nó. Do đ ó, ta có th nh n đ ưc (ab j)2 b ng cách d ch khai tri n nh phân c a ab j đ 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, j ta s nh n đ ưc tích ab b ng cách c ng n s nguyên ab j.2 v i j=0, 1, , n-1. Thí d 9: Tìm tích c a a = (110) 2 và b = (101) 2. 0 0 1 1 2 Ta có ab 0.2 = (110) 2.1.2 = (110) 2, ab 1.2 = (110) 2.0.2 = (0000) 2, ab 2.2 = 2 (110) 2.1.2 = (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 b j = 1 then cj := a đ ưc d ch đ i j ch else c j := 0 end {c 0, c 1, , c n-1 là các tích riêng ph n} p := 0 for j := 0 to n-1 p := p + c j {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 c 0, c 1, c 2, , c n-1. Khi b j=1, ta tính tích riêng ph n c j b ng cách d ch khai tri n nh phân c a a đ i j bit. Khi b j=0 thì không c n có d ch chuy n nào vì c j=0. Do đ ó, đ tìm t t j c n s nguyên ab j.2 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(n 2). 16
8. Đ c ng các s nguyên ab j t j=0 đ n n −1, đ òi h i ph i c ng m t s nguyên n bit, mt 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(n 2). 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 lp r t r ng các bài toán. Đnh ngh ĩa: Mt 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. Thí d 10: Tìm thu t toán đ quy tính giá tr a n 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 a n, đ ó là a n+1 =a.a n v i n>0 và khi n=0 thì a 0=1. V y đ tính a n 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 a 1,a 2, ,a n trong b ưc th i c a thu t toán ta so sánh x v i a i. N u x b ng a i 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 a i+1 , ,a n. 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 a i, a i+1 , , a j. 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 li 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
9. 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 a 1, a 2, , a n 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, nu 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 nu 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 = a m then loacation := m else if (x a m 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