Có bao nhiêu xâu có độ dài 10 bit có đúng 3 số 0

* Học phần: Toán rời rạc
* Loại đề: Đề thi kết thúc học phần
* Ngày thi: Chưa xác định
* Đối tượng: Dành cho lớp SPTin1A & 1B - CNTT 1A & 1B & 1C
* Thời gian: 90 phút
* Tài liệu: Được phép sử dụng tài liệu
* Đáp án: Có đáp án
* Người soạn đề: Chưa xác định

Câu 1 [2 điểm]
a. Trong một cuộc thi trắc nghiệm có 100 câu hỏi đúng/sai. Có bao nhiêu các một sinh viên có thể trả lời tất cả câu hỏi đó nếu một câu trả lời có thể để trống? 0.5đ
b. Một đội bóng có 22 cầu thủ.
 - Có bao nhiêu cách chọn 11 cầu thủ để ra sân? 0.5đ
 - Có bao nhiêu cách chọn 11 cầu thủ để ra sân và bố trí vào các vị trí khác nhau trong đội hình? 0.5đ
c. Có bao nhiêu xâu bít có thể tạo thành từ 6 bít 1 và tám bít 0? 0.5đ

Câu 2 [2 điểm]
a. Có bao nhiêu xâu chữ có từ 7 kí tự trở lên có thể được tạo ra bằng cách sử dụng các chữ cái trong từ EVERGREEN? 0.5đ
b. Xếp 10 cuốn sách vào 4 ngăn sách của một giá sách. Có bao nhiêu cách xếp nếu:
 - Các cuốn sách là không thể phân biệt? 0.5đ
 - Các cuốn sách là khác nhau nhưng vị trí trong ngăn là không quan trọng? 0.5đ
 - Có 3,3,2,2 cuốn sách trên mỗi ngăn, các cuốn sách là khác nhau và vị trí trong ngăn được tính đến?

Câu 3 [2 điểm]
a. Có bao nhiêu xâu bít có độ dài bằng 10 bắt đầu bằng 101 hoặc kết thúc bằng 010? 1đ
b. Xây dựng hệ thức truy hồi cho số các xâu bít có độ dài bằng n có chứa hai bit 0 liên tiếp [n ≥ 3]. 1đ

Câu 4 [2 điểm]
Kí hiệu N là tập các số tự nhiên. Trên tập tích Đềcác N3 định nghĩa quan hệ R như sau:

[a,b,c] R [d,e,f] ⇔ a+b+c = d+e+f

a. Chứng minh R là một quan hệ tương đương. 1đ
b. Đếm số phần tử của lớp tương đương [[2011,2012,2013]]R trong quan hệ R. 1đ

Câu 5 [2 điểm]
Một hội đồng gồm 4 người biểu quyết các vấn đề của một công ty. Với một vấn đề, một người có thể bỏ
phiếu tán thành hoặc không tán thành. Một vấn đề sẽ được thông qua nếu người thứ nhất và người thứ hai
bỏ phiếu tán thành hoặc ít nhất 3 người bỏ phiếu tán thành. Chúng ta cần thiết kế một mạch sử dụng 3 cổng
logic cơ bản NOT, AND, OR cho công việc biểu quyết trên.
a] Xây dựng bảng giá trị cho mạch như mô tả trên. 0.5đ
b] Tìm công thức tối tiểu của mạch trên. 1đ
c] Dùng công thức tối tiểu để vẽ mạch. 0.5đ

Đáp án tham khảo

Nguồn: //drive.google.com/open?id=0B8vTpNzLyh6keEhCUkFvZktsWGs

Đề thi nổi bật

150+ câu trắc nghiệm môn SPSS

168 câu 1430 lượt thi

390+ câu hỏi trắc nghiệm Hóa lí dược

392 câu 1169 lượt thi

Trắc nghiệm Toán cao cấp C3

82 câu 53 lượt thi

525 câu trắc nghiệm môn Toán rời rạc

525 câu 1675 lượt thi

500 câu trắc nghiệm Phương pháp nghiên cứu khoa học

500 câu 1359 lượt thi

1300+ câu trắc nghiệm môn Kinh tế học đại cương

1372 câu 715 lượt thi

265 câu trắc nghiệm môn Đại số tuyến tính

265 câu 1370 lượt thi

850 câu trắc nghiệm môn Hóa học đại cương

850 câu 1130 lượt thi

1350 Câu trắc nghiệm môn Sinh học đại cương

1346 câu 6494 lượt thi

Trắc nghiệm môn Toán cao cấp A1

122 câu 240 lượt thi

Bai Tap Toan Roi Rac - Co Loi Giai

Uploaded by

Dinh Tai Nguyen

0%[1]0% found this document useful [1 vote]

7K views26 pages

Document Information

click to expand document information

Original 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]

7K views26 pages

Bai Tap Toan Roi Rac - Co Loi Giai

Uploaded by

Dinh Tai Nguyen

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

Embed

Share

Print

Download now

Jump to Page

You are on page 1of 26

Search 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