Tổng hợp bài tập phép đếm của những nguyên lý cơ bản: nguyên lý cộng, nguyên lý nhân, nguyên lý loại trừ, nguyên lý bù trừ, nguyên lý quy về đơn giản, nguyên lý truy hồi để giải bài tập phép đếm
Bạn đang xem: Phép đếm
Tóm tắt lý thuyết về bài tập phép đếm
1.Nguyên lý cộng
Bài 1: Giả sử cần chọn ra 1 đại diện học sinh tham gia dự thi Olympic Tin học. Biết thể lựa chọn học sinh khối 11 và khối 12. Hỏi có bao nhiêu lựa chọn khác nhau nêu có 300 học sinh khối 11 và 260 em học sinh khối 12.
Giải
Có 300 cách chọn 1 học sinh khối 11
Có 260 cách chọn 1 học sinh khối 12
Theo nguyên lý cộng: 300 + 260 = 560 cách
Bài 2: Một sinh viên có thể lựa chọn đề tài từ 1 trong 3 danh sách. Mỗi danh sách lần lượt chứa 10, 20 và 30 đề tài khác nhau tương ứng. Mỗi đề tài chỉ xuất hiện trong 1 danh sách, Một sinh viên có bao nhiêu cách lựa chọn đề tài?
Giải
Sinh viên có thể chọn đề tài từ 1 trong 3 danh sách và không bị lặp lại.
Nên theo nguyên lý cộng có 10 + 20 + 30 = 60 cách
Bài 3: Giá trị k là bao nhiêu sau khi thực hiện đoạn mã sau:
k: = 0;
for i: = 1 to 5 do
k: = k + 1;
Giải
Giá trị khởi tạo k=0
Lệnh thực hiện vòng lặp 5 lần, mỗi lần k tăng thêm 1 => theo nguyên lý cộng k=5
Bài 4: Một mật khẩu có độ dài từ 7 đến 8 kí tự. Trong đó có 1 chữ cái hoa tiếng anh hoặc 1 chữ số, Mỗi mật khẩu phải chứa ít nhất 1 chữ số. Có bao nhiêu mật khẩu có thể có?
Giải
Số lượng mật khẩu chứa kí tự là 367
Số lượng mật khẩu chỉ chứa chữ cái hoa là 267
Số lượng mật khẩu chứa kí tự là 368
Số lượng mật khẩu chỉ chứa chữ cái hoa là 268
Vậy số lượng mật khẩu chứa ít nhất 1 chữ số là: 367 + 368 – 267 – 268
2.Nguyên lý nhân
Bài 1: Để tạo số báo danh cho học sinh bao gồm 1 chữ cái hoa tiếng anh và 1 chữ số không vượt quá 100. Hỏi số lượng lớn nhất số báo danh có thể có là bao nhiêu?
Giải
Số lượng số báo danh lớn nhất là : 26*100 = 2600
Bài 2: Có bao nhiêu chuỗi bit có độ dài là 7?
Giải
Mỗi bít có 2 cách lựa chọn do đó: 27
Bài 3: Có bao nhiêu ham từ tập m phần tử đến tập n phần tử? nm
3.Nguyên lý loại trừ
Giả sử 1 công việc có thể thực hiện 1 trong 2 cách nhưng có một số cách bị trùng
| A 1 ∪ A 2 | = | A 1 | + | A 2 | – | A 1 ∩ A 2 |
Bài 1: Có bao nhiêu chuỗi bit có độ dài 8 hoặc bắt đầu bằng 1 hoặc bắt đầu bằng 00
Giải
Chuỗi bit bắt đầu bằng 1 là: 27
Chuỗi bit bắt đầu bằng 00 là:26
Chuỗi bit trùng nhau bắt đầu bằng 1 và 00 là: 25
Theo nguyên lý trừ ta có: 27 + 26 – 25
4.Nguyên lý chia
Một công việc A có n cách thực hiện, đồng thời nó cũng được thực hiện theo k phương án khác nhau, mỗi phương án có đúng d cách thực hiện.
Xem thêm: Điều Kiện Tự Nhiên Của Nhật Bản Có Thuận Lợi Và Khó Khăn Gì, Điều Kiện Tự Nhiên Của Nhật Bản
Thì số phướng án khác nhau để thực hiện A là k=n/d
5.Nguyên lý Dirichle
Bài 1: Cần bao nhiêu học sinh để đảm bảo có ít nhất 2 học sinh trùng điểm nhau , nếu điểm được cho từ 0 – 10?
Giải
Cần ít nhất 12 học sinh
Bài 2: Cần tối thiểu bao nhiêu sinh viên để đảm bảo rằng ít nhất 3 sinh viên cùng nhận kết quả đánh giá, nếu có 5 điểm để đánh giá A, B, C, D, F
Giải
Số sinh viên tối thiểu là:
6.Hoán vị
Hoán vị là cách sắp xếp có thứ tự tất cả n phần tử
Bài 1: Người ta sắp xếp ngẫu nhiên 5 lá phiếu có ghi số thứ tự từ 1 đến 5
a.Có bao nhiêu cách sắp xếp số chẵn ở cạnh nhau?
Coi hai số chẵn là 1 => có 2!.4! =48 cách
b.Có bao nhiêu cách sắp xếp hai thành 2 nhóm chẵn lẻ riêng biệt (2!.3!.2=24)
7.Tổ hợp và chỉnh hợp
Chỉnh hợp chập k của n phần tử
Vậy số nghiệm là tổng của 4 trường hợp: 455+ 1820 + 6188 + 18564 =27027
Câu 4. Có bao nhiêu cách chia 52 quân bài cho 5 người, trong đó:a) Có 4 người mỗi người 7 quân và một người 12 quân?b) Có 4 người mỗi người nhận 6 quân đỏ và 6 quân đen và 1 người nhận 2 quân đỏ và 2quân đen