BÀI TOÁN ĐẾM

Chia sẻ: vunguyen105

Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu.

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: BÀI TOÁN ĐẾM

http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
CHƯƠNG II
BÀI TOÁN ð M
Lý thuy t t h p là m t ph n quan tr ng c a toán h c r i r c chuyên nghiên c u
s phân b các ph n t vào các t p h p. Thông thư ng các ph n t này là h u h n và
vi c phân b chúng ph i tho mãn nh ng ñi u ki n nh t ñ nh nào ñó, tùy theo yêu c u
c a bài toán c n nghiên c u. M i cách phân b như v y g i là m t c u hình t h p. Ch
ñ này ñã ñư c nghiên c u t th k 17, khi nh ng câu h i v t h p ñư c nêu ra trong
nh ng công trình nghiên c u các trò chơi may r i. Li t kê, ñ m các ñ i tư ng có nh ng
tính ch t nào ñó là m t ph n quan tr ng c a lý thuy t t h p. Chúng ta c n ph i ñ m các
ñ i tư ng ñ gi i nhi u bài toán khác nhau. Hơn n a các k thu t ñ m ñư c dùng r t
nhi u khi tính xác su t c a các bi n c .
2.1. CƠ S C A PHÉP ð M.
2.1.1. Nh ng nguyên lý ñ m cơ b n:
1) Quy t c c ng: Gi s có k công vi c T1, T2, ..., Tk. Các vi c này có th làm tương
ng b ng n1, n2, ..., nk cách và gi s không có hai vi c nào có th làm ñ ng th i. Khi ñó
s cách làm m t trong k vi c ñó là n1+n2+ ... + nk.
Thí d 1: 1) M t sinh viên có th ch n bài th c hành máy tính t m t trong ba danh
sách tương ng có 23, 15 và 19 bài. Vì v y, theo quy t c c ng có 23 + 15 + 19 = 57
cách ch n bài th c hành.
2) Giá tr c a bi n m b ng bao nhiêu sau khi ño n chương trình sau ñư c th c hi n?
m := 0
for i1 := 1 to n1
m := m+1
for i2 :=1 to n2
m := m+1
.......................
for ik := 1 to nk
m := m+1
Giá tr kh i t o c a m b ng 0. Kh i l nh này g m k vòng l p khác nhau. Sau m i
bư c l p c a t ng vòng l p giá tr c a k ñư c tăng lên m t ñơn v . G i Ti là vi c thi
hành vòng l p th i. Có th làm Ti b ng ni cách vì vòng l p th i có ni bư c l p. Do các
vòng l p không th th c hi n ñ ng th i nên theo quy t c c ng, giá tr cu i cùng c a m
b ng s cách th c hi n m t trong s các nhi m v Ti, t c là m = n1+n2+ ... + nk.
Quy t c c ng có th phát bi u dư i d ng c a ngôn ng t p h p như sau: N u A1,
A2, ..., Ak là các t p h p ñôi m t r i nhau, khi ñó s ph n t c a h p các t p h p này
b ng t ng s các ph n t c a các t p thành ph n. Gi s Ti là vi c ch n m t ph n t t

22
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

t p Ai v i i=1,2, ..., k. Có |Ai| cách làm Ti và không có hai vi c nào có th ñư c làm
cùng m t lúc. S cách ch n m t ph n t c a h p các t p h p này, m t m t b ng s ph n
t c a nó, m t khác theo quy t c c ng nó b ng |A1|+|A2|+ ... +|Ak|. Do ñó ta có:
|A1 ∪ A2 ∪...∪ Ak| = |A1| + |A2| + ... + |Ak|.
2) Quy t c nhân: Gi s m t nhi m v nào ñó ñư c tách ra thành k vi c T1, T2, ..., Tk.
N u vi c Ti có th làm b ng ni cách sau khi các vi c T1, T2, ... Ti-1 ñã ñư c làm, khi ñó
có n1.n2....nk cách thi hành nhi m v ñã cho.
Thí d 2: 1) Ngư i ta có th ghi nhãn cho nh ng chi c gh trong m t gi ng ñư ng b ng
m t ch cái và m t s nguyên dương không vư t quá 100. B ng cách như v y, nhi u
nh t có bao nhiêu chi c gh có th ñư c ghi nhãn khác nhau?
Th t c ghi nhãn cho m t chi c gh g m hai vi c, gán m t trong 26 ch cái và
sau ñó gán m t trong 100 s nguyên dương. Quy t c nhân ch ra r ng có 26.100=2600
cách khác nhau ñ gán nhãn cho m t chi c gh . Như v y nhi u nh t ta có th gán nhãn
cho 2600 chi c gh .
2) Có bao nhiêu xâu nh phân có ñ dài n.
M i m t trong n bit c a xâu nh phân có th ch n b ng hai cách vì m i bit ho c
b ng 0 ho c b ng 1. B i v y theo quy t c nhân có t ng c ng 2n xâu nh phân khác nhau
có ñ dài b ng n.
3) Có th t o ñư c bao nhiêu ánh x t t p A có m ph n t vào t p B có n ph n t ?
Theo ñ nh nghĩa, m t ánh x xác ñ nh trên A có giá tr trên B là m t phép tương
ng m i ph n t c a A v i m t ph n t nào ñó c a B. Rõ ràng sau khi ñã ch n ñư c nh
c a i - 1 ph n t ñ u, ñ ch n nh c a ph n t th i c a A ta có n cách. Vì v y theo quy
t c nhân, ta có n.n...n=nm ánh x xác ñ nh trên A nh n giá tr trên B.
4) Có bao nhiêu ñơn ánh xác ñ nh trên t p A có m ph n t và nh n giá tr trên t p B có n
ph n t ?
N u m > n thì v i m i ánh x , ít nh t có hai ph n t c a A có cùng m t nh, ñi u
ñó có nghĩa là không có ñơn ánh t A ñ n B. Bây gi gi s m ≤ n và g i các ph n t
c a A là a1,a2,...,am. Rõ ràng có n cách ch n nh cho ph n t a1. Vì ánh x là ñơn ánh
nên nh c a ph n t a2 ph i khác nh c a a1 nên ch có n - 1 cách ch n nh cho ph n t
a2. Nói chung, ñ ch n nh c a ak ta có n - k + 1 cách. Theo quy t c nhân, ta có
n!
n(n − 1)(n − 2)...(n − m + 1) =
( n − m)!
ñơn ánh t t p A ñ n t p B.
5) Giá tr c a bi n k b ng bao nhiêu sau khi chương trình sau ñư c th c hi n?
m := 0
for i1 := 1 to n1
for i2 := 1 to n2

23
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

.......................
for ik := 1 to nk
k := k+1
Giá tr kh i t o c a k b ng 0. Ta có k vòng l p ñư c l ng nhau. G i Ti là vi c thi
hành vòng l p th i. Khi ñó s l n ñi qua vòng l p b ng s cách làm các vi c T1, T2, ...,
Tk. S cách th c hi n vi c Tj là nj (j=1, 2,..., k), vì vòng l p th j ñư c duy t v i m i giá
tr nguyên ij n m gi a 1 và nj. Theo quy t c nhân vòng l p l ng nhau này ñư c duy t
qua n1.n2....nk l n. Vì v y giá tr cu i cùng c a k là n1.n2....nk.
Nguyên lý nhân thư ng ñư c phát bi u b ng ngôn ng t p h p như sau. N u A1,
A2,..., Ak là các t p h u h n, khi ñó s ph n t c a tích Descartes c a các t p này b ng
tích c a s các ph n t c a m i t p thành ph n. Ta bi t r ng vi c ch n m t ph n t c a
tích Descartes A1 x A2 x...x Ak ñư c ti n hành b ng cách ch n l n lư t m t ph n t c a
A1, m t ph n t c a A2, ..., m t ph n t c a Ak. Theo quy t c nhân ta có:
|A1 x A2 x ... x Ak| = |A1|.|A2|...|Ak|.
2.1.2. Nguyên lý bù tr :
Khi hai công vi c có th ñư c làm ñ ng th i, ta không th dùng quy t c c ng ñ
tính s cách th c hi n nhi m v g m c hai vi c. ð tính ñúng s cách th c hi n nhi m
v này ta c ng s cách làm m i m t trong hai vi c r i tr ñi s cách làm ñ ng th i c
hai vi c. Ta có th phát bi u nguyên lý ñ m này b ng ngôn ng t p h p. Cho A1, A2 là
hai t p h u h n, khi ñó
|A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.
T ñó v i ba t p h p h u h n A1, A2, A3, ta có:
|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A2 ∩ A3| − |A3 ∩ A1| + |A1 ∩ A2 ∩ A3|,
và b ng quy n p, v i k t p h u h n A1, A2, ..., Ak ta có:
| A1 ∪ A2 ∪ ... ∪ Ak| = N1 − N2 + N3 − ... + (−1)k-1Nk,
trong ñó Nm (1 ≤ m ≤ k) là t ng ph n t c a t t c các giao m t p l y t k t p ñã cho,
nghĩa là
Nm = ∑ | Ai1 ∩ Ai2 ∩ ... ∩ Aim |
1≤i1 aj+2 > ... > an, t c là tìm c p
s nguyên li n k ñ u tiên tính t bên ph i sang bên trái c a hoán v mà s ñ u nh hơn
s sau. Sau ñó, ñ nh n ñư c hoán v li n sau ta ñ t vào v trí th j s nguyên nh nh t
trong các s l n hơn aj c a t p aj+1, aj+2, ..., an, r i li t kê theo th t tăng d n c a các s
còn l i c a aj, aj+1, aj+2, ..., an vào các v trí j+1, ..., n. D th y không có hoán v nào ñi
sau hoán v xu t phát và ñi trư c hoán v v a t o ra.
Thí d 11: Tìm hoán v li n sau theo th t t ñi n c a hoán v 4736521.
C p s nguyên ñ u tiên tính t ph i qua trái có s trư c nh hơn s sau là a3 = 3
và a4 = 6. S nh nh t trong các s bên ph i c a s 3 mà l i l n hơn 3 là s 5. ð t s 5
vào v trí th 3. Sau ñó ñ t các s 3, 6, 1, 2 theo th t tăng d n vào b n v trí còn l i.
Hoán v li n sau hoán v ñã cho là 4751236.
procedure Hoán v li n sau (a1, a2, ..., an) (hoán v c a {1,2,...,n} khác (n, n−1, ..., 2, 1))
j := n − 1
while aj > aj+1
j := j − 1 {j là ch s l n nh t mà aj < aj+1}
k := n
while aj > ak
k := k - 1 {ak là s nguyên nh nh t trong các s l n hơn aj và bên ph i aj}
ñ i ch (aj, ak)
r := n
s := j + 1
while r > s
ñ i ch (ar, as)
r := r - 1 ; s := s + 1
{ði u này s x p ph n ñuôi c a hoán v sau v trí th j theo th t tăng d n.}


30
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

2.4.2. Sinh các t h p:
Làm th nào ñ t o ra t t c các t h p các ph n t c a m t t p h u h n? Vì t
h p chính là m t t p con, nên ta có th dùng phép tương ng 1-1 gi a các t p con c a
{a1,a2,...,an} và xâu nh phân ñ dài n.
Ta th y m t xâu nh phân ñ dài n cũng là khai tri n nh phân c a m t s nguyên
n m gi a 0 và 2n − 1. Khi ñó 2n xâu nh phân có th li t kê theo th t tăng d n c a s
nguyên trong bi u di n nh phân c a chúng. Chúng ta s b t ñ u t xâu nh phân nh
nh t 00...00 (n s 0). M i bư c ñ tìm xâu li n sau ta tìm v trí ñ u tiên tính t ph i qua
trái mà ñó là s 0, sau ñó thay t t c s 1 bên ph i s này b ng 0 và ñ t s 1 vào
chính v trí này.
procedure Xâu nh phân li n sau (bn-1bn-2...b1b0): xâu nh phân khác (11...11)
i := 0
while bi = 1
begin
bi := 0
i := i + 1
end
bi := 1
Ti p theo chúng ta s trình bày thu t toán t o các t h p ch p k t n ph n t
{1,2,...,n}. M i t h p ch p k có th bi u di n b ng m t xâu tăng. Khi ñó có th li t kê
các t h p theo th t t ñi n. Có th xây d ng t h p li n sau t h p a1a2...ak b ng cách
sau. Trư c h t, tìm ph n t ñ u tiên ai trong dãy ñã cho k t ph i qua trái sao cho ai ≠ n
− k + i. Sau ñó thay ai b ng ai + 1 và aj b ng ai + j − i + 1 v i j = i + 1, i + 2, ..., k.
Thí d 12: Tìm t h p ch p 4 t t p {1, 2, 3, 4, 5, 6} ñi li n sau t h p {1, 2, 5, 6}.
Ta th y t ph i qua trái a2 = 2 là s h ng ñ u tiên c a t h p ñã cho th a mãn
ñi u ki n ai ≠ 6 − 4 + i. ð nh n ñư c t h p ti p sau ta tăng ai lên m t ñơn v , t c a2 =
3, sau ñó ñ t a3 = 3 + 1 = 4 và a4 = 3 + 2 = 5. V y t h p li n sau t h p ñã cho là
{1,3,4,5}. Th t c này ñư c cho dư i d ng thu t toán như sau.
procedure T h p li n sau ({a1, a2, ..., ak}: t p con th c s c a t p {1, 2, ..., n} không
b ng {n − k + 1, ..., n} v i a1 < a2 < ... < ak)
i := k
while ai = n − k + i
i := i − 1
ai := ai + 1
for j := i + 1 to k
aj := ai + j − i


31
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

2.5. H TH C TRUY H I.
2.5.1. Khái ni m m ñ u và mô hình hóa b ng h th c truy h i:
ðôi khi ta r t khó ñ nh nghĩa m t ñ i tư ng m t cách tư ng minh. Nhưng có th
d dàng ñ nh nghĩa ñ i tư ng này qua chính nó. K thu t này ñư c g i là ñ quy. ð nh
nghĩa ñ quy c a m t dãy s ñ nh rõ giá tr c a m t hay nhi u hơn các s h ng ñ u tiên
và quy t c xác ñ nh các s h ng ti p theo t các s h ng ñi trư c. ð nh nghĩa ñ quy có
th dùng ñ gi i các bài toán ñ m. Khi ñó quy t c tìm các s h ng t các s h ng ñi
trư c ñư c g i là các h th c truy h i.
ð nh nghĩa 1: H th c truy h i (hay công th c truy h i) ñ i v i dãy s {an} là công
th c bi u di n an qua m t hay nhi u s h ng ñi trư c c a dãy. Dãy s ñư c g i là l i
gi i hay nghi m c a h th c truy h i n u các s h ng c a nó th a mãn h th c truy h i
này.
Thí d 13 (Lãi kép): 1) Gi s m t ngư i g i 10.000 ñô la vào tài kho n c a mình t i
m t ngân hàng v i lãi su t kép 11% m i năm. Sau 30 năm anh ta có bao nhiêu ti n
trong tài kho n c a mình?
G i Pn là t ng s ti n có trong tài kho n sau n năm. Vì s ti n có trong tài kho n
sau n năm b ng s có sau n − 1 năm c ng lãi su t c a năm th n, nên ta th y dãy {Pn}
tho mãn h th c truy h i sau:
Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1
v i ñi u ki n ñ u P0 = 10.000 ñô la. T ñó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho
ta P30 = 228922,97 ñô la.
2) Tìm h th c truy h i và cho ñi u ki n ñ u ñ tính s các xâu nh phân ñ dài n
và không có hai s 0 liên ti p. Có bao nhiêu xâu nh phân như th có ñ dài b ng 5?
G i an là s các xâu nh phân ñ dài n và không có hai s 0 liên ti p. ð nh n
ñư c h th c truy h i cho {an}, ta th y r ng theo quy t c c ng, s các xâu nh phân ñ
dài n và không có hai s 0 liên ti p b ng s các xâu nh phân như th k t thúc b ng s 1
c ng v i s các xâu như th k t thúc b ng s 0. Gi s n ≥ 3.
Các xâu nh phân ñ dài n, không có hai s 0 liên ti p k t thúc b ng s 1 chính là
xâu nh phân như th , ñ dài n − 1 và thêm s 1 vào cu i c a chúng. V y chúng có t t c
là an-1. Các xâu nh phân ñ dài n, không có hai s 0 liên ti p và k t thúc b ng s 0, c n
ph i có bit th n − 1 b ng 1, n u không thì chúng có hai s 0 hai bit cu i cùng. Trong
trư ng h p này chúng có t t c là an-2. Cu i cùng ta có ñư c:
an = an-1 + an-2 v i n ≥ 3.
ði u ki n ñ u là a1 = 2 và a2 = 3. Khi ñó a5 = a4 + a3 = a3 + a2 + a3 = 2(a2 + a1) + a2 = 13.
2.5.2. Gi i các h th c truy h i.
ð nh nghĩa 2: M t h th c truy h i tuy n tính thu n nh t b c k v i h s h ng s là h
th c truy h i có d ng:

32
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

an = c1an-1 + c2an-2 + ... + ckan-k ,
trong ñó c1, c2, ..., ck là các s th c và ck ≠ 0.
Theo nguyên lý c a quy n p toán h c thì dãy s th a mãn h th c truy h i nêu
trong ñ nh nghĩa ñư c xác ñ nh duy nh t b ng h th c truy h i này và k ñi u ki n ñ u:
a0 = C0, a1 = C1, ..., ak-1 = Ck-1.
Phương pháp cơ b n ñ gi i h th c truy h i tuy n tính thu n nh t là tìm nghi m
dư i d ng an = rn, trong ñó r là h ng s . Chú ý r ng an = rn là nghi m c a h th c truy
h i an = c1an-1 + c2an-2 + ... + ckan-k n u và ch n u
- - - - -
rn = c1rn 1 + c2rn 2 + ... + ckrn k hay rk − c1rk 1 − c2rk 2 − ... − ck-1r – ck = 0.
Phương trình này ñư c g i là phương trình ñ c trưng c a h th c truy h i, nghi m c a
nó g i là nghi m ñ c trưng c a h th c truy h i.
M nh ñ : Cho c1, c2, ..., ck là các s th c. Gi s r ng phương trình ñ c trưng
- -
rk − c1rk 1 − c2rk 2 − ... − ck-1r – ck = 0
có k nghi m phân bi t r1, r2, ..., rk. Khi ñó dãy {an} là nghi m c a h th c truy h i an =
c1an-1 + c2an-2 + ... + ckan-k n u và ch n u an = α1r1n + α2r2n + ... + αkrkn, v i n = 1, 2, ...
trong ñó α1, α2, ..., αk là các h ng s .
Thí d 14: 1) Tìm công th c hi n c a các s Fibonacci.
Dãy các s Fibonacci th a mãn h th c fn = fn-1 + fn-2 và các ñi u ki n ñ u f0 = 0
1+ 5 1− 5
và f1 = 1. Các nghi m ñ c trưng là r1 = và r2 = . Do ñó các s Fibonacci
2 2
1+ 5 n 1− 5 n
ñư c cho b i công th c fn = α1( ) + α2( ) . Các ñi u ki n ban ñ u f0 = 0 =
2 2
1+ 5 1− 5 1
α1 + α2 và f1 = 1 = α1( ) + α2( ). T hai phương trình này cho ta α1 = ,
2 2 5
1
α2 = - . Do ñó các s Fibonacci ñư c cho b i công th c hi n sau:
5
1 1+ 5 n 1 1− 5 n
fn = ( ) - ( ).
5 2 5 2
2) Hãy tìm nghi m c a h th c truy h i an = 6an-1 - 11an-2 + 6an-3 v i ñi u ki n
ban ñ u a0 = 2, a1 = 5 và a2 = 15.
ða th c ñ c trưng c a h th c truy h i này là r3 - 6r2 + 11r - 6. Các nghi m ñ c
trưng là r = 1, r = 2, r = 3. Do v y nghi m c a h th c truy h i có d ng
an = α11n + α22n + α33n.
Các ñi u ki n ban ñ u a0 = 2 = α1 + α2 + α3
a1 = 5 = α1 + α22 + α33
a2 = 15 = α1 + α24 + α39.
Gi i h các phương trình này ta nh n ñư c α1= 1, α2 = −1, α3 = 2. Vì th , nghi m duy
nh t c a h th c truy h i này và các ñi u ki n ban ñ u ñã cho là dãy {an} v i

33
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

an = 1 − 2n + 2.3n.
2.6. QUAN H CHIA ð TR .
2.6.1. M ñ u:
Nhi u thu t toán ñ quy chia bài toán v i các thông tin vào ñã cho thành m t hay
nhi u bài toán nh hơn. S phân chia này ñư c áp d ng liên ti p cho t i khi có th tìm
ñư c l i gi i c a bài toán nh m t cách d dàng. Ch ng h n, ta ti n hành vi c tìm ki m
nh phân b ng cách rút g n vi c tìm ki m m t ph n t trong m t danh sách t i vi c tìm
ph n t ñó trong m t danh sách có ñ dài gi m ñi m t n a. Ta rút g n liên ti p như v y
cho t i khi còn l i m t ph n t . M t ví d khác là th t c nhân các s nguyên. Th t c
này rút g n bài toán nhân hai s nguyên t i ba phép nhân hai s nguyên v i s bit gi m
ñi m t n a. Phép rút g n này ñư c dùng liên ti p cho t i khi nh n ñư c các s nguyên
có m t bit. Các th t c này g i là các thu t toán chia ñ tr .
2.6.2. H th c chia ñ tr :
Gi s r ng m t thu t toán phân chia m t bài toán c n thành a bài toán nh ,
n
trong ñó m i bài toán nh có c (ñ ñơn gi n gi s r ng n chia h t cho b; trong th c
b
n n
t các bài toán nh thư ng có c [ ] ho c ] [). Gi s r ng t ng các phép toán thêm
b b
vào khi th c hi n phân chia bài toán c n thành các bài toán có c nh hơn là g(n). Khi
ñó, n u f(n) là s các phép toán c n thi t ñ gi i bài toán ñã cho thì f th a mãn h th c
truy h i sau:
n
f(n) = af( ) + g(n)
b
H th c này có tên là h th c truy h i chia ñ tr .
Thí d 15: 1) Thu t toán tìm ki m nh phân ñưa bài toán tìm ki m c n v bài toán tìm ki m
ph n t này trong dãy tìm ki m c n/2, khi n ch n. Khi th c hi n vi c rút g n c n hai phép so
sánh. Vì th , n u f(n) là s phép so sánh c n ph i làm khi tìm ki m m t ph n t trong danh sách
tìm ki m c n ta có f(n) = f(n/2) + 2, n u n là s ch n.
2) Có các thu t toán hi u qu hơn thu t toán thông thư ng ñ nhân hai s nguyên.
ñây ta s có m t trong các thu t toán như v y. ðó là thu t toán phân nhanh, có dùng
k thu t chia ñ tr . Trư c tiên ta phân chia m i m t trong hai s nguyên 2n bit thành
hai kh i m i kh i n bit. Sau ñó phép nhân hai s nguyên 2n bit ban ñ u ñư c thu v ba
phép nhân các s nguyên n bit c ng v i các phép d ch chuy n và các phép c ng.
Gi s a và b là các s nguyên có các bi u di n nh phân ñ dài 2n là
a = (a2n-1 a2n-2 ... a1 a0)2 và b = (b2n-1 b2n-2 ... b1 b0)2.
Gi s a = 2 A1 + A0 , b = 2nB1 + B0 , trong ñó
n

A1 = (a2n-1 a2n-2 ... an+1 an)2 , A0 = (an-1 ... a1 a0)2
B1 = (b2n-1 b2n-2 ... bn+1 bn)2 , B0 = (bn-1 ... b1 b0)2.
Thu t toán nhân nhanh các s nguyên d a trên ñ ng th c:
34
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

ab = (22n + 2n)A1B1 + 2n(A1 - A0)(B0 - B1) + (2n + 1)A0B0.
ð ng th c này ch ra r ng phép nhân hai s nguyên 2n bit có th th c hi n b ng cách
dùng ba phép nhân các s nguyên n bit và các phép c ng, tr và phép d ch chuy n.
ði u ñó có nghĩa là n u f(n) là t ng các phép toán nh phân c n thi t ñ nhân hai s
nguyên n bit thì
f(2n) = 3f(n) + Cn.
Ba phép nhân các s nguyên n bit c n 3f(n) phép toán nh phân. M i m t trong các phép
c ng, tr hay d ch chuy n dùng m t h ng s nhân v i n l n các phép toán nh phân và
Cn là t ng các phép toán nh phân ñư c dùng khi làm các phép toán này.
n
M nh ñ 1: Gi s f là m t hàm tăng tho mãn h th c truy h i f(n) = af( ) + c v i
b
m i n chia h t cho b, a ≥ 1, b là s nguyên l n hơn 1, còn c là s th c dương. Khi ñó

O( n logb a ), a > 1
f(n) =  .
O(log n), a = 1

n
M nh ñ 2: Gi s f là hàm tăng tho mãn h th c truy h i f(n) = af( ) + cnd v i m i
b
n = bk, trong ñó k là s nguyên dương, a ≥ 1, b là s nguyên l n hơn 1, còn c và d là các
s th c dương. Khi ñó
O(n logb a ), a > b d


f(n) = O(n d log n), a = b d .
 d d
O(n ) , a < b

Thí d 16: Hãy ư c lư ng s phép toán nh phân c n dùng khi nhân hai s nguyên n bit
b ng thu t toán nhân nhanh.
Thí d 15.2 ñã ch ra r ng f(n) = 3f(n/2) + Cn, khi n ch n. Vì th , t M nh ñ 2 ta
suy ra f(n) = O( n log 2 3 ). Chú ý là log23 ≈ 1,6. Vì thu t toán nhân thông thư ng dùng
O(n2) phép toán nh phân, thu t toán nhân nhanh s th c s t t hơn thu t toán nhân
thông thư ng khi các s nguyên là ñ l n.

BÀI T P CHƯƠNG II:

1. Trong t ng s 2504 sinh viên c a m t khoa công ngh thông tin, có 1876 theo h c
môn ngôn ng l p trình Pascal, 999 h c môn ngôn ng Fortran và 345 h c ngôn ng C.
Ngoài ra còn bi t 876 sinh viên h c c Pascal và Fortran, 232 h c c Fortran và C, 290
h c c Pascal và C. N u 189 sinh viên h c c 3 môn Pascal, Fortran và C thì trong
trư ng h p ñó có bao nhiêu sinh viên không h c môn nào trong 3 môn ngôn ng l p
trình k trên.


35
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

2. M t cu c h p g m 12 ngư i tham d ñ bàn v 3 v n ñ . Có 8 ngư i phát bi u v
v n ñ I, 5 ngư i phát bi u v v n ñ II và 7 ngư i phát bi u v v n ñ III. Ngoài ra, có
ñúng 1 ngư i không phát bi u v n ñ nào. H i nhi u l m là có bao nhiêu ngư i phát
bi u c 3 v n ñ .
3. Ch ra r ng có ít nh t 4 ngư i trong s 25 tri u ngư i có cùng tên h vi t t t b ng 3
ch cái sinh cùng ngày trong năm (không nh t thi t trong cùng m t năm).
4. M t tay ñô v t tham gia thi ñ u giành ch c vô ñ ch trong 75 gi . M i gi anh ta có ít
nh t m t tr n ñ u, nhưng toàn b anh ta có không quá 125 tr n. Ch ng t r ng có nh ng
gi liên ti p anh ta ñã ñ u ñúng 24 tr n.
5. Cho n là s nguyên dương b t kỳ. Ch ng minh r ng luôn l y ra ñư c t n s ñã cho
m t s s h ng thích h p sao cho t ng c a chúng chia h t cho n.
6. Trong m t cu c l y ý ki n v 7 v n ñ , ngư i ñư c h i ghi vào m t phi u tr l i s n
b ng cách ñ nguyên ho c ph ñ nh các câu tr l i tương ng v i 7 v n ñ ñã nêu.
Ch ng minh r ng v i 1153 ngư i ñư c h i luôn tìm ñư c 10 ngư i tr l i gi ng
h t nhau.
7. Có 17 nhà bác h c vi t thư cho nhau trao ñ i 3 v n ñ . Ch ng minh r ng luôn tìm
ñư c 3 ngư i cùng trao ñ i m t v n ñ .
8. Trong kỳ thi k t thúc h c ph n toán h c r i r c có 10 câu h i. Có bao nhiêu cách gán
ñi m cho các câu h i n u t ng s ñi m b ng 100 và m i câu ít nh t ñư c 5 ñi m.
9. Phương trình x1 + x2 + x3 + x4 + x5 = 21 có bao nhiêu nghi m nguyên không âm?
10. Có bao nhiêu xâu khác nhau có th l p ñư c t các ch cái trong t MISSISSIPI,
yêu c u ph i dùng t t c các ch ?
11. M t giáo sư c t b sưu t p g m 40 s báo toán h c vào 4 chi c ngăn t , m i ngăn
ñ ng 10 s . Có bao nhiêu cách có th c t các t báo vào các ngăn n u:
1) M i ngăn ñư c ñánh s sao cho có th phân bi t ñư c;
2) Các ngăn là gi ng h t nhau?
12. Tìm h th c truy h i cho s m t th t Dn.
13. Tìm h th c truy h i cho s các xâu nh phân ch a xâu 01.
14. Tìm h th c truy h i cho s cách ñi lên n b c thang n u m t ngư i có th bư c m t,
hai ho c ba b c m t l n.
15. 1) Tìm h th c truy h i mà Rn tho mãn, trong ñó Rn là s mi n c a m t ph ng b
phân chia b i n ñư ng th ng n u không có hai ñư ng nào song song và không có 3
ñư ng nào cùng ñi qua m t ñi m.
b) Tính Rn b ng phương pháp l p.
16. Tìm nghi m c a h th c truy h i an = 2an-1 + 5an-2 - 6an-3 v i a0 = 7, a1 = -4, a2 = 8.




36
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản