Giáo trình Toán rời rạc - Chương 2: Bài toán đếm

 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: 
 33 
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 = r
n, trong đó r là hằng số. Chú ý rằng an = r
n
 là nghiệm của hệ thức truy 
hồi an = c1an-1 + c2an-2 + ... + ckan-k nếu và chỉ nếu 
r
n
 = c1r
n-1
 + c2r
n-2
 + ... + ckr
n-k
 hay r
k
  c1r
k-1
  c2r
k-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 
r
k
  c1r
k-1
  c2r
k-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 = 1r1
n
 + 2r2
n
 + ... + krk
n, 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 
và f1 = 1. Các nghiệm đặc trưng là r1 = 
1 5
2

 và r2 = 
1 5
2

. Do đó các số Fibonacci 
được cho bởi công thức fn = 1(
1 5
2

)
n
 + 2(
1 5
2

)
n. Các điều kiện ban đầu f0 = 0 = 
1 + 2 và f1 = 1 = 1(
1 5
2

) + 2(
1 5
2

). Từ hai phương trình này cho ta 1 = 
1
5
, 
2 = -
1
5
. Do đó các số Fibonacci được cho bởi công thức hiển sau: 
fn = 
1
5
(
1 5
2

)
n
 - 
1
5
(
1 5
2

)
n
. 
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 = 11
n
 + 22
n
 + 33
n
. 
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 
 34 
an = 1  2
n
 + 2.3
n
. 
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ỏ, 
trong đó mỗi bài toán nhỏ có cỡ 
n
b
 (để đơn giản giả sử rằng n chia hết cho b; trong thực 
tế các bài toán nhỏ thường có cỡ [
n
b
] hoặc ]
n
b
[). Giả sử rằng tổng các phép toán thêm 
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: 
f(n) = af(
n
b
) + g(n) 
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 = 2nA1 + A0 , b = 2
n
B1 + B0 , trong đó 
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: 
 35 
ab = (2
2n
 + 2
n
)A1B1 + 2
n
(A1 - A0)(B0 - B1) + (2
n
 + 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. 
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(
n
b
) + c với 
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 đó 
f(n) = 






1,)(log
1,)(
log
anO
anO
ab
. 
Mệnh đề 2: Giả sử f là hàm tăng thoả mãn hệ thức truy hồi f(n) = af(
n
b
) + cn
d
 với mọi 
n = b
k, 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 đó 
f(n) = 









dd
dd
da
banO
bannO
banO b
,)(
,)log(
,)(
log
. 
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( 3log2n ). Chú ý là log23  1,6. Vì thuật toán nhân thông thường dùng 
O(n
2) 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. 
 36 
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.