25/08/2014
GVC, ThS.Võ Minh Đức
1
TOÁN RỜI RẠC
CH1: Hãy cho một ví dụ về định nghĩa đệ quy?
1. Định nghĩa giai thừa của n:
n! = n * (n-1)!
2. Lũy thừa nguyên của một số:
a
n
= a * a
n-1
CH2: Có thể ĐN hai khái niệm trên không dùng đệ quy được không?
25/08/2014
GVC, ThS.Võ Minh Đức
2
TOÁN RỜI RẠC
CH1: Đọc giá trị của dãy số gồm các giai thừa của một số, bắt đầu từ 0:
0, 1, 2, 6, 12, 20, ,n!
a
1
, a
2
, a
3
, a
4
…a
n
25/08/2014
GVC, ThS.Võ Minh Đức

GIẢI
Gọi P
n
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 {P
n
} thoả mãn hệ thức truy hồi sau:
P
n
= P
n-1
+ 0,11P
n-1
= (1,11)P
n-1
với điều kiện đầu P
0
= 10.000 đô la. Từ đó suy ra P
n
= (1,11)
n
.10.000.
Thay n = 30 cho ta P
30
= 228922,97 đô la.
TOÁN RỜI RẠC
V.
Hệ thức
truy hồi

n
= b
n
+ c
n
(1)
TOÁN RỜI RẠC
V.
Hệ thức
truy hồi
25/08/2014
GVC, ThS.Võ Minh Đức
8
GIẢI
Giả sử n ≥ 3.
* b
n
chính là số xâu np như thế, độ dài n − 1 và thêm số 1 vào cuối của
chúng. Hỏi có tất cả là bao nhiêu xâu?
* c
n
là số các xâu np 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. Hỏi có tất cả là bao nhiêu xâu như thế ?
có tất cả là a
n-1
xâu.
Vậy b
n
= ?
có tất cả là a

= 3
Khi đó a
5
= a
4
+ a
3
= a
3
+ a
2
+ a
3

= 2(a
2
+ a
1
) + a
2
= 13.
TOÁN RỜI RẠC
V.
Hệ thức
truy hồi
25/08/2014
GVC, ThS.Võ Minh Đức
10
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

GVC, ThS.Võ Minh Đức
11
2. Giải
các hệ
thức truy
hồi.
Là tuyến tính vì vế phải của nó là tổng các tích của các số hạng
trước nhân với một hệ số
Là thuần nhất vì các số hạng đều là a
i
và hệ số đều là hằng số.
Có bậc k vì a
n
được biểu diễn qua k số hạng đứng trước nó.
Hệ thức truy hồi
25/08/2014
GVC, ThS.Võ Minh Đức
12
P
n
= (1,11)P
n-1
là tuyến tính bậc nhất
a
n
= a
n-1
+ a
n-2
là tuyến tính thuần nhất bậc 2.

n
, (r là hằng số) là nghiệm của hệ thức truy hồi
a
n
= c
1
a
n-1
+ c
2
a
n-2
+ + c
k
a
n-k

 r
n
= c
1
r
n-1
+ c
2
r
n-2
+ + c
k
r

k-1
- c
2
r
k-2
- C
k-1
r - c
k
= 0
được gọi là phương trình đặc trưng của hệ thức truy hồi a
n
= c
1
a
n-1

+ c
2
a
n-2
+ + c
k
a
n-k
, nghiệm của nó gọi là nghiệm đặc trưng của
hệ thức truy hồi.
2. Giải
các hệ
thức truy

, , r
k
.
Khi đó dãy {a
n
} là nghiệm của hệ thức truy hồi a
n
= c
1
a
n-1
+ c
2
a
n-2
+ +
c
k
a
n-k

khi và chỉ khi
a
n
= α
1
r
1
n
+ α

n-1
+ a
n-2
(với đk đầu a
0
= 0, a
1
= 1).
k = 2, c
1
= 1, c
2
= 1
Phương trình đặc trưng là: r
2
– r – 1 = 0
Có các nghiệm là :
2
51
2
51
21
−
=
+
= rvàr
Do đó các số Fibonacci được cho bởi công thức:
nn
n
a )

0
)1()
2
51
()
2
51
(
21
nn
n
a
−
+
+
=
αα
5
5
,
5
5
21
−
==
αα
Từ 2 phương trình trên, ta được:
)
2
51

(
5
5 −
−
+
=
Do đó các số Fibonacci được cho bởi công thức hiển sau:
2. Giải
các hệ
thức truy
hồi.
25/08/2014
GVC, ThS.Võ Minh Đức
19
Hãy tìm nghiệm của hệ thức truy hồi a
n
= 6a
n-1
- 11a
n-2
+ 6a
n-3
với điều kiện
ban đầu a
0
= 2, a
1
= 5 và a
2
= 15.

hệ chia
để
trị
25/08/2014
GVC, ThS.Võ Minh Đức
22
Procedure
Chia_tri(n);
Begin
If n< n
0
then giai truc tiep bai toan
Else
Begin
Chia bài toán thành a bài toán con có kích thước n/b
For (mỗi bài toán trong a bài toán con) do
chia_tri(n/b);
Tổng hợp lời giải từ a bài toán con để có lời giải bài toán.
End;
End;
VI. Quan
hệ chia
để
trị
25/08/2014
GVC, ThS.Võ Minh Đức
23
BÀI TOÁN tìm kiếm nhị phân. -> thuật toán
BÀI TOÁN nhân hai số nguyên. -> thuật toán (về nhà đọc sách tr.84)
Các thuật toán này gọi là các thuật toán chia để trị.

c là số thực dương. Khi đó:
Định lý
VI. Quan
hệ chia
để
trị



=
>
=
1)(
1)(log
log
)(
anêunO
anêuO
a
b
n
b
nf