Bài giảng Toán rời rạc: Bài 3 - TS. Nguyễn Văn Hiệu

BÀI 3

KỶ THUẬT ĐẾM NÂNG CAO

Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn

1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

Nhắc lại!

Quy tắc nhân

Quy tắc cộng

HV, CH, TH

Chỉnh hợp lặp

Tổ hợp lặp

Nguyên lý bù trừ

Nội dung

3.1. Giới thiệu 3.2. Một số khái niệm 3.3. Mô hình hóa 3.4.Định nghĩa 3.5. Phương pháp

 Phương pháp thế  Phương trình đặc trưng

3.6. Bài tập

3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.1. Giới thiệu

 Khó định nghĩa đối tượng một cách tường minh  Có thể định nghĩa đối tượng qua chính nó  Kỷ thuật = đệ quy.

4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.1. Giới thiệu

• Ví dụ 3.1

• Ví dụ 3.2

10 000$

11 % tính gộp

Một ông già

30 năm

5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.2. Các khái niệm

Xác định một hay nhiều số hạng đầu tiên

a0 = 5

Đệ quy dãy số {a n}

an = 2 an-1

Xác định số hạng tiếp theo từ số hạng đi trước

Hệ thức truy hồi

6 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.2. Các khái niệm

Có thể

giải nếu

phiên bản đơn giản có thể được giải

Đưa ra vấn đề phức tạp

phiên bản đơn giản có thể được giải

an = 2an-1 an-1 = 2an-2, a1 = 2a0, a0=5

3.2. Các khái niệm

• Hệ thức truy hồi của {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.

• Nghiệm htth là dãy {bn} nếu các số hạng thỏa

mản hệ thức truy hồi.

• Giải htth là đi tìm công thức biểu diễn các số

hạng của dãy mà không thông qua các số hạng phía trước

8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.2. Các khái niệm

 an = 3n với mọi n nguyên không âm, có là lời giải của hệ

thức truy hồi an = 2 an-1 – an-2 với n = 2, 3, 4, …hay không?

 HD:

2an-1 – an-2 = ___________________

Giả sử an = 3n với mọi n, n ≥ 2;

 an = 5 với mọi n nguyên không âm, có là lời giải của hệ thức truy hồi an = 2an-1 – an-2 với n = 2, 3, 4, …hay không?

 HD

2an-1 – an-2 = ___________________

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. tổ hợp C(n,k), k ≤ n, 3.3.2. Bài toán tháp Hà nội, 3.3.3. Bài toán họ nhà thỏ

10 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

• C(n,k) = ?

• Xây dưng

11 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

 Cố định a trong n phần tử  Chia số cách chọn tập con k pt của tập n pt thành 2

lớp: – Lớp chứa a: C(n-1,k-1) – Lớp không chứa a: C(n-1,k)

 Nguyên lý cộng C(n,k) = C(n-1,k-1) + C(n-1,k) C(n,0) = C(n,n) =1

12 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

 int c(int m,int n)

{

if(m==0) return 1;

else if(m==n) return 1;

else return (c(m-1,n-1)+c(m,n-1));

}

 Nhược điểm đệ quy

13 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

3.3.2. Bài toán tháp Hà nội • Mô tả bài toán toán:

• Cho 3 cái cọc A, B, C và tập n đĩa có kích cỡ khác

nhau;

• Đĩa được bố trí theo thứ tự đường kính giảm dần từ

dưới lên trên

• Số đĩa ban đầu được đặt trên cọc A; • Mục đích: xếp được tất cả đĩa lên cọc C

14 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

3.3.2. Bài toán tháp Hà nội

• Quy tắc chơi

− Mỗi lần chuyển chỉ được chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ lên trên đĩa có đường kính lớn hơn.

− Mỗi đĩa có thể chuyển từ cọc này sang cọc khác; − Trong quá trình chuyển được phép sử dụng cọc B làm

trung gian.

• Bài toán đặt là: Tìm số lần dịch chuyển đĩa ít nhất cần

thực hiện để thực hiện xong nhiệm vụ đặt ra trong trò chơi tháp Hà Nôi

15 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

MINH HỌA

NGHIỆM

n đĩa

Gọi Hn : Số lần chuyển n đĩa

A

C

B Vị trí bắt đầu trên tháp Hà Nội

n-1 đĩa

Chuyển n-1 đĩa ở phần trên sang cọc B

A

B

C

Vị trí trung gian trên tháp Hà Nội

16 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

NGHIỆM

MINH HỌA

Chuyễn đĩa lớn nhất sang cọc C

1 đĩa

1 lần chuyển

B Vị trí trung gian trên Tháp Hà Nội

n đĩa

Chuyển phần trên n-1 đĩa sang cọc C

Hn-1 lần chuyển

Vị trí cuối cùng trên Tháp Hà Nội

17 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi

Chuyển n-1 đĩa phần trên sang cọc B

Chuyển đĩa lớn nhất sang cọc C

Chuyển n-1 đĩa phần trên sang cọc C

1 Hn-1

Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18

void THN(int n,char a, char b, char c){ if(n==1) Move(a,b); else { THN(n-1,a,c,b); Move(a,b); THN(n-1,c,b,a);} }

• Nhập n đưa ra số lần chuyển  Quan tâm số lần chuyển  Cách chuyển không quan trọng

void Move(char a, char b){ printf("\t%c ---> %c\n",a,b); }

3.3. Mô hình hóa hệ thức truy hồi

3.3.3. Bài toán họ nhà thỏ (population of rabbits)

Đôi tái tạo (từ hai tháng tuổi)

Đôi thỏ con (dưới hai tháng tuổi)

Tổ ng

Th án g

Đôi thỏ con

Đôi tái tạo

20 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.3. Mô hình hóa hệ thức truy hồi 3.3.3. Bài toán họ nhà thỏ f n = f n-1 + fn-2 , n≥ 3

Số đôi thỏ sau n-1 tháng

Số đôi thỏ trên đảo sau n tháng

số đôi thỏ mới sinh

số đôi thỏ sau n-2 tháng

Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21

3.4. Định nghĩa

• Hệ thức truy hồi tuyến tính thuần nhất bậc k hệ số

hằng có dạng:

an = c1 an-1 + c2 an-2 +…+ ck an-k

c1, c2,…,ck - hằng số, ck ≠ 0 .

• Hệ thức truy hồi bậc k với k giá đầu:

a0=I0, a1,= I1 ,…,ak-1 = I k-1

sẽ xác định duy nhất một dãy {an}

22 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.4. Định nghĩa

• Hệ thức truy hồi tuyến tính thuần nhất có hệ số hằng

Pn = (1.11) Pn-1

bậc một

1. Thường xuyên tồn tại trong các mô hình hóa các bài toán

fn = fn-1 + fn-2

bậc hai

Có thể giải một cách có hệ thống

bậc năm

an = an-5

Không thuần nhất

• Hệ thưc truy hồi không tuyến tính, không thuần nhất, không hệ số hằng

Hn = 2Hn-1 + 1

Không có hệ sô hằng

Bn = nBn-1

Không tuyến tính

an = an-1 + a²n-2

3.5. Phương pháp giải hệ thức truy hồi

• Giải hệ thức truy hồi

– Tìm công thức tổng quát cho số hạng an – Số hạng an không phải tính qua k phần tử trước nó.

• Phương pháp giải: – Phương pháp thế – Phương pháp phương trình đặc trưng

24 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

3. 5.1 Phương pháp thế:

• Dùng để giải hệ thức truy hồi bậc 1 • Các bược giải:

Thay an bởi an-1 Thay an-1 bởi an-2 --- Thay a0 bởi I0

• Thu được công thức trực tiếp cho an • Chứng minh tính đúng đắn

25 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

3.5.1. Phương pháp thế:

– Gọi Hn là số lần chuyển đĩa ít nhất của bài toán

tháp Hà nội.

– Hn = 2Hn-1 + 1, n ≥1,với H1 = 1 –

Chứng minh

26 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

– Dùng giải hệ thức truy hồi bậc 2 tuyến tính thuần

nhất hệ số hằng.

an = c1 an-1 + c2 an-2 , n ≥2 (1)

c1, c2- hằng số, c2 ≠ 0 . – Có phương trình đặc trưng:

r2 = c1 r + c2 (2)

r - hằng số.

27 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

 Nếu (2) có hai nghiệm thực phân biệt r1, r2 và có a0 = I0 ,a1 = I1, thì tồn tại duy nhất hằng số d1 , d2: 1 + d2 rn an = d1 rn 2 là nghiệm của (1)  Nếu (2) có nghiệm thực kép r1, có a1 = I0 ,a1 = I1

thì tồn tại duy nhất hằng số d1 , d2:

1 an = (d1 + d2 n )rn là nghiệm của (1)

28 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

2 là nghiệm của (1)

• Cần chứng minh: 1 + d2 rn • an = d1 rn • tồn tại d1 d2 duy nhất không ?

• chứng minh:

1 + d2 rn

2 với mọi n≥2

• c1 an-1 + c2 an-2 = d1 rn • I0 = d1 + d2 • I1 = d1 r1 + d2 r2 Suy ra d1 d2 duy nhất •

29 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

• Bài toán họ nhà thỏ có hệ thức truy hồi an = an-1 + an-2 , n≥2; a0 = 1, a1 = 1

Giải: Bước 1: Tìm nghiệm tổng quát Bước 2: Tìm hệ số hằng Bước 3: Nghiệm của hệ thức truy hồi

30 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

Bước 1: Tìm nghiệm tổng quát

– Phương trình đặc trưng: r2 = r +1 – Nghiệm của pt đặc trưng: r1 = (1+√5)/2 , r2 = (1-√5)/2 – Nghiệm tổng quát: an = d1((1+√5)/2)n + d2 ((1+√5)/2)n

Bước 2: Tìm hằng số d1 và d2 :

– Sử dụng điều kiện đầu: 1 = d1 + d2 1 = d1 (1+√5)/2 + d2 (1+√5)/2

31 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

Bước 2 (t.):

d1 = (1+√5) / 2√5 d2 = -(1-√5) / 2√5

Bước 3: Nghiệm của hệ thức truy hồi

32 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

Vi dụ 5.1 Giải hệ thức truy hồi sau: an = 6an-1 - 9an-2 , a0= 1, a1= 6.

33 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi

• Vi dụ 5.1

– Bước 1: Tìm nghiệm tổng quát

• Phương trình đặc trưng: r2 = 6r -9 • pt đặc trưng có nghiệm kép: r1 = r2 = 3 • Nghiệm tổng quát: an = (d1 + d2 n ) 3n

34 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

– Bước 2: Tìm hằng số d1 và d2 • Sử dụng điều kiện đầu: 1 = d1 d1 = 1 6= (d1 + d2) 3 d2 = 1 – Bước 3: Nghiệm của hệ thức truy hồi an = (1 + n ) 3n , n≥0

3.5. Giải hệ thức truy hồi bậc k ≥ 3

 Hệ thức truy hồi tuyến tính thuần nhất bậc k:

an = c1 an-1 + c2 an-2 +…+ ck an-k (*)

trong đó, c1, c2,…,ck - hằng số, ck ≠ 0 .

 Phương trình đặc trưng:

= c1 rk-1

+ c2 rk-2

+…+ ck (**)

35 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3

 Người ta chứng minh đươc kết quả sau:

 Nếu (*) có nghiệm thực phân biệt r1 ,r2 ,…,rk , thì

(**) có nghiệm tổng quát sau:

 Nếu (*) có t nghiệm thực phân biệt r1 ,r2 ,…,rt

tương ứng với các tính bội m1, m2 ,…, mt , thì (**) có nghiệm tổng quát:

36 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Giải hệ thức truy hồi bậc k ≥ 3

• Ví dụ 5.2 Giải hệ thức truy hồi sau: an = -3an-1- 3an-2 - an-3,

a0 = 1, a1 = -2, a2 = -1.

37 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3

• Ví dụ 5.2

Bước 1: Tìm nghiệm tổng quát

• Phương trình đặc trưng: r3 = - 3r2 - 3r - 1 • Nghiệm của pt đặc trưng: r1 = r2 = r3 = - 1 • Nghiệm tổng quát: an = (d10 + d11 n + d12 n2 )(-1)n

Bước 2: Tìm hằng số d10, d11 và d12

• Sử dụng điều kiện đầu: 1 = d10 , -2 = (d10 + d11 + d12)(-1) , -1 = d10 + d112 + d12 4

38 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3

Ví dụ 5.2

Bước 2 (t.):

d10 = 1 d11 = 3 d12 = -2

Bước 3: Nghiệm của hệ thức truy hồi an = (1 + 3 n - 2 n2 ) (-1)n , n ≥ 0

39 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

3. 6. Bài tập

1. an = 6an-1 - 11an-2 + 6an-3 , a0 =2, a1 = 5 , a2 = 15.

• ĐS: an = 1  2n + 2.3n.

40 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

THAT’S ALL; THANK YOU

• WHAT NEXT? BÀI TOÁN TỒN TẠI

Bài giảng Toán rời rạc: Bài 3 - TS. Nguyễn Văn Hiệu

Bài 3 "Kỹ thuật đếm nâng cao" thuộc bài giảng Toán rời rạc giới thiệu đến các bạn những nội dung: Một số khái niệm, mô hình hóa, định nghĩa, phương pháp đếm nâng cao, phương pháp thế, phương trình đặc trưng,...

BÀI 3

KỶ THUẬT ĐẾM NÂNG CAO

Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn

Nhắc lại!

Nội dung

3.1. Giới thiệu

3.1. Giới thiệu

10 000$

11 % tính gộp

30 năm

3.2. Các khái niệm

a0 = 5

Đệ quy dãy số {a n}

an = 2 an-1

Hệ thức truy hồi

3.2. Các khái niệm

an = 2an-1 an-1 = 2an-2, a1 = 2a0, a0=5

3.2. Các khái niệm

3.2. Các khái niệm

thức truy hồi an = 2 an-1 – an-2 với n = 2, 3, 4, …hay không?

 an = 5 với mọi n nguyên không âm, có là lời giải của hệ thức truy hồi an = 2an-1 – an-2 với n = 2, 3, 4, …hay không?

3.3. Mô hình hóa hệ thức truy hồi

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

 Nguyên lý cộng C(n,k) = C(n-1,k-1) + C(n-1,k) C(n,0) = C(n,n) =1

3.3. Mô hình hóa hệ thức truy hồi

3.3.1. Tính C(n,k)

3.3. Mô hình hóa hệ thức truy hồi

3.3.2. Bài toán tháp Hà nội • Mô tả bài toán toán:

3.3. Mô hình hóa hệ thức truy hồi

3.3.2. Bài toán tháp Hà nội

3.3. Mô hình hóa hệ thức truy hồi

MINH HỌA

NGHIỆM

A

C

B Vị trí bắt đầu trên tháp Hà Nội

A

B

C

3.3. Mô hình hóa hệ thức truy hồi

NGHIỆM

MINH HỌA

1 lần chuyển

Hn-1 lần chuyển

3.3. Mô hình hóa hệ thức truy hồi

1

Hn-1

Hn-1

• Nhập n đưa ra số lần chuyển  Quan tâm số lần chuyển  Cách chuyển không quan trọng

3.3. Mô hình hóa hệ thức truy hồi

3.3.3. Bài toán họ nhà thỏ (population of rabbits)

3.3. Mô hình hóa hệ thức truy hồi 3.3.3. Bài toán họ nhà thỏ f n = f n-1 + fn-2 , n≥ 3

3.4. Định nghĩa

hằng có dạng:

3.4. Định nghĩa

3.5. Phương pháp giải hệ thức truy hồi

3.5. Phương pháp giải hệ thức truy hồi

3. 5.1 Phương pháp thế:

3.5. Phương pháp giải hệ thức truy hồi

3.5.1. Phương pháp thế:

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

r2 = c1 r + c2 (2)

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

 Nếu (2) có hai nghiệm thực phân biệt r1, r2 và có a0 = I0 ,a1 = I1, thì tồn tại duy nhất hằng số d1 , d2: 1 + d2 rn an = d1 rn 2 là nghiệm của (1)  Nếu (2) có nghiệm thực kép r1, có a1 = I0 ,a1 = I1

1

an = (d1 + d2 n )rn là nghiệm của (1)

3.5. Phương pháp giải hệ thức truy hồi

3.5.2. Phương pháp phương trình đặc trưng

3.5. Phương pháp giải hệ thức truy hồi

• Bài toán họ nhà thỏ có hệ thức truy hồi an = an-1 + an-2 , n≥2; a0 = 1, a1 = 1

Giải: Bước 1: Tìm nghiệm tổng quát Bước 2: Tìm hệ số hằng Bước 3: Nghiệm của hệ thức truy hồi

3.5. Phương pháp giải hệ thức truy hồi

Bước 1: Tìm nghiệm tổng quát