Dạng bài tập toán rời rạc cộng trừ nhân bù năm 2024
|
Toan-To-Hop - Le-Van-Luyen - Chuong-3 - Nguyen-Ly-Bu-Tru - (Cuuduongthancong - Com) 0% found this document useful (0 votes) 59 views 34 pages Original Titletoan-to-hop_le-van-luyen_chuong-3_nguyen-ly-bu-tru - [cuuduongthancong.com] Copyright© © All Rights Reserved Available FormatsPDF, TXT or read online from Scribd Share this documentDid you find this document useful?0% found this document useful (0 votes) 59 views34 pages Toan-To-Hop - Le-Van-Luyen - Chuong-3 - Nguyen-Ly-Bu-Tru - (Cuuduongthancong - Com) Links downloaded from ToanDHSP.COM Bai tap toan roi rac co giai BT Toan roi rac 1 BÀI TẬP CHƯƠNG I Bài 1: Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau. Mỗi điện thoại có 9 chữ số có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9. Giải: Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 (10 số), có 07 ký tự X do vậy sẽ có 107 trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng cần thiết là: ][ 35,2 000.000.10 000.000.25 \=\= ⎢ ⎣ ⎡ ⎥ ⎦ ⎤. Vậy số mã vùng cần thiết thỏa yêu cầu bài toán là 3. Bài 2: Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, ví dụ 75_1576_F1. Hai số đầu là mã tỉnh, X là chữ cái (26 chũ cái). N gồm các số 0, 1, …, 9. Hỏi một tỉnh nào đó cần đăng ký cho 10 triệu xe thì cần bao nhiêu serial (X). Giải Bài toán này có 02 cách hiểu: serial ở đây có thể là 02 ký tự NN đầu tiên hoặc là 02 ký tự XN cuối cùng. Cách hiểu 1: (serial là 02 ký tự XN cuối cùng). Hai số NN đầu là mã tỉnh, do nhà nước quy định nên không ảnh hưởng đến kết quả bài toán. Sáu ký tự còn lại có 5 ký tự là N, như vậy có 5 10 trường hợp. Theo nguyên lý Dirichlet, số serial X tối thiểu phải thỏa mãn: 100 000.100 000.000.10 \= ⎢ ⎣ ⎡ ⎥ ⎦ ⎤. Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. Do vậy, nếu bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, khi đó số serial là: 10 000.100 000.000.1 \= ⎢ ⎣ ⎡ ⎥ ⎦ ⎤. Cách hiểu 2: (serial là 02 ký tự NN đầu tiên) Bốn ký tự NNNN sẽ có 104 trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắc nhân, tổng số trường hợp sẽ là: 104*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểu phải là: ][ 484,3 000.600.2 000.000.10 \=\= ⎢ ⎣ ⎡ ⎥ ⎦ ⎤. Vậy cần 04 số serial để đăng ký đủ cho 10 triệu xe. Bài 3: Có bao nhiêu xâu nhị phân có độ dài 10:
Giải
Xâu nhị phân bắt đầu bằng 00 có dạng: 00.xxxx.xxxx. Ký tự x có thể là 0 hoặc 1, có 8 ký tự x do vậy có 8 2 xâu. Xâu nhị phân kết thúc bằng 11 có dạng: xx.xxxx.xx11. Tương tư ta cũng tính được có 8 2 xâu. Xâu nhị phân bắt đầu bằng 00 và kết thúc bằng 11 có dạng 00.xxxx.xx11. Tương tự như trên, ta cũng tính được có 6 2 xâu. Vậy số xâu nhị phân bắt đầu bằng 00 hay kết thúc bằng 11 là: |
