Bài tập môn toán rời rạc

Chia sẻ: Nguyen Quoc Chinh | Ngày: | Loại File: DOC | Số trang:5

Thêm vào BST

Báo xấu

288
lượt xem 64
download

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

Câu 1 Tốt nghiệp 2007 (Đợt 1) Cho xâu S = “AABCCDD” có |S| = 7, Có bao nhiêu xâu tạo ra từ S thỏa: a) Chữ b đứng chính giữa xâu (dạng ***B***) C1: Chữ B giữ 1 vị trí ở giữa xâu, nên 6 vị trị còn

Chủ đề:

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

Lưu

Nội dung Text: Bài tập môn toán rời rạc

Câu 1 Tốt nghiệp 2007 (Đợt 1) Cho xâu S = “AABCCDD” có |S| = 7, Có bao nhiêu xâu tạo ra từ S thỏa: Chữ b đứng chính giữa xâu (dạng ***B***) a) C1: Chữ B giữ 1 vị trí ở giữa xâu, nên 6 vị trị còn lại là hoán vị lặp của 6 giá chữ còn lại: 6! /(2!x2!x2!) = 90 (xâu) C2: Chia trường hợp a thành 2 trường hợp (Với ** là 2 ký tự trùng nhau, * là 1 ký tự khác, ví dụ AACBCDD,ACABDDC,…) Sẽ có 6 trường hợp cho mỗi ký tự lặp (***): AAD,AAC,CCA,CCD,DDA,DDC Và mỗi trường hợp sẽ là hoán vị lặp của 1 ký tự : C32 = 3 Vậy với mỗi xâu có dạng TTEBETT có 3x3 = 9 trường hợp (vì có dạng ***B***) Vậy trường hợp 1 có 6x9 = 54 (xâu) Trường hợp 2 gồm các *** có dạng 3 ký tự khác nhau :C,A,D Trường hợp 2 có 3!x3! = 36(xâu) Vậy tổng trường hợp a có 90 (xâu) b)Hai chữ A không đứng kề nhau: 2 chữ A đứng kề nhau có 6 trường hợp Vậy tổng xâu trường hợp B 7!/(2!x1!x2!x2!x2!) – 6 = 624(xâu) c)Hai chữ A không đứng kề nhau và 2 chữ C không đứng kề nhau Gọi S là số xâu có 2 chữ A đứng kề nhau và 2 chữ C đứng kề nhau S = 5! / 2! = 60 (xâu) Tổng xâu : 630 – 60 = 570 (xâu) d)chữ B đứng trước tất cả chữ A : 630 / 3 = 210(xâu)
Câu 1 tốt nghiệp 2007 (đợt 2) Cho X là tập các số nguyên trong đoạn [100,1000], trong X có bao nhiêu số thỏa mãn điều kiện sau: a) Số vừa chia hết cho 4 và 6 100
Trong quá trình lặp sẽ có các cặp số 100,200,…,900 bị trùng 1 giá trị, Vậy tổng số xâu là : 181 – 9 = 172 f) Số chứa đúng 1 số 7: C1: số có dạng A** với A = [1,9] / {7}, Số 7 nằm 1 trong 2 vị trí **, vị trí còn lại có 9 giá trị ([0,9]/7) 8x2x9 = 144 (số) Với A = 7, 2 vị trí còn lại mỗi vị trí có 9 giá trị ([0,9] / {7}) 9x9 = 81 (số) Vậy tổng số : 144 + 81 = 225 (số) C2: Số có dạng 7** : 9x9 = 81 (số) Số có dạng *7*: 8 x 9 = 72 (số) Số có dạng **7: 8x9 = 72(số) Tổng : 144 + 81 = 225 (số) Câu 1 tốt nghiệp năm 2010 (đợt 1) Cho 3 hộp bút bi, trong đó có một hộp bút màu xanh, một hộp bút màu đỏ và một hộp bút màu đen. Số lượng bút trong mỗi hộp là 10 cây và các cây bút trong mỗi hộp có hình thức và chất lượng như nhau. Có bao nhiêu cách lấy ra 10 cây bút từ 3 hộp bút đã cho thỏa mãn từng điều kiện sau đây: Lý thuyết: Lấy n phần tử từ k loại : Cnn+k-1 a)Số bút lấy ra ít nhất là 3: Trong 10 cây bút, ta lấy ra 3 cây bút màu xanh, còn lại 7 cây được lấy từ 3 loại bút ( vẫn tính bút màu xanh) Tập nghiệm: C79 b) Số bút màu xanh lấy ra nhiều nhất là 3: Với 10 cây bút lấy ra từ 3 loại, ta sẽ có tập nghiệm: C1012 Với 10 cây bút lấy ra sao cho số bút màu xanh lấy ra ít nhất là 4, tập nghiệm: C68 Vậy tập nghiệm cần tìm : C1012 – C68
c) Số bút mỗi màu lấy ra ít nhất là 2: Lập luận tương tự câu a, với 10 cây bút lấy ra, mỗi màu ta lấy ra 2 cây, vậy còn 4 cây bút được lấy ra từ 3 loại, tập nghiệm: C46 d) Số bút màu xanh ít nhất là 3 và số bút màu đỏ nhiều nhất là 4: Ta có số bút mày xanh lấy ra ít nhất là 3 có tập nghiệm C79 (a), trong số này có cả tập nghiệm số bút màu đỏ nhiều nhất là 4 và tập nghiệm số bút màu đỏ ít nhất là 5: Với 7 cây bút lấy ra từ 3 loại sao cho số bút màu đỏ lấy ra ít nhất là 5: C24 Vậy tập nghiệm cần tìm : C79 – C24 Câu 2: Một mật khẩu đọ dài 8 dạng XXXXXXYY, trong đó X là một chữ cái thường lấy trong các chữ cái a,b,c,d và Y là một chữ số lấy trong các chữ số 0,1,…,9. Hỏi trong trường hợp xấu nhất phải thử bao nhiêu lần để phát hiện mật khẩu nếu: a) Mật khẩu bắt đầu bằng chữ a: X ở vị trí 1 là a, 5 X còn lại mỗi X có thể có 4 trường hợp, và 2 Y mỗi Y có 10 trường hợp, vậy số lần thử là : 45 x 102 b) Mật khẩu bắt đầu bằng chữ a hoặc kết thúc bằng chữ số 9: Gọi P là số lần thử chuỗi kết thúc bằng 9 : 46 x 10 Gọi P là số lần thử chuỗi bắt đầu bằng a và kết thúc bằng 9 : 45 x 10 Số lần thử câu b : 45 x 102 + 46 x 10 – 45 x 10 Câu 1 tốt nghiệp 2009 ( đợt 1) Một số nguyên dương được gọi là số palindrome nếu như khi đọc nó từ trái qua phải cũng như từ phải qua trái ta được cùng một số. Ví dụ : 1001, 20502 là các số palindrome. Hỏi có bao nhiêu xâu trong tập X = {1,2,…,1000000} Từ 1 đến 1000.000 gồm các số có 1,2,3,4,5,6 chữ số, xét từng trường hợp: Với độ dài bằng 1([1,9]) : có 9 số Với độ dài bằng 2([10,99]): Có 9 trường hợp :11,22,…,99 Với độ dài bằng 3([100,999]): Xâu palindrome có dạng : A*A với A={1,9} Số xâu : 9x10 = 90 (số) Với độ dài bằng 4([1000,9999]): Xâu palindrome có dạng: A**A với A = {1,9}, với mỗi ** là cặp số trùng nhau
Số xâu : 9 x 10 = 90 (Số) Với độ dài bằng 5([10000,99999]): Xâu palindrome có dạng: A*B*A với A = {1,9}, ** là cặp số trùng nhau, B = {0,9} Số xâu : 9 x 10 x 10 = 900 (Số) Với độ dài bằng 6([100000,999999]): Xâu palindrome có dạng: A*BB*A với A = {1,9}, ** là các cặp trùng nhau, BB là các cặp trùng nhau Số xâu : 9 x 10 x 10 = 900 (số) Vậy tổng số là : 900 x 2 + 90 x 2 + 9 x 2 Câu 2: Cho X là tập các xâu tam phân độ dài 8 chứa đúng 3 chữ số 0, 3 chữ số 1, 2 chữ số 2. Hỏi có bao nhiêu xau thỏa mãn từng điều kiện sau đây: a) Xâu bắt đầu bằng “00” : Có dạng 00****** 1 số 0 còn lại chiếm 1 vị trí, 3 chữ số 1 chiếm 3 vị trí, còn 2 vị trí của 2 số 2 C36 x C13 b) Xâu kết thúc bằng “22”: Có dạng ******22 3 số 0 chiếm 3 vị trí, còn 3 vị trí của 3 số 1 C36 Không thỏa 2 điều kiện trên: c)