chương 1 1.1 Xây dựng thuật toán để tính diện tích các hình tròn, hình chữ nhật 1.2 Xây dựng thuật toán nhập số tự nhiên, rồi hiển thị một trong các thông báo sau: “Số nguyên tố”, “Không phải số nguyên tố”.3 Xây dựng thuật toán tìm số bé nhất của dãy số a[0], a[1],…,a[n-1] 1.4 Xây dựng thuật toán đọc số nguyên, rồi hiển thị số đảo ngược (ví dụ 649 đảo thành 946) 1.5 Tính độ phức tạp của thuật toán tìm số lớn nhất của dãy số a[1], a[2],…,a[n] 1.6 Tính độ phức tạp của của thuật toán tìm phần tử nhỏ nhất trong ma trận A=(aij)mxn 1.7 Tính độ phức tạp của khối lệnh sau: for (i= 1;i<=n;i++) for (j= 1;j<=m;j++) for (k= 1;k<=x;k++) //lệnh 1.10 Viết chương trình (đệ quy) giải bài toán tháp Hà Nội.11 Viết chương trình nhập vào 2 số nguyên và dùng thủ tục đệ quy tìm ước số chung lớn nhất của chúng.12 Viết chương trình nhập số tự nhiên n > 0 từ bàn phím và dùng thủ tục đệ quy chuyển sang dạng nhị phân.13 Viết chương trình nhập số tự nhiên n > 0 từ bàn phím và dùng thủ tục đệ quy tính 1 +1/2 + 1/3 + .14 Viết chương trình nhập số tự nhiên n > 0 từ bàn phím và dùng thủ tục đệ quy tính 1 + 1/2! + 1/3! + .15 Viết chương trình (đệ quy) đọc số nguyên, rồi hiển thị số đảo ngược (ví dụ 649 đảo thành 946) 12 Chương 2. BÀI TOÁN ĐẾM Tóm tắt chương Chương này, sẽ tập trung trả lời câu hỏi có bao nhiêu cấu hình thỏa mãn điều kiện đã nêu? Để trả lời câu hỏi đó, cần dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấu hình đơn giản và một số phép tính trong tập hợp, các công thức tổ hợp và hệ thức truy hồi.1 Các khái niệm cơ bản - Tập hợp được coi là kết hợp các đối tượng có cùng bản chất (thuộc tính, dấu hiệu) chung nào đó. - Biểu diễn tập hợp • Liệt kê các phần tử A = { 1, 2, 3, 4 } X = {x1, x2,. , xn} • Biểu diễn tập hợp bằng cách mô tả tính chất: C = {n| n là số lẻ} Y = {x|x là nghiệm của phương trình 3x2+7x+4=0} - Lực lượng tập hợp: là số phần tử của A, ký hiệu là |A| hoặc card(A), gọi là lực lượng của tập A.
Nếu |A| < , ta nói A là tập hữu hạn, nếu |A| = , ta nói A là tập vô hạn. Quan hệ bao hàm: Cho hai tập A, B. - Nếu mỗi phần tử thuộc A cũng thuộc B ta nói A là tập con của B (hoặc A bao hàm trong B) và ký hiệu A B - Nếu A không phải tập con của B ta ký hiệu A B - Nếu A B và B A ta nói A bằng B và ký hiệu A = B Tập tất cả tập con của A ký hiệu là P(A) Định lý 1. Ta luôn có tập chứa {x} có số phần tử là k và tập không chứa {x} cũng có 13 số phần tử là k, nghĩa là |P(A)|= |P(A1)| +|P(A2)|=2k+2k=2.2k=2k+1 ➢ Suy ra đúng với mọi n Theo nguyên lý quy nạp ta có đpcm Định lý 2.
Quan hệ bao hàm có các tính chất sau đây. - Phản xạ: A : A A - Phản đối xứng: A, B : A B & B A A = B - Bắc cầu: A, B, C : A B & B C A C 2.2 Các phép toán trên tập hợp Cho các tập A và B. Ta định nghĩa các phép toán sau. - Phép hiệu: hiệu của A và B, ký hiệu A \ B là tập: A \ B = { x|x A & x B } - Phần bù: cho tập X và A X.
Phần bù của A (trong X) là tập 𝐴𝑋 = X \ A - Phép hợp: hợp của A và B, ký hiệu A B là tập A B = { x |x A hoặc x B } - Phép giao: giao của A và B, ký hiệu A B là tập A B = { x| x A & x B } - Phân hoạch: Nếu A B = , ta nói A và B rời nhau. Xn và chúng rời nhau từng đôi một, ta nói { X1, X2,. , Xn } là một phân hoạch của tập hợp A.2 Các nguyên lý đếm cơ bản 2.1 Nguyên lý cộng Giả sử {X1, X2,. , Xn} là một phân hoạch của tập S.
+ Xn Hệ quả :A B = A+ B− A B Các luật a) Luật kết hợp: (AB)C=A(BC) (AB)C=A(BC) b) Luật giao hoán: 14 AB=BA AB=BA c) Luật phân bố: A ( B C ) = (A B) (A C ) A ( B C ) = (A B) (A C ) d) Luật bù kép 𝐴̿ = 𝐴 e) Luật đối ngẫu De Morgan: ̅̅̅̅̅̅̅ 𝐴 ∪ 𝐵 = 𝐴̅ ∩ 𝐵̅ & ̅̅̅̅̅̅̅ 𝐴 ∩ 𝐵 = 𝐴̅ ∪ 𝐵̅ 𝐴1 𝐴2 .2 Nguyên lý nhân Giả sử có cấu hình tổ hợp xây dụng k bước, bước 1 có thể thực hiện qua n1 cách, bước 2 có thể thực hiện qua n2 cách, …, bước k có thể thực hiện qua nk cách. Khi đó số cấu hình là: n1.3 Nguyên lý bù trừ Cho 2 tập X1, X2 Ta có nguyên lý cộng trên 2 tập |𝑋1 ∪ 𝑋2 | = |𝑋1 | + |𝑋1 | − |𝑋1 ∩ 𝑋2 | Tổng quát lên n tập X1 đến Xn |𝑋1 ∪ 𝑋2 ∪ … ∪ 𝑋𝑛 | = 𝑆1 − 𝑆2 + ⋯. +(−1)𝑛−1 𝑆𝑛 = ∑𝑛𝑘=1(−1)𝑘−1 𝑆𝑘 Sk là tổng phần tử của tất cả các giao của k (k=1,…,n) tập lấy từ n tập Giả sử X1, X2, X3 là các tập hợp, khi đó ta có |𝑋1 ∪ 𝑋2 ∪ 𝑋3 | = |𝑋1 | + |𝑋1 | + |𝑋3 | − |𝑋1 ∩ 𝑋2 | − |𝑋1 ∩ 𝑋3 | − |𝑋2 ∩ 𝑋3 | + |𝑋1 ∩ 𝑋2 ∩ 𝑋3 | Bây giờ ta cho các tính chất 1,. Xét bài toán: Đếm số phần tử trong X không thoả mãn một tính chất k nào cả., n, ta ký hiệu: Xk={x X| x thoả mãn k} 15 Như vậy phần bù của Xk là 𝑋𝑘 ={ x X| x không thoả mãn k} Ký hiệu N là số cần đếm, ta có : N= 𝑋1 𝑋2 .
Xn Suy ra N=X +∑𝑛𝑘=1(−1)𝑘 𝑆𝑘 N=∑𝑛𝑘=0(−1)𝑘 𝑆𝑘 (S0=X ) Ví dụ 1. Công đoàn Khoa CNTT cử đoàn vận động viên đi thi bơi lội và thi cầu lông cho trường. Nam có 12 người. Số vận động viên thi bơi lội có 16 người.
Số nữ vận động viên thi cầu lông bằng số nam vận động viên thi bơi lội. Hỏi toàn đoàn có bao nhiêu người? Giải: đoàn có 2 thành phần nam và nữ, nữ tham gia bơi lội và cầu lông mà số nữ thi cầu lông bằng số nam thi bơi lội nên số nữ bằng 16, suy ra tổng đoàn 28 vận động viên (theo nguyên lý cộng) Ví dụ 2. Có 50 đề tài về lĩnh vực lập trình Web, 30 đề tài về lập trình di động và 20 đề tài về thiết kế hướng đối tượng. Hỏi một sinh viên có bao nhiêu khả năng để chọn đề tài trong 3 lĩnh vực trên.
Giải: sinh viên có thể chọn ở lĩnh vực 1 với 50 cách, lĩnh vực 2 với 30 cách và lĩnh vực 3 với 20 cách. Vậy có 50+30+20= 100 cách chọn Ví dụ 3. y có giá trị bằng bao nhiêu khi nhập đầu vào m=20, n=30, k=10, y=0 for (i= 1;i<=m;i++) y=y+1; for (j= 1;j<=n;j++) y=y+1; for (k= 1;k<=x;k++) y=y+1; Giải: có 3 vòng lặp for độc lập nên mỗi lần lặp y tăng lên 1 đơn vị, vậy giá trị của y=20+30+10=60 Ví dụ 4. Có bao nhiêu chuỗi 8 bit bắt đầu bằng 10 hoặc 11? Giải: Theo nguyên lý nhân có 26 chuỗi bắt đầu bằng 10 và có 26 chuỗi bắt đầu bằng 11.
Vì hai loại chuỗi này khác nhau nên ta có 2. 26 = 128 chuỗi 8 bit bắt đầu bằng 10 hoặc 11. Có bao nhiêu cách xếp 5 người đứng thành 1 hàng ngang sao cho A không đứng cạnh B Giải: theo nguyên lý nhân có 1.5=5! cách xếp 5 người thành hàng ngang A đứng cạnh B có 2.4! cách xếp, nên ta có 5!-2.4! cách xếp 16 Ví dụ 6. Một đợt phát hành sổ số với các số vé gồm 2 phần: phần chữ và phần số.
Phần chữ gồm 2 chữ cái từ A đến Z, phần số gồm 4 chữ số từ 0 đến 9. Hỏi xác xuất để trúng giải độc đắc là bao nhiêu? Giải: phần chữ gồm 26. Phần số có 104 cách chọn. Vậy theo nguyên lý nhân có m=26.104 tờ vé số khác nhau.
Nếu chỉ có 1 tờ vé trúng giải độc đắc thì xác xuất là 1/m. Đếm số cách chọn 2 quyển sách chuyên ngành khác nhau từ 6 quyển thuật toán khác nhau, 4 quyển lập trình web khác nhau, và 3 quyển lập trình C khác nhau. Giải Theo nguyên lý nhân ta có: 6x4 = 24 cách chọn 1 quyển thuật toán, 1 quyển lập trình web 6x3 = 18 cách chọn 1 quyển thuật toán, 1 quyển lập trình C 4x3 = 12 cách chọn 1 quyển lập trình web, 1 quyển lập trình C Theo nguyên lý cộng ta có: 24 + 18 + 12 = 54 cách chọn sách Ví dụ 8. Có bao nhiêu xâu nhị phân có độ dài bằng 8 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi 01 Giải Có 26 = 64 xâu nhị phân độ dài 8 bắt đầu bởi 00 và 26 =64 xâu nhị phân độ dài 8 kết thúc bởi 01.
Số xâu nhị độ dài 8 bắt đầu 00 và kết thúc 01 là 24 =16 Vậy theo nguyên lý bù trừ suy ra số xâu nhị phân có độ dài bằng 8 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi 01 là: 2.3 Giải tích tổ hợp 2.1 Chỉnh hợp lặp Ðịnh nghĩa 1. Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể được lặp lại. Một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích Ðề-các Xk, với X là tập n phần tử.
Như vậy số tất cả các chỉnh hợp lặp chập k của n là nk Ví dụ 1. Tính số ánh xạ từ tập X có k phần tử đến tập Y có n phần tử. Mỗi ánh xạ từ X vào Y tương ứng với một bộ có thứ tự k thành phần của n phần tử của Y, các phần tử có thể lặp lại. Như vậy số ánh xạ từ X vào Y là nk Ví dụ 2.