TÀI LIỆU GIÁO KHOA CHUYÊN TIN - QUYỂN 1

Chia sẻ: Nguyễn Văn Toàn | Ngày: | Loại File: PDF | Số trang:219

Thêm vào BST

Báo xấu

455
lượt xem 119
download

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

Bộ Giáo dục và đào tọa đã ban hành chương trình tin học cho các lớp chuyên 10,11,12. Dựa theo các chuyên đề chuyên sâu trong chương trình nói trên, các tác giả biên soạn bộ sách chuyên tin học, bao gồm các vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình

Chủ đề:

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

Lưu

Nội dung Text: TÀI LIỆU GIÁO KHOA CHUYÊN TIN - QUYỂN 1

Hå sÜ ®µm (Chñ biªn) ®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng tµi liÖu gi¸o khoa chuyªn tin quyÓn 1 Nhµ xuÊt b¶n gi¸o dôc viÖt nam
C«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc H Néi - Nh xuÊt b¶n Gi¸o dôc ViÖt Nam gi÷ quyÒn c«ng bè t¸c phÈm. 349-2009/CXB/43-644/GD M sè : 8I746H9 2
L I NÓI ð U B Giáo d c và ðào t o ñã ban hành chương trình chuyên tin h c cho các l p chuyên 10, 11, 12. D a theo các chuyên ñ chuyên sâu trong chương trình nói trên, các tác gi biên so n b sách chuyên tin h c, bao g m các v n ñ cơ b n nh t v c u trúc d li u, thu t toán và cài ñ t chương trình. B sách g m ba quy n, quy n 1, 2 và 3. C u trúc m i quy n bao g m: ph n lí thuy t, gi i thi u các khái ni m cơ b n, c n thi t tr c ti p, thư ng dùng nh t; ph n áp d ng, trình bày các bài toán thư ng g p, cách gi i và cài ñ t chương trình; cu i cùng là các bài t p. Các chuyên ñ trong b sách ñư c l a ch n mang tính h th ng t cơ b n ñ n chuyên sâu. V i tr i nghi m nhi u năm tham gia gi ng d y, b i dư ng h c sinh chuyên tin h c c a các trư ng chuyên có truy n th ng và uy tín, các tác gi ñã l a ch n, biên so n các n i dung cơ b n, thi t y u nh t mà mình ñã s d ng ñ d y h c v i mong mu n b sách ph c v không ch cho giáo viên và h c sinh chuyên PTTH mà c cho giáo viên, h c sinh chuyên tin h c THCS làm tài li u tham kh o cho vi c d y và h c c a mình. V i kinh nghi m nhi u năm tham gia b i dư ng h c sinh, sinh viên tham gia các kì thi h c sinh gi i Qu c gia, Qu c t H i thi Tin h c tr Toàn qu c, Olympiad Sinh viên Tin h c Toàn qu c, Kì thi l p trình viên Qu c t khu v c ðông Nam Á, các tác gi ñã l a ch n gi i thi u các bài t p, l i gi i có ñ nh hư ng ph c v cho không ch h c sinh mà c sinh viên làm tài li u tham kh o khi tham gia các kì thi trên. L n ñ u t p sách ñư c biên so n, th i gian và trình ñ có h n ch nên ch c ch n còn nhi u thi u sót, các tác gi mong nh n ñư c ý ki n ñóng góp c a b n ñ c, các ñ ng nghi p, sinh viên và h c sinh ñ b sách ñư c ngày càng hoàn thi n hơn . Các tác gi 3
4
Chuyên ñ 1 THU T TOÁN VÀ PHÂN TÍCH THU T TOÁN 1. Thu t toán Thu t toán là m t trong nh ng khái ni m quan tr ng nh t trong tin h c. Thu t ng thu t toán xu t phát t nhà khoa h c Ar p Abu Ja'far Mohammed ibn Musa al Khowarizmi. Ta có th hi u thu t toán là dãy h u h n các bư c, m i bư c mô t chính xác các phép toán ho c hành ñ ng c n th c hi n, ñ gi i quy t m t v n ñ . ð hi u ñ y ñ ý nghĩa c a khái ni m thu t toán chúng ta xem xét 5 ñ c trưng sau c a thu t toán: • ð u vào (Input): Thu t toán nh n d li u vào t m t t p nào ñó. • ð u ra (Output): V i m i t p các d li u ñ u vào, thu t toán ñưa ra các d li u tương ng v i l i gi i c a bài toán. • Chính xác: Các bư c c a thu t toán ñư c mô t chính xác. • H u h n: Thu t toán c n ph i ñưa ñư c ñ u ra sau m t s h u h n (có th r t l n) bư c v i m i ñ u vào. • ðơn tr : Các k t qu trung gian c a t ng bư c th c hi n thu t toán ñư c xác ñ nh m t cách ñơn tr và ch ph thu c vào ñ u vào và các k t qu c a các bư c trư c. • T ng quát: Thu t toán có th áp d ng ñ gi i m i bài toán có d ng ñã cho. ð bi u di n thu t toán có th bi u di n b ng danh sách các bư c, các bư c ñư c di n ñ t b ng ngôn ng thông thư ng và các kí hi u toán h c; ho c có th bi u di n thu t toán b ng sơ ñ kh i. Tuy nhiên, ñ ñ m b o tính xác ñ nh c a thu t toán, thu t toán c n ñư c vi t b ng các ngôn ng l p trình. M t chương trình là s bi u di n c a m t thu t toán trong ngôn ng l p trình ñã ch n. Trong tài li u này, chúng ta s d ng ngôn ng t a Pascal ñ trình bày các thu t toán. Nói là t a Pascal, b i vì nhi u trư ng h p, ñ cho ng n g n, chúng ta không hoàn toàn tuân 5
theo quy ñ nh c a Pascal. Ngôn ng Pascal là ngôn ng ñơn gi n, khoa h c, ñư c gi ng d y trong nhà trư ng ph thông. 2, Ví d : Thu t toán ki m tra tính nguyên t c a m t s nguyên dương vi t trên ngôn ng l p trình Pascal. function is_prime(n):boolean; begin for k:=2 to n-1 do if (n mod k=0) then exit(false); exit(true); end; 2. Phân tích thu t toán 2.1. Tính hi u qu c a thu t toán Khi gi i m t bài toán, chúng ta c n ch n trong s các thu t toán m t thu t toán mà chúng ta cho là “t t” nh t. V y d a trên cơ s nào ñ ñánh giá thu t toán này “t t” hơn thu t toán kia? Thông thư ng ta d a trên hai ti u chu n sau: 1. Thu t toán ñơn gi n, d hi u, d cài ñ t (d vi t chương trình). 2. Thu t toán hi u qu : Chúng ta thư ng ñ c bi t quan tâm ñ n th i gian th c hi n c a thu t toán (g i là ñ ph c t p tính toán), bên c nh ñó chúng ta cũng quan tâm t i dung lư ng không gian nh c n thi t ñ lưu gi các d li u vào, ra và các k t qu trung gian trong quá trình tính toán. Khi vi t chương trình ch ñ s d ng m t s ít l n thì tiêu chu n (1) là quan tr ng, nhưng n u vi t chương trình ñ s d ng nhi u l n, cho nhi u ngư i s d ng thì tiêu chu n (2) l i quan tr ng hơn. Trong trư ng h p này, dù thu t toán có th ph i cài ñ t ph c t p, nhưng ta v n s l a ch n ñ nh n ñư c chương trình ch y nhanh hơn, hi u qu hơn. 2.2. T i sao c n thu t toán có tính hi u qu ? Kĩ thu t máy tính ti n b r t nhanh, ngày nay các máy tính l n có th ñ t t c ñ tính toán hàng nghìn t phép tính trong m t giây. V y có c n ph i tìm thu t toán hi u qu hay không? Chúng ta xem l i ví d bài toán ki m tra tính nguyên t c a 2. m t s nguyên dương function is_prime(n):boolean; begin 6
for k:=2 to n-1 do if (n mod k=0) then exit(false); exit(true); end; 2 phép D dàng nh n th y r ng, n u là m t s nguyên t chúng ta ph i m t . Gi s m t siêu máy tính có th tính ñư c trăm nghìn t 10 toán phép trong m t giây, như v y ñ ki m tra m t s kho ng 25 ch s m t kho ng ~3170 năm. Trong khi ñó, n u ta có nh n xét vi c th t2 1 là không c n thi t mà ch c n th t 2 ñ n √ , ta có: ñn function is_prime(n):boolean; begin for k:=2 to trunc(sqrt(n)) do if (n mod k=0) then exit(false); exit(true); end; {hàm sqrt(n) là hàm tính √ , trunc(x) là hàm làm tròn x } ~0.03 giây! Như v y ñ ki m tra m t s kho ng 25 ch s m t kho ng 2.3. ðánh giá th i gian th c hi n thu t toán Có hai cách ti p c n ñ ñánh giá th i gian th c hi n c a m t thu t toán. Cách th nh t b ng th c nghi m, chúng ta vi t chương trình và cho ch y chương trình v i các d li u vào khác nhau trên m t máy tính. Cách th hai b ng phương pháp lí thuy t, chúng ta coi th i gian th c hi n thu t toán như hàm s c a c d li u vào (c c a d li u vào là m t tham s ñ c trưng cho d li u vào, nó có nh hư ng quy t ñ nh ñ n th i gian th c hi n chương trình. Ví d ñ i v i bài toán ki m tra s nguyên t thì c c a d li u vào là s c n ki m tra; hay v i bài toán s p x p dãy s , c c a d li u vào là s ph n t c a dãy). Thông thư ng c c a d li u vào là m t s nguyên dương , ta s d ng hàm s trong ñó là c c a d li u vào ñ bi u di n th i th c hi n c a m t thu t toán. Xét ví d bài toán ki m tra tính nguyên t c a m t s nguyên dương (c d li u 2 thì ch c n m t l n th chia 2 ñ k t lu n vào là ), n u là m t s ch n 3 không chia h t cho 2 nhưng l i chia không ph i là s nguyên t . N u h t cho 3 thì c n 2 l n th (chia 2 và chia 3) ñ k t lu n không nguyên t . Còn n u là m t s nguyên t thì thu t toán ph i th c hi n nhi u l n th nh t. 7
Trong tài li u này, chúng ta hi u hàm s là th i gian nhi u nh t c n thi t ñ th c hi n thu t toán v i m i b d li u ñ u vào c . S d ng kí hi u toán h c ô l n ñ mô t ñ l n c a hàm . Gi s là m t s nguyên dương, và là hai hàm th c không âm. Ta vi t n u và ch n u t n t i các h ng s dương và , sao cho ,v i mi . N u m t thu t toán có th i gian th c hi n chúng ta nói r ng thu t toán có th i gian th c hi n c p . 2 , ta có 2 2 3 1 Ví d : Gi s v im i Vy , trong trư ng h p này ta nói thu t toán có th i gian th c hi n cp . 2.4. Các quy t c ñánh giá th i gian th c hi n thu t toán ð ñánh giá th i gian th c hi n thu t toán ñư c trình bày b ng ngôn ng t a Pascal, ta c n bi t cách ñánh giá th i gian th c hi n các câu l nh c a Pascal. Trư c tiên, chúng ta hãy xem xét các câu l nh chính trong Pascal. Các câu l nh trong Pascal ñư c ñ nh nghĩa ñ quy như sau: 1. Các phép gán, ñ c, vi t là các câu l nh (ñư c g i là l nh ñơn). 2. N u S1, S2, ..., Sm là câu l nh thì Begin S1; S2; …; Sm; End; là câu l nh (ñư c g i là l nh h p thành hay kh i l nh). 3. N u S1 và S2 là các câu l nh và E là bi u th c lôgic thì If E then S1 else S2; là câu l nh (ñư c g i là l nh r nhánh hay l nh If). 4. N u S là câu l nh và E là bi u th c lôgic thì While E do S; là câu l nh (ñư c g i là l nh l p ñi u ki n trư c hay l nh While). 5. N u S1, S2,…,Sm là các câu l nh và E là bi u th c lôgic thì Repeat S1; S2; …; Sm; Until E; là câu l nh (ñư c g i là l nh l p ñi u ki n sau hay l nh Repeat) 8
6. N u S là l nh, E1 và E2 là các bi u th c cùng m t ki u th t ñ m ñư c thì For i:=E1 to E2 do S; là câu l nh (ñư c g i là l nh l p v i s l n xác ñ nh hay l nh For). ð ñánh giá, chúng ta phân tích chương trình xu t phát t các l nh ñơn, r i ñánh giá các l nh ph c t p hơn, cu i cùng ñánh giá ñư c th i gian th c hi n c a chương trình, c th : 1 1. Th i gian th c hi n các l nh ñơn: gán, ñ c, vi t là 2. L nh h p thành: gi s th i gian th c hi n c a S1, S2,…,Sm tương ng là , ,..., . Khi ñó th i gian th c hi n c a l nh h p , ,…, thành là: . 3. L nh If: gi s th i gian th c hi n c a S1, S2 tương ng là , . Khi ñó th i gian th c hi n c a l nh If là: , . 4. L nh l p While: gi s th i gian th c hi n l nh S (thân c a l nh While) là và là s l n l p t i ña th c hi n l nh S. Khi ñó th i gian th c hi n l nh While là . 5. L nh l p Repeat: gi s th i gian th c hi n kh i l nh Begin S1; S2;…; Sm; End; là và là s l n l p t i ña. Khi ñó th i gian th c hi n l nh Repeat là . 6. L nh l p For: gi s th i gian th c hi n l nh S là và là s l n l p t i ña. Khi ñó th i gian th c hi n l nh For là . 2.5. M t s ví d Ví d 1: Phân tích th i gian th c hi n c a chương trình sau: var i, j, n :longint; s1, s2 :longint; BEGIN {1} readln(n); {2} s1:=0; {3} for i:=1 to n do {4} s1:=s1 + i; {5} s2:=0; 9
{6} for j:=1 to n do {7} s2:=s2 + j*j; {8} writeln('1+2+..+',n,'=',s1); {9} writeln('1^2+2^2+..+',n,'^2=',s2); END. Th i gian th c hi n chương trình ph thu c vào s . 1. Các l nh {1}, {2}, {4}, {5}, {7}, {8}, {9} có th i gian th c hi n là L nh l p For {3} có s l n l p là , như v y l nh {3} có th i gian th c hi n là . Tương t l nh l p For {6} cũng có th i gian th c hi n là . V y th i gian th c hi n c a chương trình là: max 1, 1, , 1, , 1, 1 Ví d 2: Phân tích th i gian th c hi n c a ño n chương trình sau: {1} c:=0; {2} for i:=1 to 2*n do {3} c:=c+1; {4} for i:=1 to n do {5} for j:=1 to n do {6} c:=c+1; Th i gian th c hi n chương trình ph thu c vào s . 1. Các l nh {1}, {3}, {6} có th i gian th c hi n là L nh l p For {2} có s l n l p là 2 , như v y l nh {2} có th i gian th c hi n là . L nh l p For {5} có s l n l p là , như v y l nh {5} có th i gian th c hi n là . L nh l p For {4} có s l n l p là , như v y l nh {4} có th i gian th c hi n là . V y th i gian th c hi n c a ño n chương trình trên là: max 1, , Ví d 3: Phân tích th i gian th c hi n c a ño n chương trình sau: {1} for i:=1 to n do {2} for j:=1 to i do {3} c:=c+1; Th i gian th c hi n chương trình ph thu c vào s . 1. Các l nh {3} có th i gian th c hi n là 10
Khi i = 1, j ch y t 1 ñ n 1 l nh l p For {2} l p 1 l n Khi i = 2, j ch y t 1 ñ n 2 l nh l p For {2} l p 2 l n … Khi i = , j ch y t 1 ñ n l nh l p For {2} l p ln Như v y l nh {3} ñư c l p: 1 2 .. l n, do ñó l nh {1} có th i gian th c hi n là V y th i gian th c hi n c a ño n chương trình trên là: Bài t p 1.1. Phân tích th i gian th c hi n c a ño n chương trình sau: for i:=1 to n do if i mod 2=0 then c:=c+1; 1.2. Phân tích th i gian th c hi n c a ño n chương trình sau: for i:=1 to n do if i mod 2=0 then c1:=c1+1 else c2:=c2+1; 1.3. Phân tích th i gian th c hi n c a ño n chương trình sau: for i:=1 to n do if i mod 2=0 then for j:=1 to n do c:=c+1 1.4. Phân tích th i gian th c hi n c a ño n chương trình sau: a:=0; b:=0; c:=0; for i:=1 to n do begin a:=a + 1; b:=b + i; c:=c + i*i; end; 1.5. Phân tích th i gian th c hi n c a ño n chương trình sau: i:=n; d:=0; 11
while i>0 do begin i:=i-1; d:=d + i; end; 1.6. Phân tích th i gian th c hi n c a ño n chương trình sau: i:=0; d:=0; repeat i:=i+1; if i mod 3=0 then d:=d + i; until i>n; 1.7. Phân tích th i gian th c hi n c a ño n chương trình sau: d:=0; for i:=1 to n-1 do for j:=i+1 to n do d:=d+1; 1.8. Phân tích th i gian th c hi n c a ño n chương trình sau: d:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do d:=d+1; 1.9. Phân tích th i gian th c hi n c a ño n chương trình sau: d:=0; while n>0 do begin n:=n div 2; d:=d+1; end; 1.10. Cho m t dãy s g m s nguyên dương, xác ñ nh xem có t n t i m t dãy con liên ti p có t ng b ng hay không? a) ðưa ra thu t toán có th i gian th c hi n . b) ðưa ra thu t toán có th i gian th c hi n . c) ðưa ra thu t toán có th i gian th c hi n . 12
Chuyên ñ 2 CÁC KI N TH C CƠ B N 1. H ñ m H ñ m ñư c hi u là t p các kí hi u và quy t c s d ng t p các kí hi u ñó ñ bi u 1 , các kí hi u ñư c di n và xác ñ nh giá tr các s . Trong h ñ m cơ s dùng có các giá tr tương ng 0, 1, . . , 1. Gi s có bi u di n: … 1 0, … 1 2 1 2 1 s các ch s bên trái, là s các ch s bên ph i d u phân chia trong ñó ph n nguyên và ph n phân c a s và các ph i tho mãn ñi u ki n 0 . Khi ñó giá tr c a s ñư c tính theo công th c: ... ... 1 Chú ý: ð phân bi t s ñư c bi u di n h ñ m nào ngư i ta vi t cơ s làm ch s dư i c a s ñó. Ví d : là bi u di n h ñm . 1.1. Các h ñ m thư ng dùng: H th p phân (h cơ s 10) dùng 10 kí hi u 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 28,910 = 2 × 101 + 8 × 100 + 9 × 10-1 Ví d : H nh phân (h cơ s 2) ch dùng hai kí hi u 0, 1 102= 1 × 21 + 0 × 20 = 210 Ví d : 101,12= 1 × 22 + 0 × 21 + 1 × 20 + 1 × 2-1 =5,5 H cơ s mư i sáu, còn g i là h hexa, s d ng các kí hi u 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, trong ñó A, B, C, D, E, F có các giá tr tương ng 10, 11, 12, 13, 14, 15 trong h th p phân Ví d : AF016 = 10 × 162 + 15 × 161 + 0 × 160 =280010 13
1.2. Chuy n ñ i bi u di n s h th p phân sang h ñ m cơ s khác ð chuy n ñ i bi u di n m t s h th p phân sang h ñ m cơ s khác, trư c h t ta tách ph n nguyên và ph n phân r i ti n hành chuy n ñ i t ng ph n, sau ñó ghép l i. Chuy n ñ i bi u di n ph n nguyên: T (1) ta l y ph n nguyên: ... đó 0 . Do 0 0 nên khi chia cho thì ph n dư c a phép chia ñó là còn 1 s là: ... 1 2 1 1 . Tương t 1 là ph n dư c a thương s phép chia 1 cho . Quá trình ñư c l p cho ñ n khi nh n ñư c thương b ng 0. Chuy n ñ i bi u di n ph n phân: T (1) ta l y ph n sau d u ph y: ... . 1 ... Ta nh n th y 1 chính là phân nguyên c a k t qu phép nhân, còn ph n phân c a k t qu là 2 ... . Quá trình ñư c l p cho ñ n khi nh n ñ s ch s c n tìm. 2. S nguyên t 1 là s nguyên t n u có ñúng hai ư c s là 1 và . M t s t nhiên Ví d các s nguyên t : 2, 3, 5, 7, 11, 13, 17, 19, 23, … 2.1. Ki m tra tính nguyên t 1 có là s nguyên t không, ta ki m tra a) ð ki m tra s nguyên dương 2 1) mà là ư c c a ( chia h t xem có t n t i m t s nguyên ) thì không ph i là s nguyên t , ngư c l i là s nguyên t . 1 không ph i là s nguyên t , ta luôn có th tách Nu à2 1. Vì √ . Do ñó, nên 1 là không c n thi t, mà ch c n ki m tra t 2 vi c ki m tra v i t 2 ñ n ñ n√ . function is_prime(n:longint):boolean; var k :longint; begin if n=1 then exit(false); 14
for k:=2 to trunc(sqrt(n)) do if (n mod k=0) then exit(false); exit(true); end; Hàm is_prime(n) trên ti n hành ki m tra l n lư t t ng s nguyên trong ño n [2, √ ], ñ c i ti n, c n gi m thi u s các s c n ki m tra. Ta có nh n xét, ñ ki m 1 có là s nguyên t không, ta ki m tra xem có t n tra s nguyên dương 2 √ ) mà là ư c c a thì không ph i là s t i m t s nguyên t nguyên t , ngư c l i là s nguyên t . Thay vì ki m tra các s là nguyên t ta s ch ki m tra các s có tính ch t gi ng v i tính ch t c a s nguyên t , có th s d ng m t trong hai tính ch t ñơn gi n sau c a s nguyên t : 1) Tr s 2 và các s nguyên t là s l . 2) Tr s 2, s 3 các s nguyên t có d ng 6 1 (vì s có d ng 6 2 thì chia h t cho 2, s có d ng 6 3 thì chia h t cho 3). Hàm is_prime2(n) dư i ñây ki m tra tính nguyên t c a s b ng cách ki m tra xem có chia h t cho s 2, s 3 và các s có d ng 6 1 trong ño n [5, √ ]. function is_prime2(n:longint):boolean; var k,sqrt_n:longint; begin if (n=2)or(n=3) then exit(true); if (n=1)or(n mod 2=0)or(n mod 3=0) then exit(false); sqrt_n:=trunc(sqrt(n)); k:=-1; repeat inc(k,6); if (n mod k=0)or(n mod (k+2)=0) then break; until k>sqrt_n; exit(k>sqrt_n); end; b) Phương pháp ki m tra s nguyên t theo xác su t T ñ nh lí nh Fermat: nu là s nguyên t và là s t nhiên thì Ta có cách ki m tra tính nguyên t c a Fermat: 15
n u2 2 thì không là s nguyên t n u2 2 thì nhi u kh năng là s nguyên t Ví d : 2 9 512 9 8 2, do ñó s 9 không là s nguyên t . 2 3 8 3 2, do ñó nhi u kh năng 3 là s nguyên t , th c t 3 là s nguyên t . 2 11 2048 11 2, do ñó nhi u kh năng 11 là s nguyên t , th c t 11 là s nguyên t . , 2.2. Li t kê các s nguyên t trong ño n trong ño n 1, Cách th nh t là th l n lư t các s , r i ki m tra tính nguyên t ca . procedure generate(N:longint); var m :longint; begin for m:=2 to N do if is_prime(m) then writeln(m); end; Cách này ñơn gi n nhưng ch y ch m, ñ c i ti n có th s d ng các tính ch t c a s nguyên t ñ lo i b trư c nh ng s không ph i là s nguyên t và không c n ki m tra các s này. Cách th hai là s d ng sàng s nguyên t , như sàng Eratosthene, li t kê ñư c các s nguyên t nhanh, tuy nhiên như c ñi m c a cách này là t n nhi u b nh . Cách làm ñư c th c hi n như sau: Trư c tiên xoá b s 1 ra kh i t p các s nguyên t . S ti p theo s 1 là s 2, là s nguyên t , xoá t t c các b i c a 2 ra kh i b ng. S ñ u tiên không b xoá sau s 2 (s 3) là s nguyên t , xoá các b i c a 3... Gi i thu t ti p t c cho ñ n khi g p s nguyên t l n hơn √ thì d ng l i. T t c các s chưa b xoá là s nguyên t . {$M 1100000} procedure Eratosthene(N:longint); const MAX = 1000000; var i,j :longint; Prime :array [1..MAX] of byte; begin 16
fillchar(Prime,sizeof(Prime),0); for i:=2 to trunc(sqrt(N)) do if Prime[i]=0 then begin j:=i*i; while j
1 1 1 1 1 1 … 1 1 1 Ví d : T ng các ư c c a 24 là: 2 1 3 1 60 2 1 3 1 3.3. Ư c s chung l n nh t c a hai s Ư c s chung l n nh t (USCLN) c a 2 s ñư c tính theo thu t toán Euclid , , function USCLN(a,b:longint):longint; var tmp :longint; begin while b>0 do begin a:=a mod b; tmp:=a; a:=b; b:=tmp; end; exit(a); end; 3.4. B i s chung nh nh t c a hai s B i s chung nh nh t (BSCNN) c a hai s ñư c tính theo công th c: , , , 4. Lí thuy t t p h p 4.1. Các phép toán trên t p h p 1. Ph n bù c a trong , kí hi u , là t p h p các ph n t c a không thu c : : 2. H p c a và , kí hi u , là t p h p các ph n t ho c thu c vào ho c thu c vào : 18
: 3. Giao c a và , kí hi u , là t p h p các ph n t ñ ng th i thu c c và : à \ , là t p h p các ph n t thu c t p 4. Hi u c a và , kí hi u là nhưng không thu c . \ : à 4.2. Các tính ch t c a phép toán trên t p h p 1. K t h p 2. Giao hoán 3. Phân b 4. ð i ng u 4.3. Tích ð -các c a các t p h p Tích ð -các ghép hai t p h p: | , , Tích ð -các m r ng ghép nhi u t p h p: | … , ,…, , 1, 2, . . , 4.4. Nguyên lí c ng Nu và là hai t p h p r i nhau thì | | || || Nguyên lí c ng m r ng cho nhi u t p h p ñôi m t r i nhau: 19
, ,…, Nu là m t phân ho ch c a t p thì: || | | | | | | 4.5. Nguyên bù tr Nu và không r i nhau thì | | || || | | Nguyên lí m r ng cho nhi u t p h p: , ,…, Gi s là các t p h u h n: | | … 1 trong ñó là t ng ph n t c a t t c các giao c a t pl yt t p ñã cho 4.6. Nguyên lí nhân , ,…, N u m i thành ph n c a b có th t k thành ph n có kh 1, 2, … , , thì s b s ñư c t o ra là tích s c a các kh năng năng l a ch n .. này M t h qu tr c ti p c a nguyên lí nhân: | … | | | | | … | | 4.7. Ch nh h p l p , ,…, Xét t p h u h n g m ph n t M t ch nh h p l p ch p ca ph n t là m t b có th t g m ph n t c a , các ph n t có th l p l i. M t ch nh h p l p ch p ca có th xem như m t ph n t c a tích ð cac . Theo nguyên lí nhân, s t t c các ch nh h p l p ch p ca s là . 4.8. Ch nh h p không l p M t ch nh h p không l p ch p ca ph n t là m t b có th t g m thành ph n l y t ph n t c a t p ñã cho. Các thành ph n không ñư c l p l i. ð xây d ng m t ch nh h p không l p, ta xây d ng d n t ng thành ph n ñ u tiên. Thành ph n này có kh năng l a ch n. M i thành ph n ti p theo, s kh năng 20