1
Bài 2: quy và GT quy
2.1. quy và gii thut quy
2.2. Thit k gii thut quy
2.3. Mt s dng bài toán in hình
2.4. Bài tp
2
2.1. quy và
gii thut quy
3
quy
Khái nim: Mt i tng là quy nu nó c nh
ngha qua
chính nó hoc mt i tng khác cùng dng
vi chính nó bng quy np.
Phân loi: Có 2 loi i tng quy.
quy tr
c ti
p:
i t
ng A
c mô t
tr
c ti
p qua
chính
i t
ng A.
quy gián ti
p:
i t
ng A
c mô t
gián ti
p qua
i t
ng A.
!∀ #
∃!∀
4
Minh ho quy
1) quy trc tip 2) quy gián tip
A
B C
A
A
A
C
E
B
D
5
Mô t quy
im mnh ca quy: Cho phép mô t 1 tp ln các
i tng bng 1 s ít các mnh hoc mô t 1 GT
phc tp bng 1 s ít các thao tác (1 chng trình con
quy).
Mô t quy: gm 2 phn
Ph
n neo: Mô t
các tr
ng h
p suy bi
n c
a
i t
ng
(gi
i thu
t) qua 1 c
u trúc (thao tác) c
th
xác
nh.
Ph
n
quy: Mô t
i t
ng (gi
i thu
t) trong tr
ng
h
p ph
bi
n thông qua chính
i t
ng (gi
i thu
t)
ó 1
cách tr
c ti
p (
quy tr
c ti
p) ho
c gián ti
p (
quy
gián ti
p).
Chú ý: N
u không có ph
n neo thì
i t
ng
c mô t
có c
u trúc l
n vô h
n (gi
i thu
t l
p không d
ng)!
6
Mt s mô t quy thng gp
1. Tp s t nhiên N:
0 là s
t
nhiên. {ph
n neo}
X là s
t
nhiên n
u X – 1 là s
t
nhiên. {ph
n
quy}
2. Giai tha ca 1 s t nhiên N:
0! = 1 {ph
n neo}
N
u N > 0 thì N! = N * (N – 1)! {ph
n
quy}
3. c s chung ln nht (USCLN) ca 2 s t nhiên A
và B không ng thi bng 0 (A
2
+ B
2
> 0)
USCLN(A, 0) = A {ph
n neo}
USCLN(A, B) = USCLN(B, A mod B) {ph
n
quy}
7
Câu hi kim tra nhn thc
Câu hi 1:
Gii thích mô t quy USCLN(A, B). Minh ho quá
trình thc hin vi:
1.
A = 126 và B = 72.
2.
A = 72 và B = 126.
áp án:
Gii thích:
%&∋( ) ∗+,%−.∋
%&
≠
( ) / 01/ 01
234564738 )93:
∗+,%−.∋∗+,%−.
8
Câu hi kim tra nhn thc
Minh ho
1:
∗+,%−;<=><. ∋∗+,%−><?≅. ΑΑ∋>< ≠ (
∋∗+,%−?≅;Β. ΑΑ ∋?≅≠ (
∋∗+,%−;Β(. ΑΑ ∋;Β≠ (
∋;Β ΑΑ ∋(
Minh ho
2:
∗+,%−><;<=. ∋∗+,%−;<=><. ΑΑ ∋;<=≠ (
∋∗+,%−><?≅. ΑΑ ∋><≠ (
∋∗+,%−?≅;Β. ΑΑ ∋?≅≠ (
∋∗+,%−;Β(. ΑΑ ∋;Β≠ (
∋;Β ΑΑ ∋(
9
Mt s bài toán quy in hình
Bài toán tìm nghim gn úng: ca phng trình f(x)=0
trên on
[a, b] vi sai s c, bit f(x) liên tc trên [a, b].
Bài toán “Tháp Hà Ni”: Chuyn mt chng a N a
vi kích thc khác nhau t ct
A sang ct C theo cách:
M
i l
n ch
chuy
n 1
a .
Khi chuy
n có th
dùng c
t trung gian B.
Trong su
t quá trình chuy
n, các ch
ng
a
các c
t luôn
c x
p
úng (
a có kích th
c bé
t trên
a có kích
th
c l
n).
Bài toán “N quân Hu”: Xp
N quân hu trên bàn c
hình vuông kích thc
N x N sao cho trên mi ng
chéo, ng ngang, ng dc ch có úng 1 quân Hu.
10
c im hàm quy
Khái nim: mt chng trình con mô t gii thut
quy
gi là chng trình con quy, hay hàm quy.
Pascal (hàm, th
t
c), C/C++ (hàm có ki
u, hàm void).
c im: mt hàm quy có 3 c im sau
1.
Có l
i g
i
n chính nó: trong thân hàm
quy có ch
a
l
i g
i hàm t
i chính hàm
quy
ó.
2.
Kích th
c bài toán gi
m d
n: m
i l
n có l
i g
i hàm
quy thì kích th
c c
a bài toán
ã thu nh
h
n tr
c.
3.
Có tr
ng h
p suy bi
n: là tr
ng h
p
c bi
t mà khi
x
y ra thì bài toán s
c gi
i quy
t theo 1 cách khác
h
n và quá trình g
i hàm
quy c
!
ng k
t thúc.
Χ∆0∀383Ε
0
Φ 6Γ/03&Η
11
c im hàm quy
Phân loi: Có 2 loi hàm quy, tng ng vi 2 loi
mô t quy.
quy tr
c ti
p: trong thân hàm A có ch
a l
i g
i hàm
n chính A (th
ng g
p).
∀3833Ι∗+,%ϑ303ΚΛ 6Μ
quy gián ti
p: trong thân hàm A ch
a l
i g
i hàm
n
hàm
B, và trong thân hàm B l
i ch
a l
i g
i hàm
n A
(ít g
p).
Ν3 3&44Ο
12
quy gián tip: Gi thit Collatz
Collatz a ra gi thuyt rng:
“Vi mt s nguyên dng X bt k, nu X chn thì ta
gán X = X / 2; nu X l thì ta gán X = X * 3 + 1 thì sau
mt s hu hn bc, ta s có X = 1”.
Vi X = 10, các bc tin hành nh sau:
1.
X = 10 //X ch
∀
n
X = 10 / 2
2. X = 5 //X l
#
X = 5 * 3 + 1
3. X = 16 //X ch
∀
n
X = 16 / 2
4. X = 8 //X ch
∀
n
X = 8 / 2
5. X = 4 //X ch
∀
n
X = 4 / 2
6. X = 2 //X ch
∀
n
X = 2 / 2
7. X = 1 //K
t thúc
13
quy gián tip: Gi thit Collatz
Bài toán (da trên khng nh gi thuyt Collatz là
úng
):
“Cho tr
c s
1 cùng v
i hai phép toán * 2 và / 3, hãy s
d
ng m
t cách h
p lý hai phép toán
ó
bi
n s
1
thành m
t s
nguyên d
ng X cho tr
c.”
Ví d
: X = 10 ta có bi
u di
∃
n 1 * 2 * 2 * 2 * 2 / 3 * 2 = 10.
Gii thut:
bi
u di
∃
n X chia 2 tr
ng h
p:
N
u X ch
∀
n, thì tìm cách bi
u di
∃
n s
X / 2 và vi
t thêm
phép toán * 2 vào cu
i.
N
u X l
#
, thì tìm cách bi
u di
∃
n s
X * 3 + 1 và vi
t thêm
phép toán
/ 3 vào cu
i.
14
quy gián tip: Gi thit Collatz
void XuLySoLe(int X) //khi X l
{
XuLySo(X * 3 + 1);
printf(“ / 3”);
}
void XuLySoChan(int X) //khi X ch n
{
XuLySo(X / 2);
printf(“ * 2”);
}
15
quy gián tip: Gi thit Collatz
//In ra cách biu di!n s X
void XuLySo(int X)
{
if (X == 1)
printf(“%d”, X);
else
if (X % 2 == 1) XuLySoLe(X);
else
XuLySoChan(X);
}
16
2.2. Thit k gii thut quy
2.2.1. Hàm N!
2.2.2. Dãy s Fibonacci
2.2.3. Chú ý
17
2.2.1. Hàm N!
Mô t quy:
1 n
u N = 0 (ph
n neo)
N! =
N * (N - 1)! n
u N > 0 (ph
n
quy)
Hàm quy tính N! :
long GT(int N)
{
if (N == 0) return 1;
return N * GT(N – 1);
}
18
3 c im quy ca hàm N!
c im:
i chiu vi c im hàm quy:
Có l
i g
i
n chính nó: hàm
quy GT(N) g
i
n hàm
GT(N – 1).
return N * GT(N – 1)
Kích th
c bài toán gi
m d
n: sau m
i l
n g
i
quy,
giá tr
c
a d
%
li
u vào N gi
m
i 1.
Có tr
ng h
p suy bi
n: là tr
ng h
p N = 0. Khi
ó,
hàm
GT(N) tr
v
&
giá tr
1 và
quy k
t thúc.
if (N == 0) return 1;
19
GT lp tính N!
Khái nim:
Ph
ng pháp s
∋
d
ng vòng l
p
gi
i bài toán
quy
g
i là kh
∋
quy.
Gi
i thu
(
t mô t
ph
ng pháp kh
∋
quy g
i là gi
i
thu
(
t l
p.
c im:
u
i
m:
Φ3:Π: /6393:3Θ4Ε
88Ρ3∀Σ668!∀ 336803&0Τ
Χ0Υ ∀0Τ ∆Γ: /634ς 8
4Φ3Ρ3∆
Nh
c
i
m:
3:)Ν456ΦΩΠ3ΘΝ: /
3:4Ξ6)Φ676
20
GT lp tính N!
Mô t không quy: bài toán N! có th mô t theo
cách không quy nh sau:
N! = 1 * 2 * … * (N – 1) * N
N! là tích c
a N s
t
nhiên liên ti
p t
)
1
n N!
Gii thut lp:
long GT(int N)
{
long p = 1;
for(int i = 2; i <= N; i++)
p = p * i;
return p;
}
Gi
i thu
(
t l
p tính N! r
t
n gi
n!
21
ánh giá phc tp gii thut
Phân tích ánh giá phc tp ca gii thut lp tính N!:
B1: Xác
nh phép toán tích c
c:
p = p * i;
B2: S
l
n th
c hi
n c
a phép toán tích c
c là:
1 + 1 + … + 1 = N – 1 (l
n)
B3: K
t lu
(
n
ph
c t
p c
a gi
i thu
(
t:
T(N) = O(N)
22
2.2.2. Dãy s Fibonacci
Khái nim: Dãy s Fibonacci b∀t ngun t bài toán c#
v vic sinh sn ca các cp th∃.
Dãy s
Fibonacci là mô hình c
a r
t nhi
&
u hi
n t
ng t
nhiên và c
!
ng
c s
∋
d
ng nhi
&
u trong tin h
c.
Bài toán:
1.
Các con th
không bao gi
ch
t.
2. Hai tháng sau khi ra
i, 1 c
p th
m
i s
sinh ra 1 c
p
th
con g
m (1
c, 1 cái).
3. Khi
ã sinh con r
i thì c
m
i tháng ti
p theo chúng l
i
sinh ra
c 1 c
p th
con m
i.
Yêu c
u: T
)
1 c
p th
m
i ra
i thì
n tháng th
N s
có bao nhiêu c
p th
?
23
Dãy s Fibonacci
Din gii quá trình sinh sn ca th:
Tháng th
1: 1 c
p (c
p ban
u)
Tháng th
2: 1 c
p (c
p ban
u v
∗
n ch
a sinh)
Tháng th
3: 2 c
p (
ã có thêm 1 c
p con)
Tháng th
4: 3 c
p (c
p
u v
∗
n sinh thêm)
Tháng th
5: 5 c
p (c
p con b
+
t
u sinh)
Tháng th
6: 8 c
p (c
p con v
∗
n sinh ti
p)
…
Tháng th
N: ? c
p
Dãy s Fibonacci
1 1 2 3 5 8 … ?
24
Công thc tính s Fibonacci F(N)
Tìm công thc tính s cp th tháng th N: F(N)
N
u m
i c
p th
tháng th
(N - 1)
&
u sinh con thì:
F(N) = 2 * F(N – 1)
Do 2 tháng sau khi
c sinh ra, th
m
i sinh con, nên
trong các c
p th
tháng th
(N–1) ch
có nh
%
ng c
p
ã
có
tháng th
(N – 2) m
i sinh con
tháng th
N.
Do
ó s
c
p th
tháng th
N s
là:
F(N) = F(N – 2) + F(N – 1)
Mô t quy: tính F(N).
1 n
u N ≤ 2 //ph
n neo
F(N) =
F(N – 2) + F(N – 1) n
u N > 2 //ph
n
quy
25
GT quy tính F(N)
Hàm quy tính F(N):
long F(long N)
{
if (N <= 2) return 1;
return F(N – 2) + F(N – 1);
}
3 c im ca hàm quy:
1.
Có l
i g
i
n chính nó: return F(N – 2) + F(N – 1);
2. Kích th
c bài toán gi
m d
n: N gi
m thành N-1, N-2
3. Có tr
ng h
p suy bi
n: F(1) = 1 và F(2) = 1
Chú ý: có 1 chi ti
t h
i khác là tr
ng h
p suy bi
n
ng
v
i 2 giá tr
: F(1) = 1 và F(2) = 1