Bo de toan roi rac [on thi cao hoc khmt] from lieu_lamlam
Bai Tap Toan Roi Rac - Co Loi GiaiUploaded by
Dinh Tai Nguyen
0%[1]0% found this document useful [1 vote]
7K views26 pagesAI-enhanced title
Document Information
click to expand document informationOriginal Title
ToanDHSP.COM_Bai-tap-Toan-roi-rac_co-loi-giai
Copyright
© Attribution Non-Commercial [BY-NC]
Available Formats
PDF, TXT or read online from Scribd
Share this document
Share or Embed Document
Sharing Options
- Share with Email, opens mail client
Email
Did you find this document useful?
0%0% found this document useful, Mark this document as useful
100%100% found this document not useful, Mark this document as not useful
Is this content inappropriate?
Download now
SaveSave ToanDHSP.COM_Bai-tap-Toan-roi-rac_co-loi-giai For Later
0%[1]0% found this document useful [1 vote]
Bai Tap Toan Roi Rac - Co Loi Giai
Uploaded by
Dinh Tai NguyenAI-enhanced title
SaveSave ToanDHSP.COM_Bai-tap-Toan-roi-rac_co-loi-giai For Later
0%0% found this document useful, Mark this document as useful
100%100% found this document not useful, Mark this document as not useful
EmbedShare
PrintDownload now
Jump to Page
You are on page 1of 26Search inside document
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ó 10
7
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: 100000.100000.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à: 10000.100000.000.1
=
⎢⎣⎡⎥⎦⎤
.
Cách hi
ể
u 2:
[serial là 02 ký t
ự
NN
đầ
u tiên
]
B
ố
n ký t
ự
NNNN s
ẽ
có 10
4
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à: 10
4
*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: a.
B
ắ
t
đầ
u b
ằ
ng 00 ho
ặ
c k
ế
t thúc b
ằ
ng 11.
b.
B
ắ
t
đầ
u b
ẳ
ng 00 và k
ế
t thúc b
ằ
ng 11.
Gi
ả
i
a.
B
ắ
t
đầ
u b
ằ
ng 00 ho
ặ
c k
ế
t thúc b
ằ
ng 11. 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à:
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai
BT Toan roi rac 2 4486451222*2
68
=−=−=
n
xâu. b.
B
ắ
t
đầ
u b
ằ
ng 00 và k
ế
t thúc b
ằ
ng 11. Xâu nh
ị
phân th
ỏ
a mãn
đề
bài ph
ả
i có d
ạ
ng: 00.xxxx.xx11. Hai ký t
ự
đầ
u và 02 ký t
ự
cu
ố
i là không
đổ
i, do v
ậ
y ch
ỉ
còn 06 ký t
ự
ở
gi
ữ
a. Do
đ
ó s
ố
xâu nh
ị
phân th
ỏ
a mãn
đề
bài là: 2
6
xâu.
Bài 4: Khóa 29 CNTT có 150 SV h
ọ
c NNLT Java, 160 SV hoc Delphi, 40 SV h
ọ
c c
ả
hai môn trên. a.
Tìm t
ấ
t c
ả
SV c
ủ
a khóa 29 bi
ế
t r
ằ
ng SV nào c
ũ
ng ph
ả
i h
ọ
c ít nh
ấ
t 01 môn. b.
Bi
ế
t t
ổ
ng s
ố
SV là 285, h
ỏ
i có bao nhiêu SV không h
ọ
c Java ho
ặ
c Delphi. Gi
ả
i
G
ọ
i J: SV h
ọ
c Java D: SV h
ọ
c Delphi a.
S
ố
SV c
ủ
a khóa 29 là: 27040160150
1
=−+=−+==
D J D J D J n
IU
SV b.
Câu b có 02 cách hi
ể
u:
Cách 01:
không h
ọ
c ít nh
ấ
t 01 môn. S
ố
SV không h
ọ
c Java ho
ặ
c Delphi là [áp d
ụ
ng nguyên lý bù tr
ừ
] ta tính
đượ
c:
24540285
2
=−=−=
D J nn
I
SV
Cách 02:
không h
ọ
c Java c
ũ
ng ch
ẳ
ng h
ọ
c Delphi: Theo cách hi
ể
u này, áp d
ụ
ng nguyên lý bù tr
ừ
ta tính
đượ
c s
ố
SV nh
ư
sau: 1540160150285
'2
=+−−=+−−==
D J D J n D J n
IU
SV
Bài 5: M
ỗ
i ng
ườ
i s
ử
d
ụ
ng máy tính dùng password có 6 -> 8 ký t
ự
. Các ký t
ự
có th
ể
là ch
ữ
s
ố
ho
ặ
c ch
ữ
cái, m
ỗ
i password ph
ả
i có ít nh
ấ
t 01 ch
ữ
s
ố
. Tìm t
ổ
ng s
ố
password có th
ể
có. Gi
ả
i
Bài toán này c
ũ
ng có th
ể
đượ
c hi
ể
u theo 02 cách.
Cách 01:
phân bi
ệ
t ch
ữ
th
ườ
ng v
ớ
i ch
ữ
hoa. Ch
ữ
cái th
ườ
ng: 26 Ch
ữ
cái hoa: 26 Ch
ữ
s
ố
: 10 Do
đ
ó, t
ổ
ng c
ộ
ng có 26 + 26 + 10 = 62 ký t
ự
khác nhau. N
ế
u password có n ký t
ự
. T
ổ
ng s
ố
tr
ườ
ng h
ợ
p:
n
62 S
ố
password không có ch
ữ
s
ố
:
n
52 Suy ra s
ố
password có ít nh
ấ
t 01 ch
ữ
s
ố
:
nnn
n
5262
−=
Áp d
ụ
ng cho các tr
ườ
ng h
ợ
p n = 6, 7, 8. T
ổ
ng s
ố
password th
ỏ
a yêu c
ầ
u
đề
bài là:
040.583.949.410.167526252625262
887766 876
=−+−+−=++=
nnnn
Cách 02:
không phân bi
ệ
t ch
ữ
th
ườ
ng v
ớ
i ch
ữ
hoa: Cách làm hoàn toàn t
ươ
ng t
ự
, nh
ư
ng thay vì s
ử
d
ụ
ng các s
ố
62 và 52 thì
ở
đ
ây s
ử
d
ụ
ng 02 s
ố
: 36 và 26. K
ế
t qu
ả
s
ẽ
là:
063.3602.684.483.263626362636
887766 876
=−+−+−=++=
nnnn
Bài 6: Có n lá th
ư
b
ỏ
vào n bì th
ư
. H
ỏ
i xác su
ấ
t
để
x
ả
y ra tr
ườ
ng h
ợ
p không có lá th
ư
nào b
ỏ
đ
úng
đượ
c bì th
ư
c
ủ
a nó. Gi
ả
i
Share this document
Share or Embed Document
Sharing Options
- Share with Email, opens mail client