Tải bản đầy đủ (.pdf) (51 trang)

bài 2 đệ quy và gt đệ quy

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (247.41 KB, 51 trang )

1
Bài 2:  quy và GT  quy
2.1.  quy và gii thut  quy
2.2. Thit k gii thut  quy
2.3. Mt s dng bài toán in hình
2.4. Bài tp
2
2.1.  quy và
gii thut  quy
3
 quy
 Khái nim: Mt i tng là  quy nu nó c nh
ngha qua
chính nó hoc mt i tng khác cùng dng
vi chính nó bng quy np.
 Phân loi: Có 2 loi i tng  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 trc tip 2)  quy gián tip
A
B C
A
A
A
C
E
B
D
5
Mô t  quy
 im mnh ca  quy: Cho phép mô t 1 tp ln các
i tng bng 1 s ít các mnh  hoc mô t 1 GT
phc tp bng 1 s ít các thao tác (1 chng trình con
 quy).
 Mô t  quy: gm 2 phn

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
Mt s mô t  quy thng gp
1. Tp 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 tha ca 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 ln nht (USCLN) ca 2 s t nhiên A
và B không ng thi bng 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 hi kim tra nhn thc
 Câu hi 1:
Gii thích mô t  quy USCLN(A, B). Minh ho quá
trình thc hin vi:
1.
A = 126 và B = 72.
2.
A = 72 và B = 126.

áp án:
 Gii thích:

%&∋( ) ∗+,%−.∋

%&

( ) / 01/ 01
234564738 )93:
∗+,%−.∋∗+,%−.

8
Câu hi kim tra nhn thc

Minh ho

1:
∗+,%−;<=><. ∋∗+,%−><?≅. ΑΑ∋>< ≠ (
∋∗+,%−?≅;Β. ΑΑ ∋?≅≠ (
∋∗+,%−;Β(. ΑΑ ∋;Β≠ (
∋;Β ΑΑ ∋(

Minh ho

2:
∗+,%−><;<=. ∋∗+,%−;<=><. ΑΑ ∋;<=≠ (
∋∗+,%−><?≅. ΑΑ ∋><≠ (
∋∗+,%−?≅;Β. ΑΑ ∋?≅≠ (
∋∗+,%−;Β(. ΑΑ ∋;Β≠ (
∋;Β ΑΑ ∋(
9
Mt s bài toán  quy in hình
 Bài toán tìm nghim gn úng: ca phng trình f(x)=0
trên on
[a, b] vi sai s c, bit f(x) liên tc trên [a, b].
 Bài toán “Tháp Hà Ni”: Chuyn mt chng a N a
vi kích thc khác nhau t ct
A sang ct 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 Hu”: Xp
N quân hu trên bàn c
hình vuông kích thc
N x N sao cho trên mi ng
chéo, ng ngang, ng dc ch có úng 1 quân Hu.
10
c im hàm  quy
 Khái nim: mt chng trình con mô t gii thut 
quy
gi là chng 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 im: mt hàm  quy có 3 c im 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∀383Ε
0
Φ 6Γ/03&Η
11
c im hàm  quy
 Phân loi: Có 2 loi hàm  quy, tng ng vi 2 loi
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).

∀3833Ι∗+,%ϑ303ΚΛ  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 tip: Gi thit Collatz
 Collatz a ra gi thuyt rng:
“Vi mt s nguyên dng X bt k, nu X chn thì ta
gán X = X / 2; nu X l thì ta gán X = X * 3 + 1 thì sau
mt s hu hn bc, ta s có X = 1”.
 Vi X = 10, các bc tin 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 tip: Gi thit Collatz
 Bài toán (da trên khng nh gi thuyt 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.
 Gii thut:

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 tip: Gi thit 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 tip: Gi thit Collatz
//In ra cách biu 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. Thit k gii thut  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 im  quy ca hàm N!
 c im:
i chiu vi c im 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 lp tính N!
 Khái nim:

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 im:
 
u

i

m:

Φ3:Π: /6393:3Θ4Ε
88Ρ3∀Σ668!∀ 336803&0Τ

Χ0Υ ∀0Τ ∆Γ: /634ς 8
4Φ3Ρ3∆

Nh

c


i

m:

3:)Ν456ΦΩΠ3ΘΝ: /

3:4Ξ6)Φ676
20
GT lp 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!
 Gii thut lp:
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á  phc tp gii thut
 Phân tích ánh giá  phc tp ca gii thut lp 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 nim: Dãy s Fibonacci b∀t ngun t bài toán c#
v vic sinh sn ca các cp 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
 Din gii quá trình sinh sn ca 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 thc tính s Fibonacci F(N)
 Tìm công thc tính s cp 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

ã


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 im ca 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

×