Có bao nhiêu xâu nhị nhân có độ dài bằng 8 có đúng 3 bit 1
|
Bo de toan roi rac (on thi cao hoc khmt) from lieu_lamlam Show Bai Tap Toan Roi Rac - Co Loi Giai 0%(1)0% found this document useful (1 vote) 7K views26 pagesAI-enhanced title Document Informationclick to expand document informationOriginal TitleToanDHSP.COM_Bai-tap-Toan-roi-rac_co-loi-giai Copyright© Attribution Non-Commercial (BY-NC) Available FormatsPDF, TXT or read online from Scribd Share this documentShare or Embed DocumentSharing Options
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 byDinh 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 documentShare or Embed DocumentSharing Options
|
