Giáo trình Toán rời rạc - Vũ Kim Thành

pdf

222 trang huongle 4000

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Vũ Kim Thành", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_roi_rac_vu_kim_thanh.pdf

Nội dung text: Giáo trình Toán rời rạc - Vũ Kim Thành

B GIÁO D C VÀ ðÀO T O TR ƯNG ðI H C NƠNG NGHI P HÀ N I VŨ KIM THÀNH TỐN R I R C (Giáo trình dành cho sinh viên ngành cơng ngh thơng tin) Hà ni 2008 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 0
MC L C 5 Li nĩi đ u Ch ng 1. THU T TỐN 7 1. ðnh ngh ĩa 7 2. Mơ t thu t tốn b ng l ưu đ 8 3. Mơ t thu t tốn b ng ngơn ng ph ng Pascal 9 4. ð ph c t p c a thu t tốn 14 5. Thu t tốn tìm ki m 18 6. Thu t tốn đ quy 19 7. M t s thu t tốn v s nguyên 23 BÀI T P CH ƯƠ NG 1 28 Ch ng 2. BÀI TỐN ðM 32 1. Nguyên lý cng và nguyên lý nhân 32 2. Ch nh h p.Hố n v . T hp. 35 3. Nguyên lý bù tr 42 4. Gi i cá c h th c truy h i 44 5. Bà i tố n li t kê. 51 6. B àitố n t n t i 61 BÀI T P CH ƯƠ NG 2 64 Ch ng 3. CÁC KHÁI NI M C Ơ B N V ð TH 69 1. Các đnh ngh ĩa v đ th và bi u di n hình h c c a đ th 69 2. Bi u di n đ th b ng đ i s 79 3. S đ ng c u c a các đ th 82 4. Tính liên thơng trong đ th 84 5. S n đnh trong, s n đnh ngồ i và nhân c a đth 88 6. Sc s c a đth 91 BÀI T P CH ƯƠ NG 3 93 Ch ng 4. ð TH EULER, ð TH HAMILTON, ð TH PH NG 98 1. ðth Euler 98 2. ðth Hamilton 103 3. ð thi ph ng 108 BÀI T P CH ƯƠ NG 4 113 Ch ng 5. CÂY VÀ M T S NG D NG C A CÂY 117 1. Cây vàcá c tí nh ch t c ơ b n c a cây 118 2. Cây nh phân và phép duy t cây 122 3. M t vài ng dng c a cây 126 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 1
4. Cây khung (cây bao trù m) c a đth 131 5. H chu trì nh đc l p 134 6. Cây khung nh nh t 136 BÀI T P CH ƯƠ NG 5 142 Ch ng 6. M T S BÀI TỐN T I ƯU TRÊN ð TH 147 1. Bài tốn đưng đi ng n nh t trong đ th 147 2. Tâm, Bá n kí nh, ðư ng kí nh c a đth 152 3. Mng và Lu ng 153 4. Bài tốn du l ch 160 BÀI T P CH ƯƠ NG 6 166 Ch ng 7. ðI S BOOLE 172 1. Hà m Boole 172 2. Bi u th c Boole 174 3. ðnh nghĩ a đi s Boole theo tiên đ 176 4. Bi u di n cá c hà m Boole 177 5. Các c ng logic 183 6 Ti thi u hốhà m Boole 185 BÀI T P CH ƯƠ NG 7 193 Ph ch ng. ðI C ƯƠ NG V TỐN LOGIC 197 1. Lơgic m nh đ 197 2. Cơng th c đ ng nh t đúng và cơng th c đ ng nh t b ng nhau trong lơgic m nh đ 201 3. ðiu ki n đng nh t đúng trong lơgic m nh đ 205 4. Lơgic v t 208 BÀI T P PH CH ƯƠ NG 213 Mt s bài t p làm trên máy tính 216 Mt s thu t ng dùng trong giáo trình 218 Tài li u tham kh o 221 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 2
LI NĨI ð U Tốn R i r c (Discrete mathematics) là mơn tốn h c nghiên c u các đ i t ưng r i rc. Nĩ đưc ng d ng trong nhi u ngành khoa h c khác nhau, đ c bi t là trong tin h c bi quá trình x lý thơng tin trên máy tính th c ch t là m t quá trình r i r c. Ph m vi nghiên c u c a Tốn R i r c r t r ng, cĩ th chia thành các mơn h c khác nhau. Theo quy đnh c a ch ươ ng trình mơn h c, giáo trình này đ c p đ n các l ĩnh v c: Thu t tốn và bài tốn đm; Lý thuy t đ th ; ði s Logic và đưc chia thành 8 ch ươ ng: - Ch ươ ng 1 đ c p đ n m t trong các v n đ c ơ b n nh t c a Thu t tốn đĩ là đ ph c t p v th i gian c a thu t tốn. - Ch ươ ng 2 nĩi v các nguyên lý c ơ b n c a Bài tốn đm. - Các ch ươ ng 3, 4, 5 và 6 trình bày v Lý thuy t đ th và các ng d ng. ðây là ph n chi m t tr ng nhi u nh t c a giáo trình. Trong đĩ cĩ các ch ươ ng v các khái ni m c ơ bn c a đ th , các đ th đ c bi t nh ư đ th Euler, đ th Hamilton, đ th ph ng, Cây cùng các ng d ng ca các đ thi đ c bi t này. Riêng ch ươ ng 6 dành cho m t v n đ tr ng là m t s bài tốn t i ưu trên đ th ho c bài tốn t i ưu đưc gi i b ng cách ng dng lý thuy t đ th . - Ch ươ ng 7 là các ki n th c c ơ b n v ði s Boole, m t cơng c h u hi u trong vi c thi t k các m ch đin, đin t . Cu i giáo trình là ph ch ươ ng: Nh ng khái ni m c ơ b n v tốn Logic đ ng ưi hc cĩ th t nghiên c u thêm v Tốn Logic. Trong m i ch ươ ng chúng tơi c g ng trình bày các ki n th c c ơ b n nh t c a ch ươ ng đĩ cùng các thí d minh h a c th . Vì khuơn kh s ti t h c nên chúng tơi lưc b mt s ch ng minh ph c t p. Cu i m i ch ươ ng đu cĩ các bài t p đ ng ưi h c ng d ng, ki m ch ng các lý thuy t đã h c, đ ng th i c ũng cung c p m t s đáp s c a các bài t p đã cho. Cũng c n nĩi thêm r ng tốn R i rc khơng ch đưc ng d ng trong tin h c mà cịn đưc ng d ng trong nhi u ngành khoa h c khác. B i v y giáo trình c ũng cĩ ích cho nh ng ai c n quan tâm đ n các ng d ng khác c a mơn h c này. Tác gi xin chân thành c m ơn các b n đ ng nghi p đã đng viên và gĩp ý cho vi c biên so n giáo trình này. ðc bi t chúng tơi xin c m ơn Nhà giáo ưu tú Nguy n ðình Hi n đã hi u đính và cho nhi u ý ki n đĩng gĩp b ích và thi t th c. Vì trình đ cĩ h n và giáo trình đưc biên so n l n đ u nên khơng tránh kh i các thi u sĩt. Tác gi r t mong nh n đưc các ý ki n đĩng gĩp c a các đ ng nghi p và b n đc v các khi m khuy t c a cu n sách. TÁC GI Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 3
CHƯƠ NG1. THU T TỐN 1. ðnh ngh ĩa. 2. Mơ t thu t tốn b ng l ưu đ. 3. Mơ t thu t tốn b ng ngơn ng ph ng Pascal. 3.1. Câu l nh Procedure (th t c) ho c Function (hàm). 3.2. Câu l nh gán. 3.3. Kh i câu l nh tu n t . 3.4. Câu l nh di u ki n. 3.5. Các câu l nh l p. 4. ð ph c t p c a thu t tốn. 4.1. Khái ni m đ t ăng c a hàm. 4.2. ð t ăng c a t h p các hàm. 4.3. ð ph c t p c a thu t tốn. 5. Thu t tốn tìm ki m 5.1. Thu t tốn tìm ki m tuy n tính (cịn g i là thu t tốn tìm ki m tu n t ). 5.2. Thu t tốn tìm ki m nh phân. 6. Thu t tốn đ quy. 6.1. Cơng th c truy h i. 6.2. Thu t tốn đ quy. 6.3. ð quy và l p 7. M t s thu t tốn v s nguyên. 7.1. Bi u di n các s nguyên. 7.2. C ng và nhân trong h nh phân. 1. ðnh ngh ĩa Thu t tốn (algorithm) là m t dãy các quy t c nh m xác đ nh m t dãy các thao tác trên các đi t ưng sao cho sau m t s h u hn bưc th c hi n s đt đưc mc tiêu đt ra. T đ nh ngh ĩa c a thu t tốn cho th y các đ c tr ưng (tính ch t) c ơ b n c a thu t tốn là: a. Y u t vào, ra: • ðu vào (Input): M i thu t tốn cĩ m t giá tr ho c m t b giá tr đ u vào t m t t p xác đ nh đã đưc ch rõ. • ðu ra (Output): T các giá tr đ u vào, thu t tốn cho ra các giá tr c n tìm g i là k t qu c a bài tốn. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 4
b. Tính d ng: Sau m t s h u h n b ưc thao tác thu t tốn ph i k t thúc và cho k t qu . c. Tính xác đnh: Các thao tác ph i rõ ràng, cho cùng m t k t qu dù đưc x lý trên các b x lý khác nhau (hai b x lý trong cùng m t điu ki n khơng th cho hai k t qu khác nhau). d. Tính hi u qu Sau khi đư a d li u vào cho thu t tốn ho t đ ng ph i đưa ra k t qu nh ư ý mu n. e. Tính t ng quát Thu t tốn ph i đưc áp d ng cho m i bài tốn cùng d ng ch khơng ph i ch cho mt t p đ c bi t các giá tr đ u vào. Cĩ nhi u cách mơ t thu t tốn nh ư: Dùng ngơn ng t nhiên; dùng l ưu đ (s ơ đ kh i); dùng m t ngơn ng l p trình nào đĩ (trong giáo trình này dùng lo i ngơn ng mơ t gn nh ư ngơn ng l p trình Pascal và g i là ph ng Pascal); 2. Mơ t thu t tốn b ng l ưu đ Sau khi cĩ thu t tốn đ gi i bài tốn, tr ưc khi chuy n sang ngơn ng l p trình, ng ưi ta th ưng ph i th hi n thu t tốn d ưi d ng s ơ đ. S ơ đ đĩ g i là l ưu đ c a thu t tốn. Các ký hi u quy ưc dùng trong l ưu đ đưc trình bày trong b ng 1. Bng 1. Các ký hi u quy ưc dung trong l ưu đ thu t tốn Tên ký hi u Ký hi u Vai trị ca ký hi u Kh i m đ u Dùng đ m đ u ho c k t thúc ho c k t thúc thu t tốn Kh i vào ra ðư a d li u vào và in k t qu Kh i tính tốn Bi u di n các cơng th c tính tốn và thay đi giá tr các đ i t ưng Kh i điu ki n Ki m tra các điu ki n phân nhánh Ch ươ ng trình con Gi các ch ươ ng trình con Hưng đi c a Hưng chuy n thơng tin, liên h thu t tốn gi a các kh i Thí d : Thu t tốn gi i ph ươ ng trình b c hai ax 2 + bx + c = 0 g m các b ưc sau: 1) Xác đnh các h s a, b, c (thơng tin đu vào) 2) Ki m tra h s a: c - N u a = 0: Ph ươ ng trình đã cho là ph ươ ng trình b c nh t, nghi m là: x = − . b - N u a ≠ 0: Chuy n sang b ưc 3. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 5
3) Tính bi t th c ∆ = b 2 – 4ac. 4) Ki m tra d u c a bi t th c ∆ - Nu ∆ ≥ 0: Ph ươ ng trình cĩ nghi m th c - N u ∆ < 0: Ph ươ ng trình cĩ nghi m ph c 5) In k t qu Lưu đ c a thu t tốn đưc trình bày trong hình 1 B t đu Nh p a, b, c Sai a = 0 ðúng 2 c ∆ = b = 4ac x = − b Sai ∆ ≥ 0 ðúng b − b + Ph n th c = − x1 = 2a 2a − − b + Ph n o = x = 2a 2 2a Thơng báo k t qu K t thúc Hình 1. L ưu đ gi i ph ươ ng trình b c hai 3. Mơ t thu t tốn b ng ngơn ng ph ng Pascal ð gi i bài tốn trên máy tính đin t ph i vi t ch ươ ng trình theo m t ngơn ng l p trình nào đĩ (Pascal, C, Basic, ). M i ngơn ng l p trình cĩ m t quy t c c u trúc riêng. ð thay vi c mơ t thu t tốn b ng l i, cĩ th mơ t thu t tốn b ng các c u trúc l nh tươ ng t nh ư ngơn ng l p trình Pascal và g i là ngơn ng ph ng Pascal. Các câu l nh chính dùng đ mơ t thu t tốn g m cĩ: Procedure ho c Function; câu lnh gán; các câu l nh điu ki n; các vịng l p. Ngồi ra khi c n gi i thích các câu l nh bng l i, cĩ th đ các l i gi i thích trong d u (* *) ho c { }. Ngh ĩa là ngơn ng ph ng Pascal hồn tồn t ươ ng t ngơn ng l p trình Pascal, nh ưng khơng cĩ ph n khai báo. Tuy nhiên, ph i nêu rõ đu vào (Input) và đu ra (output) c a thu t tốn. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 6
3.1. Câu l nh Procedure (th t c) ho c Function (hàm) ðng ngay sau câu l nh này là tên c a th t c ho ăc tên hàm. Các b ưc th c hi n c a thu t tốn đưc mơ t trong th t c (hàm) đưc b t đ u b i t khĩa begin và k t thúc b i t khĩa end. Thí d 1 Function Max(a, b, c) (* Hàm tìm s l n nh t trong 3 s a, b, c *) Begin (* thân hàm*) End; Thí d 2 Procedure Giai_phuong_trình_bac_hai (* Th t c gi i ph ươ ng trình b c hai *) Begin (* thân th t c *) End; Chú ý r ng, khi mơ t thu t tốn b ng function, tr ưc khi k t thúc (end) thu t tốn ph i tr v (ghi nh n) giá tr c a function đĩ. 3.2. Câu l nh gán Dùng đ gán giá tr cho các bi n. Cách vi t: Tên bi n := giá tr gán Thí d : x := a; (*bi n x đưc gán giá tr a*) max := b; (*bi n max đưc gán giá tr b*) 3.3. Kh i câu l nh tu n t ðưc m đ u b ng t khĩa begin và k t thúc b ng end nh ư sau: begin Câu l nh 1; Câu l nh 2; Câu l nh n; end; Các l nh đưc th c hi n tu n t t câu l nh th nh t đ n câu l nh cu i cùng. 3.4. Câu l nh điu ki n Cĩ hai d ng: d ng đơn gi n và d ng l a ch n. a. D ng đơn gi n: Cách vi t: if then câu l nh ho c kh i câu l nh; Khi th c hi n, điu ki n đưc ki m tra, n u điu ki n th a mãn thì câu l nh (kh i câu lnh) đưc th c hi n, n u điu ki n khơng th a mãn thì l nh b b qua. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 7
b. D ng l a ch n: Cách vi t: if then câu l nh ho c kh i câu l nh 1 else câu l nh ho c kh i câu l nh 2; Khi th c hi n, điu ki n đưc ki m tra, n u điu ki n th a mãn thì câu l nh (kh i câu lnh) 1 đưc th c hi n, n u điu ki n khơng đưc th a mãn thì câu l nh (kh i câu l nh) 2 đưc th c hi n. Thí d 1. Thu t tốn tìm s l n nh t trong 3 s th c a, b, c. - ðu tiên cho max = a; - So sánh max v i b, n u b > max thì max = b; - So sánh max v i c, n u c > max thì max = c. Function max(a,b,c) Input: 3 s th c a,b,c; Output: S l n nh t trong 3 s đã nh p; Begin x := a; if b > x then x:= b; if c > x then x:= c; max := x; End; Thí d 2. Thu t tốn gi i ph ươ ng trình b c hai ax 2 + bx + c = 0 Procedure Giai_phuong_trinh_bac2; Input: Các h s a, b, c; Output: Nghi m c a ph ươ ng trình; begin if a = 0 then x := -c/b; if a ≠ 0 then begin ∆ := b 2 – 4ac; if ∆ ≥ 0 then begin x 1 = (– b – ∆ )/2a ; x 2 = (– b + ∆ )/2a; end else begin Ph n th c := -b/2a; Ph n o := ( − ∆ )/2a; end; end; end; Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 8
3.5. Các câu l nh l p Cĩ hai lo i: Lo i cĩ b ưc l p xác đnh và lo i cĩ b ưc l p khơng xác đ nh. a. Lo i cĩ b ưc l p xác đ nh: Cách vi t nh ư sau: for bi n điu khi n := giá tr đ u to giá tr cu i do câu l nh ho c kh i câu l nh; Khi th c hi n, bi n điu khi n đưc ki m tra, n u bi n điu khi n nh h ơn ho c b ng giá tr cu i thì câu l nh (kh i câu l nh) đưc th c hi n. Ti p đĩ bi n điu khi n s t ăng thêm 1 đơ n v và quá trình đưc l p l i cho đ n khi bi n điu khi n l n h ơn giá tr cu i thì vịng l p d ng và cho k t qu . Nh ư v y h t vịng l p for s b ưc l p là giá tr cu i (c a bi n điu khi n) tr giá tr đ u c ng m t. Thí d : Tìm giá tr l n nh t c a dãy s a 1, a 2, ,a n. Thu t tốn: ð u tiên cho giá tr l n nh t (max) b ng a 1, sau đĩ l n l ưt so sánh max vi các s a i (i = 2, 3, , n), n u max a i thì max khơng đi. Function max_day_so; Input: Dãy s a 1, a 2, ,a n; Output: Giá tr l n nh t (max) c a dãy s đã nh p; begin max := a 1 ; for i:= 2 to n do if a i > max then max := a i ; max_day_so := max; end; Chú thích: Vịng l p for cịn cách vi t lùi bi n điu khi n nh ư sau: for bi n điu khi n := giá tr cu i downto giá tr đ u do câu l nh ho c kh i câu l nh; Vic th c hi n câu l nh này t ươ ng t nh ư khi vi t bi n điu khi n t ăng d n. b. Lo i cĩ b ưc l p khơng xác đ nh: Cĩ hai cách vi t Cách th nh t: while điu ki n do câu l nh ho c kh i câu l nh; Khi th c hi n, điu ki n đưc ki m tra, n u điu kin đưc tho mãn thì câu l nh (kh i câu l nh) đưc th c hi n. N u điu ki n khơng tho mãn thì vịng l p d ng và cho kt qu . Thí d : Ki m tra xem s nguyên d ươ ng m đã cho cĩ ph i là s nguyên t khơng? Thu t tốn nh ư sau: S m là s nguyên t n u nĩ khơng chia h t cho b t c s nguyên dươ ng khác 1 nào nh h ơn ho c b ng m . Th t v y, n u m là m t h p s (khơng ph i là s nguyên t ), ngh ĩa là t n t i các s nguyên d ươ ng a, b sao cho: m = a.b ⇒ a ≤ m ho c b ≤ m Vy, n u m là s nguyên t thì m khơng chia h t cho m i s nguyên d ươ ng i, 2 ≤ i ≤ m Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 9
Procedure nguyento(m); Input: S nguyên d ươ ng m; Output: True, n u m là s nguyên t ; False, n u m khơng ph i là s nguyên t ; begin i := 2; while i ≤ m do begin if m mod i = 0 then nguyento := false else nguyento := true; i := i+1; end; end; Cách th hai: repeat câu l nh ho c kh i câu l nh until điu ki n; Khi th c hi n, câu l nh (kh i câu l nh) đưc th c hi n, sau đĩ điu ki n đưc ki m tra, n u điu ki n sai thì vịng l p đưc th c hi n, n u điu ki n đúng thì vịng l p d ng và cho k t qu . Thí d : Thu t tốn Ơ-clit tìm ưc s chung l n nh t c a hai s nguyên d ươ ng a, b nh ư sau: Gi s a > b và a chia cho b đưc th ươ ng là q và s d ư là r, trong đĩ a, b, q, r là các s nguyên d ươ ng: a = bq + r suy ra: ƯCLN(a, b) = ƯCLN(b, r) và s d ư cu i cùng khác khơng là ưc s chung l n nh t c a a và b. Th t v y: Gi s d là ưc s chung c a hai s nguyên d ươ ng a và b, khi đĩ: r = a – bq chia h t cho d. V y d là ưc chung c a b và r. Ng ưc l i, n u d là ưc s chung c a b và r, khi đĩ do bq + r = a c ũng chia h t cho d. Vy d là ưc s chung c a a và b. Ch ng h n, mu n tìm ưc s chung l n nh t c a 111 và 201 ta làm nh ư sau: 201 = 1. 111 + 90 111 = 1. 90 + 21 90 = 4. 21 + 6 21 = 3. 6 + 3 6 = 2. 3 Vy ƯCLN(111, 201) = 3 (3 là s d ư cu i cùng khác 0). Function UCLN(a, b) Input: a, b là 2 s nguyên d ươ ng; Output: UCLN(a, b); begin Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 10
x := a; y : = b; repeat begin r := x mod y; (* r là ph n d ư khi chia x cho y *) x : = y; y := r ; if y ≠ 0 then uc := y; end; until y = 0; UCLN := uc; end ; Chú ý: Khi gi i các bài tốn ph c t p thì th ưng ph i phân chia bài tốn đĩ thành các bài tốn nh h ơn g i là các bài tốn con. Khi đĩ ph i xây d ng các th t c ho c hàm đ gi i các bài tốn con đĩ, sau đĩ t p h p các bài tốn con này đ gi i bài tốn ban đu đã đt ra. Thu t ng tin h c g i các ch ươ ng trình gi i bài tốn con đĩ là các ch ươ ng trình con. Thí d : Tìm s nguyên t nh nh t l n h ơn s nguyên d ươ ng m đã cho. Procedure So_nguyen_to_lon_hon(m); Input: S nguyên d ươ ng m; Output: n là s nguyên t nh nh t l n h ơn m; begin n := m + 1; while nguyento(n) = false do n := n + 1; end; 4. ð ph c t p c a thu t tốn Cĩ hai lý do làm cho m t thu t tốn đúng cĩ th khơng th c hi n đưc trên máy tính. ðĩ là do máy tính khơng đ b nh đ th c hi n ho c th i gian tính tốn quá dài. T ươ ng ng v i hai lý do trên ng ưi ta đưa ra hai khái ni m: - ð ph c t p khơng gian c a thu t tốn, đ ph c t p này g n li n v i các c u trúc d li u đưc s d ng. V n đ này khơng thu c ph m vi c a mơn h c này. - ð ph c t p th i gian c a thu t tốn, đ ph c t p này đưc th hi n qua s l ưng các câu l nh v các phép gán, các phép tính s h c, phép so sánh, đưc s d ng trong thu t tốn khi các giá tr đ u vào cĩ kích th ưc đã cho. 4.1. Khái ni m đ t ăng c a hàm Tr ưc h t xét thí d : Gi s th i gian tính tốn c a m t thu t tốn ph thu c vào kích th ưc n c a đ u vào theo cơng th c: t(n) = 60n 2 + 9n + 9 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 11
Bng sau cho th y khi n l n, t(n) x p x s h ng 60n 2 : n t(n) = 60n 2 + 9n + 9 60n 2 10 9099 6000 100 600 909 600 000 1 000 60 009 009 60 000 000 10 000 6 000 090 009 6 000 000 000 ðnh ngh ĩa: Cho f(x) và g(x) là hai hàm t t p s nguyên hoc t p s th c vào t p các s th c. Ng ưi ta nĩi f(x) là O(g(x)) hay f(x) cĩ quan h big-O v i g(x), ký hi u f(x) = O(g(x)), n u t n t i hai h ng s C và k sao cho: | f(x) | ≤ C. | g(x) |, ∀x ≥ k. Thí d 1. t(n) = 60n 2 + 9n + 9 = O(n 2) Th t v y: ∀n ≥ 1, ta cĩ: | 60n 2 + 9n +9| = 60n 2 + 9n +9  9 9  = n2 60 + +   n n2  ≤ n 2 (60 + 9 + 9) = 78n 2. V y C = 78; k = 1. T ươ ng t ta cĩ th ch ng minh: n n-1 n Pn(x) = a 0x + a 1x + + a n = O(x ) , x ∈ R. Thí d 2. f(n) = 1 + 2 + 3 + + n k 1 | f 2(x)| ≤ C2 | g 2(x)) | , ∀x > k 2 Ch n k = max(k 1; k 2) thì c hai b t đ ng th c đ u tho mãn. Do đĩ: 1) |(f 1 + f 2)(x)| = |f 1(x) + f 2(x)| ≤ |f 1(x)| + |f 2(x)| ≤ ≤ C 1|g 1(x)| + C 2|g 2(x)| ≤ (C 1 + C 2)g(x) đây g(x) = max{|g 1(x)|, |g 2(x)|}. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 12
2) |(f 1.f 2)(x)| = |f 1(x)|.|f 2(x)| ≤ C 1C2 |g 1(x)|.|g 2(x)| = C 1C2|g 1(x)g 2(x)| H qu : N u f 1(x) = O(g(x)), f 2(x) = O(g(x)) thì (f 1+f 2)(x) = O(g(x)) Thí d . Cho đánh giá O c a các hàm: 3 1/ f(n) = 2nlg(n!) + (n + 3)lgn , n ∈ N. 2/ f(x) = (x + 1)lg(x 2 + 1) + 3x 2 , x ∈ R. Gi i: 1) Ta cĩ: lg(n!) = O(nlgn) ⇒ 2nlg(n!) = O(n 2lgn) (n 3 + 3)lgn = O(n 3lgn) V y f(n) = O(n 3lgn) 2) Ta cĩ: lg(x 2 + 1) ≤ lg2x 2 = lg2 + 2lgx ≤ 3lgx , ∀x > 1 ⇒ lg(x 2 + 1) = O(lgx) ⇒ (x + 1)lg(x 2 + 1) = O(xlgx) Mt khác: 3x 2 = O(x 2) và max{xlgx; x 2} = x 2. Vy f(x) = O(x 2). 4.3. ð ph c t p c a thu t tốn Nh ư đã nĩi ph n đ u c a m c 4, chúng ta ch đ c p đ n đ ph c t p v th i gian ca thu t tốn. ð ph c t p v th i gian c a thu t tốn đưc đánh giá qua s l ưng các phép tốn mà thu t tốn s d ng. Vì v y ph i đ m các phép tốn cĩ trong thu t tốn. Các phép tốn ph i đ m là: - Các phép so sánh các s nguyên ho c s th c; - Các phép tính s h c: c ng, tr , nhân, chia; - Các phép gán; - Và b t k ỳ m t phép tính s ơ c p nào khác xu t hi n trong quá trình tính tốn. Gi s s các phép tốn c a thu t tốn là f(n), trong đĩ n là kích th ưc đ u vào, khi đĩ ng ưi ta th ưng quy đ ph c t p v th i gian c a thu t tốn v các m c: • ð ph c t p O(1), g i là đ ph c t p h ng s , n u f(n) = O(1). • ð ph c t p O(logan), g i là đ ph c t p logarit, n u f(n) = O(log an). ( ðiu ki n a > 1) • ð ph c t p O(n), g i là đ ph c t p tuy n tính, n u f(n) = O(n). • ð ph c t p O(nlog an), g i là đ ph c t p nlogarit n u f(n) = O(log an). ( ðiu ki n a > 1) • ð ph c t p O(n k), g i là đ ph c t p đa th c, n u f(n) = O(n k). • ð ph c t p O(a n), g i là đ ph c t p m ũ, n u f(n) = O(a n). ( ðiu ki n a > 1) • ð ph c t p O(n!), g i là đ ph c t p giai th a, n u f(n) = O(n!). Thí d 1. Tìm đ ph c t p c a thu t tốn đ gi i bài tốn: Tìm s l n nh t trong dãy n s nguyên a 1, a 2, , a n đã cho: Procedure max(a 1, a 2, , a n); Input: Dãy s a 1, a 2, , a n; Output: S l n nh t (max) c a dãy s đã cho; begin max := a 1; for i := 2 to n do Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 13
if a i > max then max := a i; end; M i b ưc c a vịng l p for ph i th c hi n nhi u nh t 3 phép tốn: phép gán bi n điu khi n i, phép so sánh a i v i max và cĩ th là phép gán a i vào max; vịng l p cĩ (n – 1) bưc (i = 2, 3, , n) do đĩ nhi u nh t cĩ c th y 3(n - 1) phép tốn ph i th c hi n. Ngồi ra thu t tốn cịn ph i th c hi n phép gán đ u tiên max := a 1. Vy s phép tốn nhi u nh t mà thu t tốn ph i th c hi n là: 3(n – 1) + 1 = 3n – 2 = O(n) ð ph c t p v th i gian c a thu t tốn là đ ph c t p tuy n tính. Thí d 2. ð ph c t p c a thu t tốn nhân ma tr n. Procedure nhân_matran; Input: 2 ma tr n A = (a ij )m x p và B = (b ij )p x n ; Output: ma tr n tích AB = (c ij )m x n ; Begin for i:=1 to m do for j:=1 to n do begin cij := 0; for k:=1 to p do c ij := c ij + a ik bkj ; end; End. S phép c ng và s phép nhân trong thu t tốn trên là: V i m i ph n t c ij ph i th c hi n p phép nhân và p phép c ng. Cĩ t t c m.n ph n t c ij , v y ph i th c hi n 2mnp phép cng và phép nhân. ð xác đ nh đ ph c t p c a thu t tốn, ta gi s A, B là hai ma tr n vuơng c p n, ngh ĩa là m = n = p. nh ư v y ph i c n 2n 3 phép c ng và phép nhân. V y đ ph c t p c a thu t tốn là O(n 3) – đ ph c t p đa th c. M t điu thú v là, khi nhân t 3 ma tr n tr lên thì s phép tính c ng và nhân ph thu c vào th t nhân các ma tr n y. Ch ng h n A, B, C là các ma tr n cĩ kích th ưc tươ ng ng là 30 ×20, 20 ×40, 40 ×10. Khi đĩ: Nu th c hi n theo th t ABC =A(BC) thì tích BC là ma tr n kích th ưc 20 ×10 và cn th c hi n 20.40.10 = 8000 phép tính c ng và nhân. Ma tr n A(BC) cĩ kích th ưc 30 ×10 và c n th c hi n 30.20.10 = 6000 phép c ng và nhân. T đĩ suy ra c n th c hi n 8000+6000 = 14000 phép tính c ng và nhân đ hồn thành tích ABC. Tươ ng t , n u th c hi n theo th t ABC = (AB)C thì c n th c hi n 30.20.40 phép tính c ng và nhân đ th c hi n tích AB và 30.40.10 phép c ng và nhân đ th c hiên tích (AB)C. Do đĩ s các phép tính c ng và nhân ph i th c hi n đ hồn thành tích ABC là 24000+12000 = 36000 phép tính. Rõ ràng hai cách nhân cho k t qu v s l ưng các phép tính ph i th c hi n là khác nhau. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 14
5. Thu t tốn tìm ki m Bài tốn tìm ki m đưc phát bi u nh ư sau: Tìm trong dãy s a 1, a 2, , a n m t ph n t cĩ giá tr b ng s a cho tr ưc và ghi l i v trí c a ph n t tìm đưc. Bài tốn này cĩ nhi u ng d ng trong th c t . Ch ng h n vi c tìm ki m t trong t đin, vi c ki m tra l i chính t c a m t đon v ăn b n, Cĩ hai thu t tốn c ơ b n đ gi i bài tốn này: Thu t tốn tìm ki m tuy n tính và thu t tốn tìm ki m nh phân. Chúng ta l n l ưt xét các thu t tốn này. 5.1. Thu t tốn tìm ki m tuy n tính (cịn g i là thu t tốn tìm ki m tu n t ). ðem so sánh a l n l ưt v i a i (i = 1, 2, , n) n u g p m t giá tr a i = a thì ghi l i v trí ca a i, n u khơng g p giá tr a i = a nào (a i ≠ a. ∀i) thì trong dãy khơng cĩ s nào b ng a. Procedure Tim_tuyen_tinh_phan_tu_bang_a; Input: a và dãy s a 1, a 2, , a n; Output: V trí ph n t c a dãy cĩ giá tr b ng a, ho c là s 0 n u khơng tìm th y a trong dãy; begin i := 1; while (i ≤ n and a i ≠ a) do i := i + 1; if i ≤ n then vitri := i else vitri := 0; end; Nh ư v y n u a đưc tìm th y v trí th i c a dãy (a i = a) thì câu l nh i := i + 1 trong vịng l p while đưc th c hi n i l n (i = 1, 2, , n). N u a khơng đưc tìm th y, câu l nh ph i th c hi n n l n. V y s phép tốn trung bình mà thu t tốn ph i th c hi n là: 1 + 2 + + n n(n + 1) n + 1 = = = O(n) n 2n 2 V y, đ ph c t p c a thu t tốn tìm ki m tuy n tính là đ ph c t p tuy n tính. 5.2. Thu t tốn tìm ki m nh phân. Gi thi t r ng các ph n t c a dãy đưc x p theo th t t ăng d n. Khi đĩ so sánh a 1+ n  vi s gi a dãy, n u a a m thì tìm a trong dãy am+1 , , a n. ði v i m i dãy con (m t n a c a dãy đã cho) đưc làm t ươ ng t đ ch ph i tìm ph n t cĩ giá tr b ng a m t n a dãy con đĩ. Quá trình tìm ki m k t thúc khi tìm th y v trí c a ph n t cĩ giá tr b ng a ho c khi dãy con ch cịn 1 ph n t . Ch ng h n vi c tìm s 8 trong dãy s 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22 đưc ti n hành nh ư sau: Dãy đã cho g m 14 s h ng, chia dãy thành 2 dãy con: 5, 6, 8, 9, 11, 12, 13 và 15, 16, 17, 18, 19, 20, 22 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 15
Vì 8 a m then i := m+1 else j := m; end; if a = a i then vitri := i else vitri := 0; end; ð ph c t p c a thu t tốn tìm ki m nh phân đưc đánh giá như sau: Khơng gi m k tng quát cĩ th gi s đ dài c a dãy a 1, a 2, , a n là n = 2 v i k là s nguyên d ươ ng. (N u n khơng ph i là l ũy th a c a 2, luơn tìm đưc s k sao cho 2 k – 1 < n < 2 k do đĩ cĩ th xem dãy đã cho là m t ph n c a dãy cĩ 2 k ph n t ). Nh ư v y ph i th c hi n nhi u nh t k ln chia đơi các dãy s (m i n a dãy c a l n chia đơi th nh t cĩ 2 k – 1 ph n t , c a l n chia đơi th hai cĩ 2 k – 2 ph n t , , và c a l n chia đơi th k là 2 k – k = 2 0 = 1 ph n t ). Nĩi cách khác là nhi u nh t cĩ k vịng l p while đưc th c hi n trong thu t tốn tìm ki m nh phân. Trong m i vịng l p while ph i th c hi n hai phép so sánh, và vịng l p cu i cùng khi ch cịn 1 ph n t ph i th c hi n 1 phép so sánh đ bi t khơng cịn 1 ph n t nào thêm n a và 1 phép so sánh đ bi t a cĩ ph i là ph n t đĩ hay khơng. T đĩ th y r ng thu t tốn ph i th c hi n nhi u nh t 2k + 2 = 2[log 2n] + 2 = O(logn) phép so sánh. V y, đ ph c t p c a thu t tốn tìm kim nh phân là đ ph c t p logarit. 6. Thu t tốn đ quy 6.1. Cơng th c truy h i ðơi khi r t khĩ đ nh ngh ĩa m t đ i t ưng nào đĩ m t cách t ưng minh, nh ưng cĩ th đnh ngh ĩa đ i t ưng đĩ qua chính nĩ v i đ u vào nh h ơn. Cách đnh ngh ĩa nh ư v y g i là cách đnh ngh ĩa b ng truy h i ho c đ nh ngh ĩa b ng đ quy và nĩ cho m t cơng th c g i là cơng th c truy h i. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 16
ðnh ngh ĩa: ðnh ngh ĩa b ng truy h i bao g m các quy t c đ xác đ nh các đ i tưng, trong đĩ cĩ m t s quy t c dùng đ xác đ nh các đ i t ưng ban đu g i là các điu ki n ban đ u; cịn các quy t c khác dùng đ xác đ nh các đ i t ưng ti p theo g i là cơng th c truy h i. Thí d 1. Dãy s a n đưc đ nh ngh ĩa b ng đ quy nh ư sau: a0 = 3; a n = a n – 1 + 3. Trong đĩ a 0 = 3 là điu ki n ban đ u, cịn a n = a n – 1 + 3 là cơng th c truy h i. Thí d 2. ðnh ngh ĩa b ng đ quy giai th a c a s t nhiên n là: GT(0) = 1; GT(n) = n.GT(n – 1). Vì GT(n) = n! = n(n-1)(n-2) 1 = n.GT(n-1). Trong đĩ GT(0) = 1 là điu ki n ban đ u, cịn GT(n) = n.GT(n – 1) là cơng thc truy h i. Thí d 3. Dãy s F 0, F 1, F 2, , F n đưc đ nh ngh ĩa: F0 = 0; F 1 = 1; F n = F n – 1 + F n – 2 . ðĩ chính là đnh ngh ĩa b ng đ quy c a dãy s cĩ tên là dãy Fibonacci. Trong đĩ F0 = 0, F 1 = 1 là các điu ki n ban đ u, cịn F n = F n – 1 + F n – 2 là cơng th c đ quy. D th y m t s s h ng đ u tiên c a dãy là: 0; 1; 1; 2; 3; 5; 8; 13; 21; 6.2. Thu t tốn đ quy. Nhi u khi vi c gi i bài tốn v i đ u vào xác đnh cĩ th đưa v vi c gi i bài tốn đĩ vi giá tr đ u vào nh h ơn. Ch ng h n: n! = n . (n-1)! hay UCLN(a, b) = UCLN(a mod b, b) , a > b ðnh ngh ĩa: M t thu t tốn g i là đ quy n u thu t tốn đĩ gi i bài tốn b ng cách rút g n liên ti p bài tốn ban đu t i bài tốn c ũng nh ư v y nh ưng v i d li u đ u vào nh hơn. D th y c ơ s c a thu t tốn là cơng th c truy h i. Thí d 1. Tính giai th a c a s t nhiên n b ng đ quy. Function GT(n); Input: S t nhiên n; Output: Giá tr c a n!; Begin if n = 0 then GT(0) := 1 else GT(n) := n*GT(n – 1); End; Thí d 2. Tính s h ng c a dãy Fibonacci b ng đ quy. Function Fibonacci(n); Input: V trí th n c a dãy Fibonacci; Output: Giá tr F n c a dãy Fibonaci; Begin Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 17
if n = 0 then Fibonacci(0) := 0 else if n = 1 then Fibonacci(1) := 1 else Fibonacci(n) := Fibonacci(n-1) + Fibonacci(n-2); End; Thí d 3. Thu t tốn đ quy tìm UCLN(a, b). Function UCLN(a, b); Input: Hai s nguyên d ươ ng a và b; Output: Ưc s chung l n nh t c a a và b; Begin if b = 0 then UCLN(a, b) := a else if a > b then UCLN(a, b) := UCLN(a mod b, b) else UCLN(a, b) := UCLN(b mod a, a); End; Bây gi chúng ta th tìm đ ph c t p v th i gian c a m t vài thu t tốn vi t b ng đ quy. Ch ng h n xét thu t tốn đ quy tính s h ng c a dãy Fibonacci, đ tính F n ta bi u di n F n = F n – 1 + F n – 2 , sau đĩ thay th c hai s này b ng t ng c a hai s Fibonacci b c th p h ơn. Quá trình ti p t c nh ư v y cho đ n khi F 0 và F 1 xu t hi n thì đưc thay b ng các giá tr c a chúng trong đ nh ngh ĩa. Mi b ưc đ quy cho t i khi F 0 và F 1 xu t hi n, các s Fibonacci đưc tính hai l n. Ch ng h n gi n đ cây hình 2 cho ta hình dung cách tính F 5 theo thu t tốn đ quy. T đĩ cĩ th th y r ng đ tính F n c n th c hi n F n + 1 – 1 phép c ng. F 5 F F 4 3 F 3 F 2 F 2 F 1 F 2 F1 F 1 F0 F1 F 0 F 1 F 0 Hình 2. L ưc đ tính F 5 b ng đ quy ð ph c t p c a thu t tốn đ quy tìm ưc s chung l n nh t c a hai s nguyên dươ ng a, b (thí d 3): UCLN(a,b) = UCLN(a mod b,b), n u a ≥ b (a mod b là ph n d ư khi chia a cho b) đưc đánh giá b ng cách ng d ng dãy Fibonacci. Tr ưc h t b ng quy n p tốn h c chúng ta ch ng minh s h ng t ng quát c a dãy Fibonacci th a mãn: Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 18
n – 2 1 + 5 F n > α , ∀n ≥ 3, trong đĩ α = . (1) 2 Th t v y: Ta cĩ: α α đúng v i n, xét v i n+1. D th y α là m t nghi m c a ph ươ ng trình x2 – x – 1 = 0 nên suy ra α2 = α + 1. T đĩ: αn – 1 = α2αn – 3 = ( α + 1) αn – 3 = αn – 2 + αn – 3 . n – 3 n – 2 Theo gi thi t quy n p, n u n ≥ 4, ta cĩ F n – 1 > α và F n > α . Thay vào đnh ngh ĩa c a dãy Fibonacci: n – 2 n – 3 n – 1 Fn + 1 = F n + F n – 1 > α + α = α n – 2 V y F n > α , ∀n ≥ 3. Cơng th c (1) đưc ch ng minh. Tr l i thu t tốn đ quy tìm ưc s chung l n nh t c a hai s nguyên d ươ ng a, b (a ≥ b). ð ph c t p c a thu t tốn đưc đánh giá qua s l ưng các phép chia dùng trong thu t tốn này. ðt r 0 = a, r 1 = b, ta cĩ: r 0 = r 1q1 + r 2; 0 ≤ r 2 α v i n > 2 và α = nên b > α . 2 n −1 1 T đĩ: lgb > (n – 1) lg α > ( vì lg α ≈ 0,208 > ). 5 5 Vy: n – 1 < 5lgb ⇒ n < 5lgb + 1 = O(lgb). Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 19
Ngh ĩa là đ ph c t p c a thu t tốn Ơ-clit vi t theo đ quy là O(lgb). Qua đây cĩ th th y trong nhi u tr ưng h p, vi c đánh giá đ ph c t p c a m t thu t tốn qu là khơng d dàng. 6.3. ð quy và l p Hu nh ư các bài tốn gi i đưc b ng l p thì c ũng gi i đưc b ng đ quy. Thơng th ưng, n u dùng ph ươ ng pháp l p thì s phép tính s ít h ơn; chúng ta minh h a điu này bng th t c tính s Fibonacci b ng thu t tốn đ quy và thu t tốn l p. Trong thí d 2, m c 6.2. chúng ta đã tính s phép c ng theo thu t tốn đ quy đ tính s Fibonacci th n là F n + 1 – 1. Bây gi ta xét th t c l p đ tính s Fibonacci: Function Lap_Fibonacci(n); Input: V trí th n + 1 c a dãy Fibonacci; Output: Giá tr f n c a dãy; Begin 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; Lap_Fibonacci := z; End. Thu t tốn này kh i t o x nh ư là F 0 = 0 và y nh ư là F 1 = 1. Qua m i b ưc l p 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. Vy qua vịng l p th nh t, ta cĩ x = F 1 và y = F 2. Khi qua vịng l p th n – 1 thì x = F n – 1 . Vy ch cĩ n – 1 phép c ng đưc th c hi n đ tính F n. Rõ ràng s l ưng các phép tính này nh h ơn khi tính b ng đ quy. Tuy s l ưng các phép tính khi dùng đ quy nhi u h ơn khi dùng l p, nh ưng nhi u khi ng ưi ta v n thích s d ng đ quy h ơn. Cĩ l lý do là ch ch ươ ng trình đ quy th ưng gn h ơn, m t khác cĩ nh ng bài tốn ch gi i đưc b ng đ quy mà khơng gi i đưc b ng lp. 7. Mt vài thu t tốn v s nguyên 7.1. Bi u di n các s nguyên ðnh lý: Cho b là m t s nguyên d ươ ng l n h ơn 1, khi đĩ n u n là s nguyên d ươ ng tùy ý thì n cĩ th bi u di n duy nh t d ưi d ng: k – 1 k – 2 n = a k – 1 b + a k – 2 b + + a 1 b + a 0. (1) Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 20
trong đĩ k là s nguyên khơng âm, a 0, a 1, , a k – 1 là các s nguyên khơng âm và nh h ơn b đng th i a k – 1 ≠ 0. Chúng ta khơng ch ng minh đ nh lý này. Bi u di n c a s n theo cơng th c (1) g i là khai tri n c ơ s b c a n và đưc ký hi u là (a k – 1 ak – 2 a 0)b. ðc bi t, n u là c ơ s 10 (h th p phân, b = 10), ng ưi ta quy ưc khơng c n vi t c ơ s kèm theo. Ngồi h th p phân cịn cĩ h nh phân (c ơ s 2), h bát phân (cơ s 8) và h th p l c phân (c ơ s 16) là hay đưc dùng trong tin h c. Thí d 1: Xác đnh khai tri n th p phân c a s nguyên t các h c ơ s khác: 2 (245) 8 = 2.8 + 4.8 + 5 = 165 7 6 5 4 3 2 (10101111) 2 = 1.2 + 0.2 + 1.2 + 0.2 + 1.2 +1.2 + 1.2 + 1 = 175 H th p l c phân cĩ 16 ch s 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, trong đĩ A, B, C, D, E, F t ươ ng ng v i các s 10, 11, 12, 13, 14, 15 trong h th p phân. ch ng h n: 4 3 2 (2AE0B) 16 = 2.16 + 10.16 + 14.16 + 0.16 + 11 = 175 627 Bây gi xét bài tốn ng ưc, xác đ nh khai tri n theo c ơ s b c a s t nhiên n cho trong h th p phân. Tr ưc h t chia n cho b đưc s d ư là a 0: n = bq 0 + a 0, 0 ≤ a 0 ≤ b ( a 0 = n mod b) khi đĩ a 0 là chính là ch s cu i cùng trong h c ơ s b. Ti p theo chia q 0 cho b đưc s d ư a1 chính là s đ ng tr ưc a 0 trong h đ m c ơ s b: q0 = bq 1 + a 1, 0 ≤ a 1 ≤ b ( a 1 = q 0 mod b) Quá trình ti p t c cho đ n khi nh n đưc th ươ ng b ng 0. Thí d 2: Tìm khai tri n c ơ s 8 c a 12345. Ta cĩ: 12345 = 8. 1543 + 1 1543 = 8. 192 + 7 192 = 8. 24 + 0 24 = 8 . 3 + 0 3 = 8 . 0 + 3 Vy: 12345 = (30071) 8. Thu t tốn tìm khai tri n c ơ s b c a s t nhiên n nh ư sau: Procedure Khai_trien_co_so_b; Input: S t nhiên n và c ơ s b; Output: Khai tri n n theo c ơ s b (a kak – 1 a 0)b; Begin q := n; k := 0; while q ≠ 0 do begin a k := q mod b; Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 21
q :q = ; b k := k + 1; end; End; 7.2. Cng và nhân trong h nh phân Các thu t tốn th c hi n các phép tính v i các s nguyên h nh phân cĩ vai trị quan tr ng trong tin h c. B i v y ph n này mơ t hai thu t tốn th c hi n phép c ng và phép nhân – hai phép tốn s h c c ơ b n nh t – các s nguyên trong h nh phân. Gi s cĩ hai s nguyên a và b d ưi d ng nh phân: a = (a n – 1 a n – 2 a 1 a 0)2 và b = (b n – 1 bn – 2 b 1 b 0)2 . (N u c n thi t cĩ th đ t thêm các bít 0 lên ph n đ u c a các khai tri n nh phân c a a ho c b) a. Phép c ng ð c ng a và b, tr ưc h t c ng hai bit cu i: a0 + b 0 = c 0.2 + s 0. đây s 0 là bit cu i trong khai tri n nh phân c a t ng a + b và c 0 là s nh . Sau đĩ là 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 trong khai tri n nh phân c a t ng a + b và c 1 là s nh . Ti p t c nh ư v y cho đ n: an – 1 + b n – 1 + c n – 2 = c n – 1 .2 + s n – 1 . ðt s n = c n – 1 ta đưc khai tri n nh phân c a t ng a + b: a + b = (s n s n – 1 s 1 s 0)2. Thu t tốn đưc mơ t b ng ngơn ng ph ng Pascal nh ư sau: Procedure Cong_hai_so_nguyen_duong_dang_nhi_phan; Input: Hai s nguyên d ươ ng a và b d ưi d ng nh phân (a n – 1 a 1 a 0)2 và (b n – 1 b 1 b 0)2 ; Output: T ng a + b d ưi d ng nh phân (s n s n – 1 s 1 s 0)2; Begin c := 0 for j:=1 to n do begin a j + b j + c :d =   ;  2  Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 22
sj := a j + b j + c – 2d; c := d; end; sn := c; End; Cĩ th hi u là phép c ng trong h nh phân c ũng đưc ti n hành nh ư h th p phân, nh ưng l ưu ý r ng: 0 + 0 = 0; 0 + 1 = 1 + 0 = 1; 1 + 1 = 10 Ch ng h n tính (1110) 2 + (10111) 2 là: 0 1110 + 1 0111 10 0101 ð ph c t p c a thu t tốn đưc đánh giá nh ư sau: M i bit trong khai tri n nh phân ca t ng a + b đưc tính b ng cách c ng m t c p bit và cĩ th ph i c ng thêm bit nh . Nh ư vy đ cĩ m i bit c a t ng c n nhi u nh t 3 phép c ng. M i khai tri n nh phân cĩ n bit. Vy ph i th c hi n t i đa 3n phép c ng hai s nguyên n bit, ngh ĩa là thu t tốn tốn cĩ đ ph c t p tuy n tính O(n). b. Phép nhân Theo lu t phân ph i, ta cĩ: n−1 n−1 j j a.b = a ∑ b j 2 = ∑ ()ab j 2 j=0 j=0 D th y:  a , n u b j = 1 ab j =   0 , n u b j = 0 và m i l n nhân m t khai tri n nh phân v i 2 là d ch chuy n khai tri n đĩ m t v trí v bên j trái b ng cách thêm m t s 0 vào cu i khai tri n đĩ. Do đĩ cĩ th nh n đưc tích (ab j)2 bng cách d ch khai tri n nh phân c a ab j v bên trái j v trí, nĩi cách khác là thêm j bit 0 vào cu i khai tri n nh phân ab j. Cu i cùng nh n đưc tích ab b ng cách c ng n s nguyên j dươ ng ab j2 v i j = 0, 1, , n – 1. 110 Thí d : Tìm tích c a a = (110) 2 và b = (101) 2. × 0 0 101 ab 0.2 = (110) 2.1.2 = (110) 2 1 1 110 ab 1.2 = (110) 2.0.2 = (0000) 2 2 2 + 000 ab 2.2 = (110) 2.1.2 = (11000) 2 110 và, cu i cùng ta c ng (110) 2, (0000) 2 và (11000) 2 v i nhau 11110 đưc ab = (11110) 2. D th y cách th c hi n phép nhân trong h nh phân c ũng gi ng nh ư trong h th p phân. Thu t tốn đưc mơ t b ng ngơn ng ph ng Pascal mh ư sau: Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 23
Procedure Nhan_hai_so_nguyen_dang_nhi_phan; Input: Hai s nguyên d ươ ng a và b d ưi d ng nh phân (a n – 1 a 1 a 0)2 và (b n – 1 b 1 b 0)2 ; Output: Tích ab d ưi d ng nh phân; Begin for j := 0 to n do if b j = 1 then c j := a đưc d ch sang trái j v trí else c j := 0; (* c 0, c 1, , c n – 1 là các tích riêng ph n *) p := 0; for j := 0 to n – 1 do p := p + c j ; (* p là giá tr c a tích ab *) End; ð ph c t p c a thu t tốn nhân 2 s nguyên d ng nh phân b ng cách tính s các phép c ng bit và d ch bít c a thu t tốn đưc đánh giá nh ư sau: j Các tích riêng c j = ab j2 khơng c n d ch chuy n khi b j = 0, vì khi đĩ c j = 0 và nĩ ph i dch chuy n j v trí khi b j = 1. Vì th v i t t c n tích riêng c j c n th c hi n t i đa: n(n − )1 0 +1+ 2 + + n( − )1 = 2 phép d ch ch . V y s phép d ch ch t i đa là O(n 2). n – 1 Sau khi dich ch s nguyên c n – 1 = ab n – 1 2 cĩ 2 n bit, theo thu t tốn c ng hai s nguyên s cĩ t i đa O(n) s phép c ng bit đ c ng t t c n các tích riêng c j. V y đ ph c t p c a thu t tốn nhân 2 s nguyên d ng nh phân là O(n 2). Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 24
BÀI T P CH ƯƠNG 1 1.1. Ch ng minh r ng: x 2 +1 a) = O )x( ; b) 2 n + 17 = O(3 n). x +1 1.2. Tìm m t s nguyên n nh nh t sao cho f(x) = O(x n), n u: a) f(x) = 2x 3 + x 2lgx; b) f(x) = 3x 5 + (lgx) 4; x 4 + x 2 +1 x3 + 5lg x c) )x(f = ; d) )x(f = . x3 +1 x 4 +1 1.3. Ch ng minh r ng x 2 + 4x + 17 là O(x 3), nh ưng x 3 khơng là O(x 2 + 4x + 17). 1.4. Hãy cho m t đánh giá big-O t t nh t cĩ th đưc đ i v i các hàm sau: a) (n 2 + 8)(n + 1); b) (nlgn + n 2)(n 3 + 2); c) (n! + 2 n)(n 3 + lg(n 2 + 1)); d) (2 n + n 2)(n 3 + 3 n); e) (x 2 + x(lgx) 3)(2 x + x 3). 1.5. Lp và mơ t thu t tố n b ng ngơn ng ph ng Pascal cho cá c bà i tố n sau: a) Tí nh x n v i x là s th c và n là s nguyên. (Gi ý: tr ư c h t l p tht c tí nh x n v i 1 n là s nguyên d ươ ng, sau đĩ m rng tht c cho n là s nguyên âm x −n = , x n n∈N+) b) Chdù ng cá c l nh gá n đ bi n b ba s (x, y, z) thà nh (y, z, x). S ti thi u cá c l nh gá n là bao nhiêu? c) Chè n 1 s nguyên x và o vtríthí ch h p trong dã y cá c s nguyên a 1, a 2, , a n đã đư c x p theo th t tăng d n. d) Tì m s nh nh t và s ln nh t trong dã y g m n s nguyên đã cho. k 1.6. Xác đnh s các phép nhân đưc dùng đ tính x 2 b t đ u v i x r i liên ti p bình ph ươ ng ( đ tìm x 2, x 4, ). Cách này cĩ hi u qu h ơn cách nhân x v i chính nĩ m t s l n thích h p khơng? 1.7. Lp và mơ t thu t tố n b ng ngơn ng ph ng Pascal cho bà i tố n sau: ðm các bit 1 trong m t xâu bit b ng cách ki m tra t ng bit c a xâu xem cĩ ph i là bit 1 khơng. Cho đánh giá big-O đi v i các phép so sánh đưc dùng trong thu t tốn. n n – 1 1.8. Thu t tố n tí nh giátrc a đa th c P(x) = a nx + a n – 1 x + + a 1x + a 0t i x = c nh ư sau: function Dathuc(c, a 0, a 1, , a n); ð u và o: c, a 0, a 1, , a n ; ð u ra: y = P(c); begin power := 1; y : = a 0 ; Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 25
for i := 1 to n do begin power := power *c ; y := y + a i*power ; end; Dathuc := y; end; a) Tì m P(2) nu P(x) = 3x 2 + x + 1 bng cá ch th c hi n t ng b ư c thu t tố n trên. b) Cĩ bao nhiêu phé p nhân vàphé p c ng dù ng đ tăng bi n trong vị ng l p? n n – 1 1.9. Thu t tố n Horner đtì m giátr P(c) c a đa th c P(x) = a nx + a n – 1 x + + a 1x + a0 nh ư sau: function Horner(c, a 0, a 1, , a n); ð u và o: c, a 0, a 1, , a n ; ð u ra: y = P(c); begin y := a n ; for i := 1 to n do y := y*c + a n – i ; Horner := y; end; Cá c câu h i nh ư trong bà i t p 1.8. 1.10. L p thu t tốn tìm s h ng đ u tiên trong m t dãy các s nguyên cho tr ưc sao cho s h ng tìm th y b ng m t s h ng nào đĩ đng tr ưc nĩ. Tìm đ ph c t p v th i gian c a thu t tốn đã l p. 1.11. L p thu t tốn tìm trong dãy s nguyên d ươ ng cho tr ưc s h ng đ u tiên nh h ơn s hng đ ng ngay tr ưc nĩ. Xác đ nh đ ph c t p c a thu t tốn đã l p. 1.12. Ma tr n lơgic Ma tr n mà các ph n t là 0 ho c 1 đưc g i là ma tr n lơgic. 1) Cho hai ma tr n lơgic kích th ưc m ×n: A = [aij ]m, n và B = [b ij ]m, n , ta cĩ: • A ∨ B là ma tr n lơgic h p gi a A và B cĩ các ph n t hàng i, c t j là:  1 n u a ij = 1 ho c b ij = 1 aij ∨ bij =   0 n u a ij = b ij = 0 • A ∧ B là ma tr n lơgic giao gi a A và B cĩ các ph n t hàng i c t j là  1 n u a ij = b ij = 1 aij ∧ bij =   0 n u a ij = 0 ho c b ij = 0 2) Cho hai ma tr n lơgic A = [a ij ]m, p kích th ưc m ×p và B = [b ij ]p, n kích th ưc p ×n. Tích boole c a A v i B, ký hi u A ⊗B, là ma tr n lơgic kích th ưc m×n mà ph n t c ij (ph n t hàng i, c t j) đưc xác đ nh nh ư sau: cij = (a i1 ∧b1j ) ∨ (a i2 ∧b2j ) ∨ ∨ (a ip ∧bpj ) Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 26
a) Vi t thu t tốn d ng ph ng Pascal cho các phép tốn c a các ma tr n lơgic nh ư các đnh ngh ĩa nêu trên. b) Cĩ bao nhiêu phép tốn bit đưc dùng đ tính A ⊗B v i A, B là các ma tr n lơgic vuơng c p n. c) Ch ng minh r ng: A ⊗(B ⊗C) = (A ⊗B) ⊗C v i gi thi t các phép tốn trong bi u th c đã cho là th c hi n đưc, 1.13. Tìm và mơ t thu t tốn đ quy cho các bài tốn sau: a) Tìm t ng c a n s nguyên d ươ ng l đ u tiên. b) Tìm s c c ti u c a t p h u h n các s nguyên. 1.14. Hãy đư a ra thu t tốn đ quy tìm n! mod m, tromg đĩ m, n, là các s nguyên d ươ ng. n 1.15. Tìm thu t tốn đ quy tính a 2 , trong đĩ a là m t s th c và n là m t s nguyên n+1 n 2 dươ ng (G i ý: dùng đng th c a 2 = (a 2 ) ). 1.16.Tì m thu t tố n đ qui tì m ư c s chung l n nh t c a 2 s nguyên khơng âm a, b (a a i do i := i + 1; for j := 0 to n-i do a n – j + 1 := a n – j ; a j := x; {x đã đưc chèn vào v trí đúng} 1.7. Procedure ones (a: xâu bit, a = a 1a2 a n); begin ones := 0; for i:= 1 to n do if a i = 1 then ones := ones + 1; end; {ones là s các bít 1 trong xâu a} Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 27
1.10. Procedure find duplicate (a 1a2 a n : integer); location := 0; i := 2; while i ≤ n and location = 0 do begin j := 1; while j < i and location := 0 do if a i = a j then location := i else j := j +1 i := i +1; end; {location là ch s c a giá tr đ u tiên l p l i giá tr tr ưc trong dãy} O(n 2) 1.11. Procedure find decrease (a 1 a 2 a n nguyên d ươ ng); location := 0; i := 2; while i ≤ n and location = 0 do if a i < a i – 1 then location := i else i : = i + 1; end; {location là ch s c a giá tr đ u tiên nh h ơn giá tr ngay tr ưc nĩ} ð ph c t p c a thu t tốn là O(n). 1.13. a) Procedure sum of odds (n : nguyên d ươ ng); if n = 1 then sum of odds := 1 else sum of odds : = sum of odds(n – 1) + 2n – 1; b) Procedure smalless (a 1, a 2, , a n : nguyên d ươ ng); if n = 1 then smalless (a 1, a 2, , a n) := a 1 else smalless (a 1, a 2, , a n) := min(smalless (a 1, a 2, , a n – 1 ), a n); 1.14. Procedure modfactorial (n, m : nguyên d ươ ng); if n = 0 then modfactorial (n, m) : = 1 else modfactorial (n, m) := (n * modfactorial (n-1, m)) mod m; Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 28
CÂU H I ƠN T P CH ƯƠ NG 1 1. Phát bi u đnh ngh ĩa và các đc tr ưng c a thu t tốn. Các ph ươ ng pháp mơ t thu t tốn. 2. Trình bày quan h big-O c a các hàm s và khái ni m đ ph c t p v th i gian c a thu t tốn. ðánh giá đ ph c t p c a thu t tốn nhân ma tr n 3. Mơ t các thu t tốn tìm ki m và đánh giá đ ph c t p c a chúng. 4. ðnh ngh ĩa b ng đ quy là gì? Th nào là cơng th c truy h i? Trình bày thu t tốn đ quy. M i liên h gi a đ quy và l p. 5. Mơ t các thu t tốn l p và đ quy đ: Tìm t ng c a m t dãy s ; Tìm ưc s chung nh nh t c a hai s nguyên d ươ ng; Tìm s Fibonacci 6. Nêu thu t tốn chuy n đi c ơ s c ơ s c a s t nhiên. Cách c ng và nhân các s nguyên trong h nh phân? Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 29
CH ƯƠ NG 2 BÀI TỐN ðM 1. Nguyên lý cng và nguyên lý nhân 1.1. Nguyên lý cng 1.2. Nguyên lý nhân 2. Ch nh h p. Hố n v . T hp. 2.1. Ch nh h p 2.2. Hố n v 2.3. T hp 2.4. Ch nh h p và T hp suy r ng 3. Nguyên lý bù tr 4. Gi i cá c h th c truy h i 4.1. Ph ươ ng phá p kh đtì m cơng th c tr c ti p t cơng th c truy h i 4.2. Gi i cá c h th c truy h i tuy n tí nh. 5. Bà i tố n li t kê. 5.1. Ph ươ ng phá p sinh 5.2. Thu t tố n quay lui 6. B ài tố n t n t i 6.1. Nguyên lý Di-ric-le (Dirichlet) 6.2. Mt và i bà i tố n ng d ng nguyên lý Di-ric-lê. 6.3. Ph ươ ng phá p ph n ch ng Lý thuy t t hp là mt ph n r t quan tr ng c a tố n r i r c, nĩ chuyên nghiên c u s sp x p cá c đi t ư ng (ph n t c a t p h p) theo m t quy t c nà o đĩ. Mi k t quc a m t cá ch s p x p cá c ph n t c a m t t p h p theo mt quy t c xá c đnh đã cho đư c g i là mt c u hì nh t hp. ðm cá c ph n t c a m t t p h p, ho c cá c c u hì nh t hp là ni dung c a b ài tố n đ m. Chú ng ta cũ ng c n cĩ mt quan ni m r ng rã i v khá i ni m đ m, ch ng h n n u nĩi cĩ 100 đ thìđĩlà mt cá ch đ m, nh ưng cĩ th thay cá ch nĩi đĩ bng cá ch nĩ i cĩ 10 t 5đ và 25 t 2đ. Nĩ i cá ch khá c, li t kê cá c c u hì nh t hp là mt cá ch đ m. Cá c t p h p nĩ i đ n trong ch ươ ng nà y là cá c t p h p cĩ hu h n cá c ph n t . S lư ng cá c ph n t c a t p h p A, ký hi u là N(A), đư c g i là lc l ư ng (hay b n s ) c a tp h p A. 1. Nguyên lý cng và nguyên lý nhân. 1.1. Nguyên lý cng Nu A và B là 2 tp h p r i nhau (A ∩B = ∅) thì N(A ∪B) = N(A) + N(B). Nguyên lýnà y cĩ th m rng nh ư sau: Gi s A1, A 2, , A nlàcá c t p con c a m t tp X nà o đĩthomã n: Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 32
- Cá c A i đơi m t r i nhau (A i∩Aj = ∅, khi i ≠ j) - X = A 1∪A2∪ ∪An . (Cá c t p A 1, A 2, , A nthomã n 2 tí nh ch t trên đư c g i là mt phân ho ch c a t p X) Khi đĩ: N(X) = N(A 1) + N(A 2) + + N(A n) ð c bi t, ta cĩ N(A) = N(X) – N( A ) trong đĩ A là tp bù c a t p A trong X. Thí d 1: Mt khốh c cĩ 3 danh sá ch l a ch n cá c bà i th c hà nh: Danh sá ch th nh t cĩ 10 bà i; danh sá ch th hai cĩ 15 bà i; danh sá ch th ba cĩ 25 bà i. Mi sinh viên đư c ch n 1 bà i trong 3 danh sá ch trên đlà m th c hà nh. H i m i sinh viên cĩ bao nhiêu cá ch la ch n bà i th c hà nh. Gi i: Cĩ 10 cá ch l a ch n trong danh sá ch th nh t, 15 cá ch l a ch n trong danh sá ch th hai và 25 cá ch l a ch n trong danh sá ch th ba. Vy cĩ 10 + 15 + 25 = 50 cá ch l a ch n cho m i sinh viên. Thí d 2: M t đồ n v n đng viên c a m t đa ph ươ ng đư c c đi thi đu 2 mơn: bn sú ng và bn cung. Trong đồ n cĩ 10 nam và s vn đng viên b n sú ng là 14 (kc nam và n). S n vn đng viên b n cung b ng s nam v n đng viên b n sú ng. H i đồ n cĩ bao nhiêu ng ư i. Gi i: G i A, B t ươ ng ng làcá c t p v n đng viên nam, v n đng viên n , ta cĩ N(A) = 10 A 1, A 2 t ươ ng ng làcá c t p v n đng viên nam b n sú ng, v n đng viên nam b n cung, ta cĩ N(A 1) + N(A 2) = 10 B 1, B 2 t ươ ng ng làcá c t p v n đng viên n bn sú ng, v n đng viên n bn cung, ta cĩ N(B 2) = N(A 1) và N(B 1) + N(A 1) = 14 Tđĩ N(B 1) + N(B 2) = 14, nghĩ a làđồ n cĩ 14 vn đng viên n . Vy tồ n đồ n cĩ 10 + 14 = 24 vn đng viên. Thí du 3: Xé t đo n ch ươ ng trì nh ph ng Pascal sau k := 0; for i 1:= 1 to n 1 do k := k + 1; for i 2:= 1 to n 2 do k := k + 1; for i 3:= 1 to n 3 do k := k + 1; H i sau khi th c hi n xong đo n ch ươ ng trì nh trên, giátrc a k b ng bao nhiêu? Gi i: Giátr ban đu gá n cho k là 0. Kh i l nh g m 3 vị ng l p tu n t , sau m i b ư c l p c a t ng vị ng l p giátrc a k đư c t ăng thêm 1, vị ng l p th i (i = 1, 2, 3) cĩ ni bư c nên sau vị ng l p th i giá tr ca k đư c t ăng thêm n i. Do cá c vị ng l p là tu n t nên sau c 3 vị ng l p thìgiátrc a k là : k = n 1 + n 2 + n 3. 1.2. Nguyên lý nhân Nu m i thà nh ph n th i (tc là ai) c a b cĩ th t gm k thà nh ph n (a 1, a 2, , a k) cĩ ni cách ch n (i = 1, 2, , k) thì s lư ng cá c b k thà nh ph n đĩslà n1n2 n k ( tí ch c a s cá c cá ch ch n c a m i thà nh ph n). Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 33
Cĩ th phá t bi u nguyên lý nhân d ư i d ng s ph n t c a tí ch ð-cá c c a cá c t p h p: N(A 1 × A 2 × × A k) = N(A 1). N(A 2) N(A k) Thí d 1: Cĩ 4 ph ươ ng ti n đi tHà ni và o thà nh ph HChí Minh là : Ơ tơ, Tà u ho , Tà u thuvàMá y bay. Cĩ 2 ph ươ ng ti n đi t thà nh ph Hchí Minh ra Cơn đo là Má y bay vàTà u thu . H i cĩ my cá ch đi t Hà ni đ n Cơn đo n u b t bu c ph i đi qua thà nh ph HChí Minh? Gi i: M i cá ch đi t Hà ni và o thà nh ph HChí Minh cĩ 2 cá ch đi ra Cơn đo. Vy vi 4 cá ch đi t Hà ni và o thà nh ph HChí Minh cĩ 4 . 2 = 8 cá ch đi t Hà n i qua thành ph H Chí Minh r i đn Cơn đo. Thí d 2: M t xâu nh phân là mt dã y liên ti p cá c ch s 0 ho c 1 (g i là bit 0 và bit 1). ðdà i c a xâu là scá c ch s 0, 1 cĩ mt trong xâu. Hai xâu cù ng đdà i đư c g i làkhá c nhau n u cĩí t nh t m t vtrít i đĩcá c bit làkhá c nhau. H i cĩ bao nhiêu xâu nh phân cĩđdà i 8 ? Gi i: T i m i m t trong 8 vtrícĩ 2 cá ch l a ch n là bit 0 ho c bit 1. Do đĩ theo quy tc nhân cho th y cĩ 28 = 256 xâu nh phân khá c nhau cĩđdà i 8. Thí d 3: M t bi n s xe má y c a m t đa ph ươ ng đư c c u t o g m hai nhĩ m. Nhĩ m đu g m 2 ký t: đu tiên là mt ch cá i sau đĩlà mt ch s. Nhĩ m th 2 gm m t dã y 4 ch s liên ti p (kccá c s trù ng nhau). H i cĩ th phá t hà nh bao nhiêu bi n s xe t i đa ph ươ ng đĩ. Gi i: Cĩ tt c 24 cá ch ch n cho vtrí ch cá i đu tiên. Năm vtrí ti p theo, m i vtrí cĩ 10 cá ch ch n. Theo quy t c nhân, s bi n s đă ng ký xe má y cĩ th là : 24.10.10.10.10.10 = 24.10 5 = 2 400 000 Thí d 4: Giátrc a bi n k b ng bao nhiêu sau khi đo n ch ươ ng trì nh sau đư c th c hi n? k := 0; for i 1 := 1 to n 1 do for i 2 := 1 to n 2 do for i 3:= 1 to n 3 do k := k + 1; Gi i: ð u tiên k đư c gá n giátr bng 0. Cĩ 3 vị ng l p l ng nhau. Sau m i l n l p c a vị ng for trong cù ng, giátrc a k t ăng thêm 1. Vi m i giátrc a i 1, vị ng for th hai th c hi n n 2 l n và v i m i giátrc a i 2vị ng for th 3 th c hi n n 3 l n. Vy theo nguyên lý nhân, sau khi c 3 vị ng l p k t thú c thìvị ng l p trong cù ng (i 3) th c hi n n 1.n 2.n 3 l n, nghĩ a là k = n 1.n 2.n 3. Chú ý rng nhi u bà i tố n đ m p h i gi i b ng cá ch k t h p c nguyên lý cng và nguyên lý nhân. Thí d: Tên bi n trong ngơn ng lp trì nh Pascal là mt xâu g m ch cá i ti ng Anh (khơng phân bi t ch cá i th ư ng và ch cá i hoa) và ch s, trong đĩ khơng đư c b t đu bng ch s. H i cĩ th đt đư c bao nhiêu tên bi n khá c nhau cĩđdà i khơng quá 2 ký t, bi t r ng cĩ 10 tkhốcĩđdà i 2 (ch ng h n nh ư to, do, go, if, or, in, ) Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 34
Gi i: G i A là tp tên bi n cĩ 1 ký t, thì N(A) = 26 (cĩ 26 tên bi n ng v i 26 ch cá i ti n Anh) G i B là tp tên bi n cĩ 2 ký t. Ký tđu cĩ 26 cá ch l a ch n, cị n ký t th hai cĩ 36 cá ch l a ch n (26 ch cá i và 10 ch s). Vy N(B) = 26.36 = 936. Do cĩ 10 xâu b “cm” nên t ng s tên bi n cĩđdà i khơng quá 2 ký tlà : 26 + 936 – 10 = 952 2. Ch nh h p.Hố n v . T hp. 2.1. Ch nh h p ðnh nghĩ a: M t ch nh h p ch p k c a n ph n t là mt b cĩ th t gm k ph n t ly t n ph n t đã cho (k ≤ n). k Scá c ch nh h p ch p k c a n ph n t , ký hi u là An , đư c tí nh theo cơng th c: n! Ak = n(n −1)(n − n( )2 − k + )1 = n (n − k)! Th t v y, vìcĩ n ph n t đã cho nên cĩ n cá ch ch n ph n t đng đu, ti p theo cĩ n – 1 cá ch ch n ph n t đng th hai, n – 2 ph n t đng th ba, , n – k + 1 cá ch ch n ph n t th k. Theo nguyên lý nhân đư c cơng th c c n ch ng minh. Thíd 1. Cĩ 10 vn đng viên thi ch y. H i cĩ bao nhiêu cá ch d đố n cá c v n đng viên v nh t, nhì , ba? Bi t r ng cá c v n đng viên đ u cĩcù ng kh năng nh ư nhau. Gi i: Scá ch d đố n là scá ch ch n cĩ th t 3 trong 10 vn đng viên, t c là : 3 A10 = 10. 9. 8 = 720 cá ch d đố n. 3 Thíd 2. Cĩ th lp đư c 9A9 = 9.9.8.7 = 4536 s nguyên cĩ 4 ch skhá c nhau. Thíd 3. Cĩ bao nhiêu đơ n ánh t tp h p A cĩ k ph n t và o t p h p B cĩ n ph n t (k ≤ n)? Gi i : Gi scá c ph n t c a t p h p A t ươ ng ng v i cá c s 1, 2, , k; khi đĩ mi k đơ n ánh chí nh là mt b cĩ th t các nh c a cá c ph n t c a t p h p A. Vy cĩ An cá c đơ n ánh t A và o B. 2.2. Hố n v : ðnh nghĩ a: M t hố n vc a n ph n t đã cho là mt cá ch s p x p cĩ th tc a n ph n t đĩ. D nh n ra r ng, m t hốn v c a n ph n t chính là m t ch nh h p ch p n c a n. Do đĩ: Scá c hố n vc a n ph n t , ký hi u P n , là : n Pn = An = n(n − 1 )1 = !n Thíd 1. M i cá ch x p hà ng (ngang ho c d c) c a 5 ng ư i là mt hố n vc a 5 ph n t. Vy cĩ P5 = 5! = 120 cá ch x p hà ng c a 5 ng ư i. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 35
Thíd 2. M t ng ư i ph i đi ki m tra 8 d a đim khá c nhau theo b t kỳ th tnà o. H i ng ư i đĩcĩ bao nhiêu cá ch đi n u b t đu t mt trong 8 đa đim đĩ sao cho m i đa đim đ u đư c ki m tra đúng m t l n. Gi i: Ng ư i đĩcĩ P7 = 7! = 5040 cá ch đi. 2.3. T hp ðnh nghĩ a: M t t hp ch p k c a n ph n t là mt cá ch ch n khơng k th t k ph n t t n ph n t đã cho (n ≥ k). k Scá c t hp ch p k c a n ph n t , ký hi u là Cn , đư c tí nh nh ư sau: Vi m i b k ph n t khơng s p th t tươ ng ng v i k! cá ch s p x p cĩ th t. Nĩ i cá ch khá c m i t hp ch p k c a n t ươ ng ng v i k! ch nh h p ch p k c a n. Tđĩ suy ra: A k n! Ak = !k Ck ⇒ C k = n = n n n k! k!()n − k ! Thíd 1. Cĩ 6 đi bĩ ng thi đu vị ng trị n m t l ư t. H i ph i t ch c bao nhiêu tr n đu? 2 Gi i: C 2 đi g p nhau m t tr n suy ra s tr n đu là C6 = 15 tr n Thíd 2. Tí nh s giao đim c a cá c đư ng ché o n m phí a trong m t đa giá c l i n c nh (n ≥ 4). Bi t r ng khơng c ĩ 3 đư ng ché o nà o đng quy t i 1 đim phí a trong đa giá c đĩ. Gi i: C 4 đnh c a đa giá c cho ta m t giao đim thomã n bà i tố n. Vy s đim c n đ m là : n(n − 1)(n − 2)(n − 3) C 4 = n 24 Thíd 3. Cho m t l ư i cĩ m.n ơ ch nh t. Cá c nú t đư c đánh s t 0 đ n n theo chi u t trá i sang ph i và t 0 đ n m theo chi u t dư i lên trên (xem hì nh v ). H i cĩ bao nhiêu đư ng đi khá c nhau t nú t (0,0) đ n nú t (n,m), bi t r ng m i b ư c đi là s d ch chuy n ho c sang ph i ho c lên trên c a m t ơ hì nh ch nh t (khơng d ch chuy n sang trá i ho c xu ng d ư i) (0,m) (n,m) (0,0) (n,0) Gi i: M t đư ng đi nh ư v y đư c xem là gm n+m b ư c, m i b ư c chđư c ch n mt trong hai giátrlà 0 nu đi lên và 1 nu đi sang ph i. Nh ư vy m i đư ng đi t ươ ng ng v i m t dã y nh phân cĩđdà i m+n trong đĩcĩđúng m giátr 1 (và tt nhiên cĩđúng n giátr 0). Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 36
Bà i tố n d n đ n vi c tì m xem cĩ bao nhiêu dã y nh phân cĩđdà i m+n trong đĩcĩ đúng m thà nh ph n 1. Nĩ i cá ch khá c là scá ch ch n m vtrí trong m+n vtríđ xp s 1. m n Vy s đư ng đi slà Cm+n (ho c Cm+n ) Thíd 4. Xé t đo n ch ươ ng trì nh ph ng Pascal sau: for i := 1 to n – 1 do for j := i + 1 to n do if a i > a j then begin { đi ch ai, a j } t : = a i ; a i := a j ; a j := t ; end; (ðây là mt trong các thu t tố n đ xp dã y s a1, a 2, , a n theo th t tăng d n) Hã y đ m s phé p so sá nh cá c a i đư c th c hi n trong đo n ch ươ ng trì nh trên. Gi i: T i m i vị ng l p i = k thì vịng l p j ph i th c hi n n – k + 1 bưc. Ngh ĩa là vi m i i = k ph i th c hi n n – k +1 phé p so sá nh (k = 2, 3, , n). Tđĩ theo nguyên lý cng, s cá c phé p so sá nh là : n(n −1) (n − 1) + (n − 2) + + 1 = 2 Cũ ng cĩ th gi i nh ư sau: Vì m i c p a i, a j (i ≠ j) đ u ph i so sá nh v i nhau, do đĩ 2 tng cá c phé p so sá nh là Cn . Mt và i tí nh ch t k T cơng th c tí nh Cn , d dà ng ch ng minh đư c: 0 n 1) Cn = Cn = 1 ; k n−k 2) Cn = Cn ; k k k −1 3) Cn = Cn −1 + Cn −1 ; k Tí nh ch t 3 chí nh là cơng th c truy h i đtí nh Cn . Ta cĩ : n\ k 0 1 2 3 4 5 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 37
Hay: 0 C0 0 1 C1 C1 0 1 2 C2 C2 C2 . . . 0 1 2 n Cn Cn Cn Cn Mi s h ng c a hà ng d ư i, tr sh ng đu và sh ng cu i b ng 1, b ng t ng 2 s hng hà ng trên cù ng c t và ct tr ư c c a s h ng c n tí nh, ng ưi ta th ưng g i chúng là các tam giác Pascal. B ng lý lu n t hp cĩ th ch ng minh đư c: n 0 0 1 2 2 n n (x +1) = Cn x + Cn x + Cn x + + Cn x . Tht v y, h sc a x k vph i c a cơng th c cĩđư c b ng cá ch nhân k s h ng x trong k nhân t (x + 1) vi n – k s 1 trong n – k nhân t (x + 1) cị n l i vtrá i. ðiu đĩ tươ ng ng v i s cá ch ch n k nhân t (x + 1) trong n nhân t vtrá i, s cá ch ch n đĩ k chí nh là Cn . Vy cơng th c đư c ch ng minh. T cơng th c trên, ta cĩ cơng th c nh th c Niu-tơn:  n n  k n k n n n  x  n k  x  k n x k k n−k ()x + y = y  + 1 = y ∑Cn   = ∑Cny k = ∑Cnx y  y  k=0  y  k=0 y k=0 Chúý 1. N u ch n x = y = 1, ta cĩ : 0 1 n 2 Cn + Cn + + Cn = 2 . k Tuy nhiên, Cn chí nh là scá c t p con cĩ k ph n t c a t p h p cĩ n ph n t . Vy, t ng s tp con (kc tp r ng vàchí nh t p h p đĩ) c a m t t p h p cĩ n ph n t là 2 n. Chúý 2. N u ch n x = 1, y = – 1, ta cĩ : 0 1 2 n n Cn − Cn + Cn + + (− )1 Cn = 0 . 2.4. Ch nh h p và T hp suy r ng a. Ch nh h p l p ðnh nghĩ a: Mt b cĩ th t gm k ph n t ly t n ph n t đã cho, trong đĩ mi ph n t cĩ th đư c l y nhi u l n đư c g i là mt ch nh h p l p ch p k t n ph n t đã cho. Chúý rng do m i ph n t cĩ th đư c l y nhi u l n nên r t cĩ th k > n. k Scá c ch nh h p l p ch p k c a n đư c ký ki u là A n và đư c tí nh theo cơng th c: k k A n= n Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 38
Th t v y, vì cĩ n cá ch ch n cho m i ph n t th i ( i = 1, 2, , k); nên theo quy t c nhân đư c cơng th c c n ch ng minh. Thíd 1. Tí nh s cá c dã y nh phân cĩđ dài n. Mi dã y nh phân cĩđdà i n là mt b cĩ th t gm n thà nh ph n đư c ch n trong tp {0, 1}. Do đĩ sdã y nh phân cĩđdà i n là 2n. 3 3 Thíd 2. Cĩ th lp đư c 9. A 10 = 9. 10 = 9000 s nguyên d ươ ng cĩ 4 ch s. Thíd 3. Cĩ bao nhiêu ánh x t tp h p A cĩ k ph n t và o t p h p B cĩ n ph n t ? Lý lu n t ươ ng t nh ư thídtí nh s đơ n ánh trong m c ch nh h p; do m i ph n t c a tp h p B cĩ th là nh c a nhi u ph n t thu c A nên s á nh xcĩ th cĩlà nk. Thíd 4. Trong ngơn ng Pascal chu n quy đnh tên bi n khơng quá 8 ký t (mi ký tlà mt trong 26 ch cá i ti ng Anh ho c m t trong 10 ch s) vàph i b t đu b ng m t ch cá i, ký tlà ch khơng phân bi t ch hoa và ch th ư ng. H i cĩ th đnh nghĩ a đư c bao nhiêu bi n khá c nhau? Gi i: T t c cĩ 8 lo i bi n: 1 ký t, 2 ký t, , 8 ký t . Theo quy t c nhân thì s bi n cĩ k ký tlà 26.36 k – 1 , (k = 1, 2, , 8). Tđĩá p d ng quy t c c ng đư c s cá c bi n khá c nhau trong ngơn ng Pascal là : 26(1 + 36 + 36 2 + + 36 7) = 2 095 681 645 538 ≈ 2. 10 12 . ðây là mt con s rt l n, khơng th nà o duy t h t đư c chú ng. Hi n t ư ng cá c s t hp t ăng nh ư vy g i là hi n t ư ng bù ng n t hp. S k ý t 1 2 3 4 5 6 7 S bi n 26 962 34 658 1 247 714 44 917 730 1 617 038 306 58 213 379 042 b. T hp l p ðnh nghĩ a: M t t hp l p ch p k c a n ph n t là mt cá ch ch n khơng k th t k ph n t t n ph n t đã cho, trong đĩ mi ph n t cĩ th đư c ch n nhi u l n. Chúý rng do m i phn t cĩ th đư c l y nhi u l n nên r t cĩ th k > n. Cĩ rt nhi u bà i tố n đ m ph i s d ng khá i ni m t hp l p. Ch ng h n, trong h p cĩ 3 lo i bi: bi đ, bi xanh và bi tr ng; m i lo i cĩí t nh t 4 viên. H i cĩ bao nhiêu cá ch l y ra 4 viên bi t hp đĩ, n u khơng phân bi t th t ly vàcá c viên bi l y ra cĩ th cù ng 1 lo i. Gi i: Cĩ th li t kê cá c cá ch l y nh ư sau: 4 bi đ 4 bi xanh 4 bi tr ng 3 bi đ, 1 bi xanh 3 bi đ, 1 bi xanh 3 bi xanh, 1 bi đ 3 bi xanh, 1 bi tr ng 3 bi tr ng, 1 bi đ 3 bi tr ng, 1 bi xanh 2 bi đ, 2 bi xanh 2 bi đ, 2 bi tr ng 2 bi xanh, 2 bi tr ng 2 bi đ, 1 bi xanh, 2 bi xanh, 1 bi đ, 2 bi tr ng, 1 bi đ, 1 bi tr ng 1 bi trng 1 bi xanh Cĩ tt c 15 cá ch l y 4 bi t h p đã cho. Mi cá ch l y nh ư vy là mt t hp l p ch p 4 t 3 ph n t đã cho. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 39
Chú ng ta khơng th tí nh s t hp l p ch p k t n ph n t mt cá ch th cơng nh ư vy, bi khơng ph i lú c nà o cũ ng li t kê ht cá c t hp đĩđư c. Gi s mt h p cĩ 3 ng ăn đ đng 3 lo i bi khá c nhau: * * bi đ bi xanh bi tr ng bi đ bi xanh bi tr ng Vi c ch n 4 bi t ươ ng ng v i vi c đt 4 bi và o trong 3 ng ăn đã cho. Lo i tr 2 vá ch ng ăn ngồ i cù ng là cđnh, cịn 2 vách ng ăn phía trong và 4 viên bi cĩ th đ i ch cho nhau. Nh ư vy s cá ch ch n 4 bi t ươ ng ng v i s cá ch ch n 4 trong 6 v trí đ đ t 4 bi. 4 Nĩ i cá ch khá c s cá ch ch n 4 bi là C6 = 15 Khái quát cĩ th l p lu n nh ư sau: M i t h p l p ch p k c a n ph n t cĩ th xem nh ư cách x p k d u * vào m t h p cĩ n ng ăn, trong đĩ các vách ng ăn h p và các d u * cĩ th d ch chuy n đưc tr hai vách ng ăn hai đu h p là c đ nh. Nh ư v y m i t h p l p ch p k c a n ph n t chính là s cách ch n k v trí trong n + k – 1 (g m k v trí đ t d u * và n – 1 vách ng ăn) đ đ t k d u *. V y, ký hi u s các t h p l p ch p k c a n ph n t là k C n , ta cĩ: k k C n = Cn+k−1 Thíd 1. M t c a hà ng cĩ 4 lo i bá nh h p khá c nhau. H i cĩ bao nhiêu cá ch ch n 6 hp bá nh? 6 6 6 Gi i: Theo khá i ni m t hp l p, ta cĩ C 4= C4+6−1 = C9 = 84 cá ch ch n. Thíd 2. Cĩ bao nhiêu cá ch ch n 5 t ti n t 7 lo i ti n gi y 1000 đ, 2000 đ, 5000 đ, 10 000 đ, 20 000 đ, 50 000 đ và 100 000 đ? 5 5 Gi i: S cá ch ch n là C 7= C11 = 462. Thíd 3. Ph ươ ng trì nh x + y + z = 11 cĩ bao nhiêu nghi m nguyên khơng âm? Gi i: M i nghi m c a ph ươ ng trì nh ng v i m t cá ch phân chia 11 ph n t (11 s 1) đã cho thành ba lo i, sao cho cĩ x ph n t lo i 1, y ph n t lo i 2 và z ph n t lo i 3. Vì vy s nghi m c a ph ươ ng trình b ng s t hp l p ch p 11 t tp cĩ 3 lo i ph n t , nghĩ a làcĩ : 11 11 C 3 = C3+11 −1 = 78 nghi m. Cĩ th tì m đư c nghi m c a ph ươ ng trì nh đã cho v i cá c điu ki n rà ng bu c c a cá c n s . Ch ng h n tì m s nghi m nguyên khơng âm c a ph ươ ng trì nh đã cho trên tho mã n điu ki n: x ≥ 1; y ≥ 2; z ≥ 3. Khi đĩ mt nghi m c a ph ươ ng trì nh ng v i m t cá ch phân chia 11 ph n t đã cho thành 3 lo i, sao cho cĩ x ph n t lo i 1, y ph n t lo i 2 và z ph n t lo i 3 trong đĩcĩí t nh t 1 ph n t lo i 1 (x đã cĩ sn m t s 1), cĩí t nh t 2 ph n tlo i 2 vàcĩí t nh t 3 ph n t lo i 3. Vì th tr ư c h t ch n 1 ph n t lo i 1, 2 ph n t lo i 2 và 3 ph n t lo i 3; cịn l i 5 ph n t đưc chia ti p cho ba lo i. Do đĩ s nghi m c a ph ươ ng trì nh là s t hp l p ch p 5 t 3 lo i ph n t đã cho: 5 5 C 3= C7 = 21 (nghi m) Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 40
c. Hốn v c a các t p h p cĩ các ph n t gi ng nhau Trong các bài tốn đm, m t s ph n t c a t p h p đã cho cĩ th gi ng nhau. Khi đĩ ph i c n th n k o ta đ m chúng nhi u h ơn m t l n. Thí d : Cĩ th l p đưc bao nhiêu xâu khác nhau b ng cách s p x p l i các ch cái trong c m t NHANDANANHHUNG (nhân dân anh hùng)? Gi i: Trong t đã cho cĩ 14 ch cái g m 5 ch N, 3 ch H, 3 ch A và các ch D, U, G. L ra cĩ 14! cách s p x p, nh ưng trong m i cách s p x p n u đ i ch 5 ch N (cĩ 5! cách đi ch ), đ i ch 3 ch H (cĩ 3! cách đ i ch ) và đi ch 3 ch A (cĩ 3! cách đ i ch ), thì xâu thu đưc là khơng đi. V y n u g i s xâu thu đưc là m thì theo nguyên lý nhân, ta cĩ: m.5!.3!.3! = 14! 14 ! T đĩ s các xâu khác nhau cĩ đưc là: m = = 28 180 160 5!. 3!. 3! B ng lý lu n t ươ ng t ta cĩ: S hốn v c a n ph n t trong đĩ cĩ n 1 ph n t gi ng nhau thu c lo i m t, n 2 ph n t gi ng nhau thu c lo i hai, , n k ph n t gi ng nhau thu c lo i k (n 1 + n 2 + + n k ≤ n) là: !n n1! n2! nk! Chú ý: Cĩ nhi u cách đ suy ra cơng th c tính s hốn v l p. Ch ng h n, trong n v n1 trí ta ch n n 1 v trí đ x p các ph n t lo i m t, nh ư v y cĩ Cn cách ch n; sau đĩ ch n n 2 n2 v trí trong n – n 1 v trí cịn l i đ x p các ph n t lo i hai, t c là cĩ C ; v.v T đĩ n −n1 dùng nguyên lý nhân và cơng th c tính s t h p đưc k t qu nh ư đã bi t. d. S phân chia các t p h p thành các t p con khác nhau Tr ưc h t xét thí d : Cĩ bao nhiêu cách chia m t c bài 52 quân cho 4 ng ưi sao cho mt ng ưi đưc 10 quân, nh ng ng ưi khác l n l ưt đưc 8, 8, 7 quân? 10 Gi i: Ng ưi đ u tiên nh n 10 quân bài cĩ C52 cách nh n khác nhau, cịn l i 42 quân 8 nên ng ưi ti p theo cĩ C42 cách nh n 8 quân bài, cịn l i 34 quân bài nên ng ưi th ba cĩ 8 7 C34 cách nh n 8 quân bài, và ng ưi cu i cùng cĩ C26 cách nh n 7 quân bài. Theo nguyên lý nhân thì s cách chia các quân bài th a mãn đu bài là: 52 ! 42 ! 34 ! 26 ! 52 ! 31 C10 C8 C8 C7 = = ≈ 2,23.10 . 52 42 34 26 10 !42! 8!34! 8!26! 7!19! 10 !8!8!7!19! Tng quát, ta cĩ: S cách phân chia mt t p h p g m n ph n t thành k t p sao cho tp con th i cĩ n i ph n t ( n 1 + n 2 + + n k = n) là: !n n1! n 2! n k! Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 41
Chú ý là cơng th c v a l p đưc cho th y th t các t p con khơng nh h ưng đ n k t qu phân chia t p h p đã cho. 3. Nguyên lýbù tr . Nu khơng cĩgi thi t A, B là 2 tp h p r i nhau, ta cĩ nguyên lý cng t ng quá t: N(A ∪ B) = N(A) + N(B) – N(A ∩ B) (1) Rõrà ng, n u A, B r i nhau thì A ∩ B = ∅ nên N(A ∩ B) =0 vàđưc nguyên lý cng đơ n gi n (m c 1.1): N(A ∪ B) = N(A) + N(B) Cơng th c (1) cịn g i là nguyên lýbù tr cho 2 tp h p. Tng quá t h ơn, ta cĩ : ðnh lý :Gi s A1, A 2, , A nlà n t p h p h u h n. Khi đĩ: N(A 1 ∪ A2 ∪ ∪ An ) = n n−1 = ∑N(A i ) − ∑ N(A i ∩ A j ) + ∑ N(A i ∩ A j ∩ Ak ) + + (−1) N(A 1 ∩ A2 ∩ ∩ An ) i=1 i ≠ j i≠ j≠k (2) 2 Ch ng minh: Chúng ta bi t r ng s cá c t p giao A i ∩ A j là Cn , s cá c t p giao 3 r Ai∩Aj∩Aklà Cn , . Tng quá t s cá c t p giao c a r t p là Cn , r = 1, 2, ,n. Cơng th c (2) đưc ch ng minh b ng cá ch ch ra r ng, m i ph n t c a t p h p A 1 ∪ A2 ∪ ∪ A n đư c đ m đúng m t l n vph i c a (2). Xé t ph n t tuỳý x c a t p h p A 1 ∪ A 2 ∪ ∪ A n . Gi s x cĩ mt trong r t p c a 1 A1, A 2, , A n trong đĩ r = 1, 2, , n. Ph n t x nà y đư c đ m Cr l n trong t ng ΣN(A i), 2 đ m Cr trong t ng ΣN(A i∩Aj), Bi v y t ng cá c l n đ m c a x vph i c a (2) là : 1 2 3 r r 1 2 3 r r Cr − Cr + Cr − + (− )1 Cr = 1− 1[ − Cr + Cr − Cr + + (− )1 Cr ] = 1 – (1 – 1)r = 1 Vy x đư c đ m đúng m t l n trong v ph i c a (2). ðnh lýđư c ch ng minh. Cĩ th vi t cơng th c (2) dư i d ng khá c: ð ng nh t t p A i v i tí nh ch t A i cho trên mt t p h p X nà o đĩvàph i đ m xem cĩ bao nhiêu ph n t c a X khơng thomã n b t c tí nh ch t A i nà o (i = 1, 2, , n) G i N *là s cn đ m; N = N(X) ( là s ph n t c a X), ta cĩ : * n N = N – N(A 1 ∪ A 2 ∪ ∪ A n) = N – N 1 + N 2 – + (–1) Nn . (3) trong đĩ Nklà tng cá c ph n t c a X thomã n k tí nh ch t l y t n tí nh ch t đã cho. Thíd 1: Trong m t l p h c cĩ 50 sinh viên thìcĩ 30 ng ư i bi t ti ng Anh, 20 ng ư i bi t ti ng Phá p, trong s sinh viên bi t ngo i ng cĩ 10 ng ư i bi t c ti ng Anh và ti ng Phá p. H i trong l p cĩ bao nhiêu sinh viên khơng bi t c ti ng Anh và ti ng Phá p? Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 42
Gi i: Theo cơng th c (1), ta cĩ s sinh viên bi t ít nh t 1 trong 2 th ti ng Anh, Phá p là : 30 + 20 – 10 = 40 ⇒ s sinh viên khơng bi t c ti ng Anh và ti ng Phá p là 10 ng ư i. Thíd 2. Cĩ bao nhiêu xâu nh phân cĩđdà i 8 ho c b t đu b ng 1 ho c k t thú c bng 00? Gi i: Do vtríđu tiên là cđnh, chcĩ 1 cá ch ch n duy nh t, m i m t trong 7 v trí ti p theo cĩ 2 cá ch ch n (0 ho c 1), suy ra s xâu nh phân cĩđdà i 8 bt đu b ng 1 là 27 = 128 xâu. Tươ ng t s xâu nh phân cĩđdà i 8 kt thú c b ng 00 là 26 = 64 và s xâu nh phân cĩđdà i 8 bt đu b ng 1 và kt thú c 00 là 25 = 32. V y, s xâu nh phân cĩđdà i 8 ho c b t đu b ng 1 ho c k t thú c b ng 00 là 128 + 64 – 32 = 160 (xâu) Thíd 3. Cĩ bao nhiêu s nguyên d ươ ng khơng l n h ơn 100 ho c chia h t cho 4 ho c chia h t cho 6 nh ưng khơng đng th i chia h t cho c 4 và 6? 100 Gi i: S cá c s chia h t cho 4 là : = 25,  4  100 Scá c s chia h t cho 6 là : = 16 ,  6  100 Scá c s đng th i chia h t cho c 4 và 6 là : = 8  12  Vy s cn tì m là : 25 + 16 – 8 = 33. Thíd 4. Cĩ bao nhiêu s nguyên nh hơn ho c b ng 1000 khơng chia h t cho b t c snà o trong cá c s 3, 4, 5? Gi i: G i X làcá c s nguyên d ươ ng nh hơn ho c b ng 1000 thì N(X) = 1000. A i = {x ∈ X | x chia h t cho i }, i = 3, 4, 5. Khi đĩ A3 ∪A4 ∪ A 5là tp cá c s trong X chia h t cho ít nh t m t trong cá c s 3, 4, 5 và : N(A 3 ∪A4 ∪ A 5) = N 1 – N 2 + N 3 . Ta cĩ : N 1 = N(A 3) + N(A 4) + N(A 5) = 1000 1000 1000 = + + = 333 + 250 + 200 = 783  3   4   5  N 2 = N(A 3 ∩ A 4) + N(A 3 ∩ A 5) + N(A 4 ∩ A 5) = 1000 1000 1000 = + + = 83 + 66 + 50 = 199  3.4   3.5   4.5  1000 N 3 = N(A 3 ∩ A 4 ∩ A 5) = = 16 3.4.5 T đĩcĩđáp s c a bà i tố n là : 1000 – N1 + N 2 – N 3 = 400. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 43
Thíd 5. Bà i tố n b th ư Cĩ n phong bì ghi s n đa chvà n lá th ư vi t cho n đa chđĩ. B ng u nhiên cá c lá th ư và o cá c phong bì (mi lá th ư cho và o 1 phong bì ). Hã y tì m xem cĩ bao nhiêu cá ch b th ư sao cho khơng cĩlá th ư nà o đư c bđúng đa ch . Gi i: S cá ch b th ư và o phong bìlà n!. Nĩ i cá ch khá c, n u g i X là tt ccá c cá ch b th ư và o phong bìthì N(X) = n! . G i A klàtí nh ch t cĩ k lá th ư bđúng đa ch . G i N*là scá ch b th ư sao cho khơng cĩlá th ư nà o đúng đa ch . * n Theo cơng th c (3), ta cĩ : N = n! – N 1 + N 2 – + (–1) Nn , trong đĩ Nklà s tt ccá c cá ch b th ư sao cho cĩ k lá th ư bđúng đa ch . k ðtí nh s Nk ta lý lu n nh ư sau: Cĩ Cn cá ch l y k lá th ư, m i cá ch l y k lá th ư cĩ (n – k)! cá ch b k lá th ư nà y đúng đa ch (vì khi đĩ n – k lá th ư cịn l i đưc b tùy ý), do đĩ: n! N = C k (n − k)!= k n k!  n  *  1 1 (−1)  Tđĩ: N = n!1 − + −Λ +   1! 2! n!  * S N trong bà i tố n b th ư đư c g i là s mt th t, ký hi u là Dn. Dư i đây là mt và i giátrc a D n: n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133 496 1 334 961 4 890 741 S m t th t D n t ăng r t nhanh, ng ư i ta g i đĩlà hi n t ưng bù ng n t hp. 4. Gi i cá c h th c truy h i Th ư ng cá c bà i tố n đ m ph th ư c và o tham s đu và o là s t nhiên n, ch ng h n nh ư s t hp, s ch nh h p, s mt th t, Vi c bi u di n t ư ng minh cá c k t qu nà y nh ư mt hà m c a s t nhiên n g i là cơng th c tr c ti p. Trong nhi u tr ư ng h p vi c tì m cơng th c tr c ti p nh ư th làkhĩ kh ăn. Cĩ mt ph ươ ng phá p bi u di n k t quđ m đư c ng v i gi átrđu và o thơng qua cá c giátrđu và o nh hơn và cơng th c tí nh thu đư c g i là cơng th c truy h i. Cá c giátrđu tiên mà k tđĩ cơng th c truy h i cĩ hi u lc g i làgiátr ban đu c a cơng th c truy h i (xem l i đ nh ngh ĩa trong 6.1. ch ươ ng 1). k Thíd :Cĩ th tí nh s t hp Cn nh ư sau: Ch n m t ph n t a c đnh trong n ph n t đang xé t. Khi đĩ, n u a đư c ch n và o t hp t hìph i ch n thêm k – 1 ph n t k−1 na t n – 1 ph n t cị n l i, s cá ch ch n trong tr ư ng h p nà y là Cn−1 ; cị n n u a khơng đư c ch n và o t hp thìph i ch n c k ph n t trong n – 1 ph n t cị n l i, s cá ch ch n k trong tr ư ng h p nà y là Cn . Theo quy t c c ng ta cĩ : k k−1 k Cn = Cn−1 + Cn−1 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 44
k 0 1 đĩlà cơng th c truy h i tí nh s Cn . Cá c giátr ban đu c a cơng th c nà y là C1 = C1 = 1. Dưi đây chúng ta xét m t s ph ươ ng pháp đư a cơng th c truy h i v cơng th c tr c ti p. 4.1. Ph ươ ng phá p kh đtì m cơng th c tr c ti p t cơng th c truy h i Ph ươ ng phá p nà y đưc xét qua m t s thíd sau: Thíd 1: Bà i tố n chia m t ph ng. Trên m t ph ng, k n đư ng th ng sao cho khơng cĩ 2 đư ng nà o song song và khơng cĩquá 2 đư ng th ng đng quy t i m t đim. H i m t ph ng đư c chia thà nh bao nhiêu ph n? Gi i: G i s ph n c a m t ph ng đư c chia b i n đư ng th ng nh ư vy là S n. Gi s đãkđư c n – 1 đư ng th ng, k thêm đư ng th ng th n thì s ph n đư c thêm s bng s giao đim đư c thêm c ng 1. S giao đim đư c thêm là s giao đim màđư ng th ng va k ct n – 1 đư ng th ng k tr ư c đĩ, nghĩ a là bng n – 1. Tđĩ nh n đư c cơng th c truy h i: Sn = S n – 1 + n ; n ≥ 1; S 0 = 1. (S 0làgiátr ban đu) T cơng th c trên, d dàng tí nh đư c: S1 = 1 + 1 = 2, S2 = 2 + 2 = 4, S3 = 4 + 3 = 7 S4 = 7 + 4 = 11, S5 = 11+ 5 = 16, S6 = 16 + 6 = 22, ðtì m cơng th c tr c ti p, ta cĩ : S0 = 1 S1 = S 0 + 1 S2 = S 1 + 2 S3 = S 2 + 3 . . . . . . Sn = S n – 1 + n Cng v vi v c a cá c đng th c trên đư c: n(n −1) n2 + n + 2 Sn = S 0 + 1 + 2 + 3 + + n = 1 + = 2 2 Thíd 2: Bà i tố n lã i ké p. M t ng ư i g i ti t ki m 10 tri u đng v i lã i su t hà ng n ămlà 10%. Ht m t n ăm g i ti n, n u khơng rú t ti n ra ng ư i đĩđư c c ng s lã i và o g c đ tí nh lã i cho n ăm ti p theo (lã i ké p). H i sau 20 năm g i khơng rút ra l n nào thì s ti n c a ng ư i đĩlà bao nhiêu? Gi i: G i P nlà s ti n c a ng ư i đĩ sau n n ăm g i, khi đĩ s ti n c a ng ư i đĩ bng s ti n c a n ăm th n – 1 cng v i lã i su t c a n ăm th n. Nh ư vy: Pn = P n – 1 + 0,1 P n – 1 = 1,1 P n – 1 . ðĩlà cơng th c truy h i tí nh s ti n sau n n ăm g i c a ng ư i đĩ. Giátr ban đu c a bà i tố n là P0 = 10 (tri u). Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 45
Th ln l ư t P n – 1 = 1,1 P n – 2 và o P n , P n – 2 = 1,1 P n – 3 và o P n – 2 ; Cu i cù ng ta cĩ : n Pn = 1,1 P 0. 20 Sau 20 năm s ti n c a ng ư i đĩlà : P 20 = 1,1 .10 ≈ 6,7275. 10 = 67,275 tri u đng. Thíd 3: Bà i tố n thá p Hà ni. T ươ ng truy n r ng, t i m t ngơi chù a Hà ni cĩ mt t m đ bng đng, trên đĩcĩ 3 cá i c c b ng kim c ươ ng. Lú c khai thiên l p đa, trên m t trong 3 cá i c c đĩð c Ph t đãđ 64 chi c đĩa b ng và ng v i đư ng kí nh nh dn (hì nh 1). Ngà y đêm cá c nhà sư ph i d ch chuy n đĩa sang m t c c khá c theo nguyên t c: mi l n chđư c chuy n 1 đĩa t c c nà y sang c c khá c b t kỳ nh ưng khơng đư c đt m t chi c đĩa to lên trên m t chi c đĩa khá c nh hơn. H i ph i m t bao lâu cá c nhà sư mi chuy n h t s đĩa sang m t c c khá c, bi t rng m i l n chuy n 1 đĩa h t 1 giây? Hình 1. Tr ng thá i ban đu Hình 2. Tr ng thá i sau H n–1 ln chuy n Gi i: G i H n là s ln d ch chuy n đĩa n u c c ban đu cĩ n đĩa. Gi slú c đu n đĩa trên c c 1 (hình 1). Sau H n – 1 l n d ch chuy n các nhà sư đã chuy n đư c n – 1 đĩa sang c c 3 (hì nh 2). Tđây ph i cĩ 1 ln chuy n chi c đĩa l n nh t tc c 1 sang c c 2 và Hn – 1 l n d ch chuy n n – 1 chi c đĩa t c c 3 sang c c 2. Nh ư vy, ta cĩ : Hn = 2 H n – 1 + 1 đĩlà cơng th c truy h i đtí nh s l n d ch chuy n n đĩa t c c nà y sang c c khá c. D th y giátr ban đu là H1 = 1 (c c chcĩ 1 đĩa). Chúng ta tì m cơng th c tr c ti p tí nh H n. Ta cĩ : 2 H n = 2 H n – 1 + 1 = 2 (2 H n – 2 + 1) + 1 = 2 H n – 2 + 2 + 1 = 2 3 2 = 2 (2 H n – 3 + 1) + 2 + 1 = 2 H n – 3 + 2 + 2 + 1 = . . . . . n – 1 n – 2 = 2 H1 + 2 + + 2 + 1 = = 2 n – 1. Vi 64 chi c đĩa đã cho, cá c nhà sư ph i d ch chuy n: 64 18 H64 = 2 – 1 = 18,4467.10 (hơn 18 tt ln) Nu m i l n d ch chuy n h t 1 giây, cá c nhà sư cn kho ng 580 t năm m i hồ n thà nh vi c chuy n 64 đĩa t c c nà y sang c c khá c. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 46
Thíd 4: L p cơng th c truy h i tí nh s mt th t Dn. Gi i: ðánh s th ư và phong bì t 1 đ n n, th ư th i đúng v i đa ch phong bì i . Mt cá ch b th ư đng nh t v i m t hố n v (a 1, a 2, , a n) c a (1, 2, , n). Mt cá ch m t th t là mt hố n v (a 1, a 2, , a n) sao cho a i ≠ i, ∀i. Thà nh ph n a 1 c a hố n vcĩ th nh n n – 1 giátrngồ i s 1. Vi m i giátr k c a a 1 (k ≠ 1) cĩ th x y ra 2 tr ư ng h p: 1) ak = 1, khi đĩcá c thà nh ph n cị n l i đư c xá c đnh nh ư scá ch m t th t c a n – 2 ph n t , s nà y chí nh là Dn – 2 . 2) ak ≠ 1, khi đĩcá c thà nh ph n cị n l i đư c xá c đnh nh ư scá ch m t th t c a n – 1 ph n t (xem giátr 1 nh ư làgiátr k), s nà y chí nh là Dn – 1 . T đĩ cĩ cơng th c truy h i: Dn = (n – 1)(D n – 2 + D n – 1 ) , n ≥ 3 . Cá c giátr ban đu cĩ th tí nh tr c ti p t đnh nghĩ a vàđư c D 1 = 0, D 2 = 1. Nu coi D 0 = 1 thì cơng th c truy h i trên đúng ∀n ≥ 2. Ta cĩ : D 3 = (3 – 1)(0 + 1) = 2 , D4 = (4 – 1)(1 + 2) = 9, D 5 = (5 – 1)(2 + 9) = 44 , D6 = (6 – 1)(9 + 44) = 265, Cĩ th đư a cơng th c truy h i trên v cơng th c tr c ti p nh ư sau: Dn = (n – 1)(D n – 2 + D n – 1 ) ⇔ D n – nD n – 1 = – [D n – 1 – (n – 1)D n – 2 ] ð t I n = D n – nD n – 1 . Ta cĩ : n – 1 n Dn – n D n – 1 = I n = – I n – 1 = I n – 2 = = (–1) I1 = (–1) . Chia c 2 v cho n! , đư c: D D (−1)n n − n−1 = , ∀n ≥ 2 n! (n −1)! n! Cng v vi v c a h th c trên đưc : D 1 2 (−1)n  1 1 (−1)n  n ⇒   = 1 − + + + Dn = n!1− + + +  n! 1! 2! n!  1! 2! n!  Cơng th c thu đưc là cơng th c đã đã bi t trong thíd 5, m c 3 (Nguyên lýbù tr ). 4.2. Gi i cá c h th c truy h i tuy n tí nh. Trong ph n nà y xé t cá ch tì m cơng th c tr c ti p t cơng th c truy h i cĩd ng đc bi t g i làd ng tuy n tí nh. a. Cá c khá i ni m ðnh nghĩ a: Cơng th c truy h i tuy n tí nh thu n nh t b c k cĩ h s hng s là cơng th c truy h i cĩd ng: an = c 1 a n – 1 + c 2 a n – 2 + + c k a n – k (1) trong đĩ c1, c 2, , c klàcá c s th c (hng s ) và ck ≠ 0. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 47
S dĩ cĩ thu t ng “cơng th c truy h i b c k” vì sh ng a n đư c tí nh qua k s h ng tr ư c nĩ . Cá c giátr ban đu c a cơng th c truy h i trên g m k giátr : a 0, a 1, , a k – 1 . Cĩ th tì m cơng th c tr c ti p tí nh a n d ư i d ng: n a n = r . (2) Trong đĩ r là mt s th c c n xá c đnh. Dã y { a n } xá c đnh theo (2) sthomã n (1) nu r là nghi m c a ph ươ ng trì nh: n n – 1 n – 2 n – k r = c 1 r + c 2 r + + c k r . n n – 1 n – 2 n – k hay: r – c1 r – c 2 r – – c k r = 0. (3) Ph ươ ng trì nh (3) g i là ph ươ ng trì nh đc tr ưng c a cơng th c (1), và nghi m c a (3) g i là nghi m đc tr ưng. Tr ưc h t xé t v i k = 2, t c là cơng th c truy h i tuy ntí nh b c hai: an = c 1 a n – 1 + c 2 a n – 2 . Ph ươ ng trì nh đc tr ưng c a cơng th c truy h i tuy n tí nh b c hai là: 2 r – c 1 r – c 2 = 0 b. Gi i cơng th c truy h i tuy n tí nh b c hai khi ph ươ ng trì nh đc tr ưng cĩ 2 nghi m phân bit. 2 ðnh lý 1: Cho c 1, c 2là hai s th c. Nu ph ươ ng trì nh đc tr ưng r – c 1 r – c 2 = 0 cĩ hai nghi m th c phân bi t r 1, r 2thìđiu ki n c n vàđđdã y s {a n } là nghi m c a cơng th c truy h i: an = c 1 a n – 1 + c 2 a n – 2 n n là: an = α1 r 1 + α2 r 2 , n = 1, 2, trong đĩ α1, α2làcá c s th c cĩ th xá c đnh đư c nh cá c điu ki n ban đu c a cơng th c truy h i. Ch ng minh: ðiu ki n c n: N u r 1, r 2là 2 nghi m c a ph ươ ng trì nh đc tr ưng, ta ph i ch ng minh n n a n = α1 r 1 + α2 r 2 . vi α1, α2làcá c h ng s thomã n cơng th c truy h i a n = c 1 a n – 1 + c 2 a n – 2 . 2 2 Th t v y: Ta cĩ : r 1 – c 1 r 1 – c 2 = 0 và r2 – c 1 r 2 – c 2 = 0 2 2 hay: r 1 = c 1 r 1 + c 2và r2 = c 1 r 2 + c 2 n – 1 n – 1 n – 2 n – 2 Tđĩ: an = c 1 a n – 1 + c 2 a n – 2 = c 1(α1 r 1 + α2 r 2 ) + c 2(α1 r 1 + α2 r 2 ) = n – 2 n – 2 = α1 r 1 (c 1 r 1 + c 2) + α2 r 2 (c 1 r 2 + c 2) = n – 2 2 n – 2 2 = α1 r 1 r 1 + α2 r 2 r 2 = n n = α1 r 1 + α2 r 2 . ðiu ki n đ: Gi s { a n } là mt dã y b t kỳthomã n h th c truy h i a n = c 1 a n – 1 + c 2 a n – 2 . Ta n n ph i ch ng minh r ng sch n đư c cá c s α1 , α2 sao cho a n = α1 r 1 + α2 r 2 . Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 48
Th t v y, gi s a0và a1là 2 giátr ban đu c a h th c truy h i. Ta cĩ :  a = α + α  0 1 2  a1 = α1r1 + α2 r2 ðây là h ph ươ ng trì nh tuy n tí nh 2 n Cramer, nĩ cĩ nghi m duy nh t: a1 − r2a0 a0r1 − a1 α1 = ; α2 = r1 − r2 r1 − r2 n n V y a n = α1 r 1 + α2 r 2 đư c xá c đnh. Thíd :Dã y Fibonacci, nh ư đã bi t đư c xá c đnh b i cơng th c truy h i: Fn = F n – 1 + F n – 2 ; F 0 = 0 ; F 1 = 1. ðĩlà cơng th c truy h i tuy n tí nh b c hai cĩ h s khơng đi. Ta đi tì m cơng th c tr c ti p tí nh F n. Gi i: Ph ươ ng trì nh đc tr ưng c a cơng th c là : 1 ± 5 r2 − r − 1 = 0 ⇔ r = 1,2 2 Tđĩ, theo đnh lý 1, ta cĩ :  n  n 1+ 5  1− 5  Fn = α1  + α2    2   2  Thay cá c điu ki n ban đu F 0 = 0, F 1 = 1 và o đư c h ph ươ ng trình:  α + α = 0  1 2 1+ 5 1+ 5  α + α = 1  2 1 2 2 1 1 Gi i h ph ươ ng trình nà y đư c nghi m: α = ; α = - 1 5 2 5  n  n 1 1+ 5  1 1− 5  V y: Fn =   −   . 5  2  5  2  c. Gi i cơng th c truy h i tuy n tí nh b c hai khi ph ươ ng trì nh đc tr ưng cĩ nghi m ké p 2 ðnh lý 2: Cho c 1, c 2là hai s th c. Nu ph ươ ng trì nh đc tr ưng r – c 1 r – c 2 = 0 cĩ nghi m ké p r 0thìđiu ki n c n vàđđdã y s {a n } là nghi m c a cơng th c truy h i: an = c 1 a n – 1 + c 2 a n – 2 n n là : an = α1 r 0 + α2 n r 0 , n = 1, 2, trong đĩ α1, α2làcá c s th c cĩ th xá c đnh đư c nh cá c điu ki n ban đu c a cơng th c truy h i. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 49
Vi c ch ng minh đnh lý 2 tươ ng t ch ng minh đnh lý 1. Thíd : Tì m nghi m c a cơng th c truy h i: an = 6a n – 1 – 9an – 2 ; a 0 = 1, a 1 = 6. Gi i: Ph ươ ng trì nh đc tr ưng r 2 – 6r + 9 = 0 cĩ nghi m ké p r = 3. n n V y a n cĩd ng: a n = α1 3 + α2 n 3 . Thay n = 0 , n = 1, ta c ĩ:  α1 = a 0 = 1  ⇔ α1 = α2 = 1 3α1 + 3α2 = a1 = 6 n n n Vy: a n = 3 + n3 = (n + 1)3 . d. Chú thích Cĩ th m r ng đ nh lý 1 cho h th c truy h i tuy n tính b c k nh ư sau: Cho c 1, c 2, , c k là các s th c. Gi s ph ươ ng trình đc tr ưng: k k – 1 r – c 1 r – – c k – 1 r – c k = 0 cĩ k nghi m phân bi t r 1, r 2, , r k . Khi đĩ điu ki n c n và đ đ dãy {a n} là nghi m c a cơng th c truy h i: a n = c 1 an -1 + c 2 an - 2 + + c k a n - k n n n là: a n = α1 r 1 + α2 r2 + + αk rk trong đĩ α1, α2, , αk là các s th c cĩ th xác đ nh đưc nh các điu ki n ban đ u c a cơng th c truy h i đã cho. Thí d : Tìm nghi m c a cơng th c truy h i: an = 6a n – 1 – 1a n – 2 + 6a n – 3 ; a 0 = 2, a 1 = 5, a 2 = 15. Gi i: Ph ươ ng trình đc tr ưng c a cơng th c truy h i đã cho là: r3 – 6r 2 + 11r – 6 = 0 Các nghi m c a ph ươ ng trình đc tr ưng là: r = 1, r = 2, r = 3. V y cơng th c tr c ti p tính a n cĩ d ng: n n n an = α1 1 + α2 2 + α3 3 . Thay n = 0, n = 1, n = 2, n = 3 vào cơng th c tính a n, đưc h ph ươ ng trình tuy n tính theo α1, α2, α3:  α + α + α = 2  1 2 3  α1 + 2α2 + 3α3 = 5   α1 + 4α2 + 9α3 = 15 Gi i h ph ươ ng trình đưc nghi m: α1 = 1, α2 = –1, α3 = 2. V y d ng hi n c a cơng th c truy h i đã cho là: n n an = 1 – 2 + 2. 3 . Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 50
5. Bà i tố n li t kê. Cĩ nh ng bà i tố n đ m cá c c u hì nh c a t hp, ngồ i vi c đ m s lư ng cá c c u hì nh thomã n cị n ph i li t kê tt ccá c c u hì nh c n đ m. ðĩlàcá c bà i tố n ph i tì m cá c c u hì nh t hp thomã n thêm m t ho c m t s điu ki n nà o đĩ. Thíd nh ư ph i tì m cá c t p con c a m t t p h p cĩ 5 s sao cho t ng c a cá c ph n t c a t p con đĩ bng 50, khi đĩ ph i ki m tra t ng cá c s trong m i t p c a 2 5 = 32 tp con c a t p đã cho đtì mcá c t p thomã n điu ki n đã nêu. Mu n v y, ph i li t kê cá c ph n t c a m i t p trong 32 tp con đĩ. Vi c li t kê cá c c u hì nh ph i thomã n cá c nguyên t c sau: - Khơng đư c l p l i m t c u hì nh đãđ m. - Khơng đưc đsĩ t m t c u hì nh. Sau đây chúng ta tì m hi u m t s thu t tố n li t kê th ư ng g p. 5.1. Ph ươ ng phá p sinh ð th c hi n ph ươ ng phá p nà y, bà i tố n c n thomã n 2 điu ki n: 1-Cĩ th xá c đnh đư c m t th t trên t p cá c c u hình c n đ m. Tđĩcĩ th xá c đnh đư c c u hì nh đu tiên và cu hì nh cu i cù ng theo th tđãxá c đnh. 2- Xây d ng đư c thu t tố n đ t mt c u hì nh ch ưa ph i là cu i cù ng đang cĩcĩ th đư a ra m t c u hì nh k ti p theo th tđãxá c đnh. ð t tên thu t tố n theo điu ki n 2 là thu t tố n Sinh_k _ti p. Cĩ th mơ ph ng thu t tố n sinh nh ư sau: Agorithm: Tng quá t v thu t tố n sinh. Procedue Ph ươ ng pháp sinh; Begin stop := false; while not stop do begin Sinh_k _ti p ; end; End; Bi n stop là mt bi n Boole dù ng đ dng ch ươ ng trì nh, khi đ n c u hì nh cu i cù ng thì stop nh n giátr true và ch ươ ng trì nh d ng. Sinh_k _ti p là mt tht c con nh m xây d ng c u hì nh k ti p c a c u hì nh đang cĩ . Chúý rng th tcá c c u hì nh xá c đnh trong điu ki n 1 cn l a ch n sao cho cĩ th xây d ng đư c thu t tố n sinh_k _ti p. Xé t 3 bà i tố n c th sd ng ph ươ ng phá p sinh. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 51
a. Li t kê cá c xâu nh phân cĩđdà i n Mi xâu nh phân b = b n – 1 bn – 2 b 0, trong đĩ bi ∈ {0, 1} cĩ th xem là bi u di n nh phân c a 1 s nguyên P(b) nà o đĩ. Vy cĩ th ly th t tăng c a s nguyên đxá c đnh th tcá c xâu nh phân. Xâu nh phân b = b n – 1 bn – 2 b 0 đưc g i làđi tr ư c xâu a = a n – 1 an – 2 a 0, (hay a k ti p b) nu P(b) < P(a), ký hi u là b < a. Cá ch xá c đnh th t nh ư vy g i là th t t nhiên hay cị n g i là th t tđin. Ch ng h n v i n = 3, cĩ th t tđin c a cá c xâu nh ư sau: Th tc a xâu 0 1 2 3 4 5 6 7 Xâu c th 000 001 010 011 100 101 110 111 Nh ư vy xâu đu tiên là gm tồ n s 0 và xâu cu i cù ng g m tồ n s 1. Tđĩ suy ra quy t c sinh xâu nh phân k ti p nh ư sau: • Xâu đu tiên g m tồ n s 0: 00 0 • Gi sđang cĩ xâu b n – 1 bn – 2 b 0, khi đĩ: -Tì m t ph i sang, t c là t b0, b 1, đ n khi g p bí t 0 đu tiên, ch ng h n đĩlà bi, - Thay b i = 1 và bj = 0 ∀j < i xâu m i thu đư c là xâu k ti p c a xâu đang cĩ . Thíd :Tì m xâu k ti p c a xâu 1 000 100 111 (n =10). ði t bên ph i sang, bit đu tiên b ng 0 là bit th 4, t c là b3 = 0. Vy thay b 3 = 1, b 2 = b1 = b 0 = 0 đư c xâu k ti p c a xâu đã cho là 1 000 101 000. (Rõ ràng là: 1 000 100 111 = 2 9+ 2 5+ 2 2+2 1+2 0 = 541 và 1 000 101 000 = 2 9+ 2 5+ 2 3 = 542) Thu t tố n v a trì nh bà y cĩ th mơ t nh ư sau: Algorithm: Sinh xâu nh phân k ti p. Procedure Xâu nh phân k ti p; Input: Xâu nh phân b n – 1 bn – 2 b 0, ∃bi = 0; Output: Xâu nh phân k ti p a n – 1 an – 2 a0; Begin i := 0; while b i = 1 do begin bi := 0; i := i + 1 ; end; bi := 1; End; b. Li t kê cá c t hp ch p k c a m t t p h p cĩ n ph n t Xét bà i tố n li t kê tt ccá c t hp ch p k c a t p h p X = {1, 2, , n} Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 52
Vì mi t hp ch p k c a n ph n t đã cho là mt t p con g m k ph n t ly t n ph n tđĩ nên ph i x p th tcá c t p con đĩ. Tr ư c h t bi u di n m i t p con k ph n t thà nh mt b cĩ th t: a = (a 1, a 2, ,a k) ; 1 ≤ a 1 < a 2 < < a k ≤ n vàđnh nghĩ a: Tp con a = (a 1, a 2, ,a k) g i làđi tr ư c t p con a’ = (a’ 1, a’ 2, ,a’ k) theo th t tđin, ký hi u a ∝ a’, n u tì m đư c m t ch s i (1 ≤ i ≤ k) sao cho: a1 = a’ 1 , a 2 = a’ 2 , , a i – 1 = a’ i – 1 , a i < a’ i . Thíd : Cho X = {1, 2, 3, 4, 5}. Cá c t hp ch p 3 c a X đư c li t kê theo th t t đin là : {1, 2, 3} ⇒ {1, 2, 4} ⇒ {1, 2, 5} ⇒ {1, 3, 4} ⇒ {1, 3, 5} ⇒ {1, 4, 5} ⇒ {2, 3, 4} ⇒ {2, 3, 5} ⇒ {2, 4, 5} ⇒ {3, 4, 5} Nh ư vy t p con đu tiên là {1, 2, , k} và tp con cu i cù ng là {n – k+1, n–k+2, , n}. T đĩ suy ra quy t c sinh t p con k ti p nh ư sau: • Tì m t ph i qua trá i c a dã y ph n t đu tiên thomã n a i ≠ n – k + i , • Thay a i b ng a i + 1 , • Thay a j b ng a i + j – i , v i j = i + 1, i + 2, , k. Thíd : Tì m t hp ch p 4 t tp {1, 2, 3, 4, 5, 6} k ti p t hp {1, 2, 5, 6} Gi i: Lù i t ph i sang trá i th y a 2 = 2 là sh ng đu tiên thomã n: a2 = 2 ≠ 6 – 4 + 2= 4. Nh ư vy t hp k ti p là : a1 = 1, a 2 = 2 + 1 = 3, a 3 = 3 + 3 – 2 = 4, a 4 = 3 + 4 – 2 = 5, tc là tp {1, 3, 4, 5} Algorithm: Sinh t hp k ti p. Procedure T hp k ti p; Input: T hp {a 1, a 2, ,a k} khơng trù ng v i {n – k + 1, , n}; Output: T hp k ti p {a’ 1, a’ 2, ,a’ k} ; Begin i := k ; while a i = n – k + i do i := i – 1; a i := a i + 1 ; for j := i + 1 to k do a j = ai + j – i ; End; c. Li t kê cá c hố n vc a t p h p cĩ n ph n t Bà i tố n đt ra là : Li t kê tt ccá c hố n vc a t p h p X = {1, 2, , n} Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình Giáo trình Tốn R i r c . 53