1. Trang chủ
  2. Tiểu học
  3. Phương pháp truy hồi
Phương pháp truy hồi
07.08.2019 Bình luận

SỬ DỤNG PHƯƠNG PHÁP TRUY HỒI ĐỂ GIẢI BÀI TOÁN ĐẾM

Biên soạn: Trần Hữu Hiếu

Bài toán: We want to cover the following 2 x 8 rectangle by using eight 2 x 1 rectangles.

 

Each 2 x 1 rectangle is placed horizontally or vertically.

PHUONG PHAP TRUY HOI 

How many arrangements are possible to cover the 2 x 8 rectangle?

Dịch đề: Chúng ta muốn phủ kín lưới hình chữ nhật kích thước 2 x 8 bằng cách sử dụng 8 hình chữ nhật kích thước 2 x 1.

PHUONG PHAP TRUY HOI 

Mỗi hình chữ nhật chỉ được đặt thẳng đứng hoặc nằm ngang.

PHUONG PHAP TRUY HOI 

Hỏi có tất cả bao nhiêu cách sắp xếp để có thể phủ kín lưới hình chữ nhật 2 x 8 ở trên?

Phân tích:

Khi tiếp cận bài toán này, thoạt đầu tiên, chúng ta thường thử một vài cách sắp xếp, và tất nhiên, chúng ta sẽ xuất phát từ các ô vuông bên trái. Ta thấy, ô vuông ở góc trên bên trái có thể được che phủ theo 1 trong 2 cách dưới đây:

Cách 1:

PHUONG PHAP TRUY HOI 

Cách 2:

PHUONG PHAP TRUY HOI  

Với cách 1, ta nhận thấy số cách để phủ kín hình 2 x 8 lúc này chính là số cách để phủ kín hình 2 x 7.

PHUONG PHAP TRUY HOI 

Với cách 2, ta thấy ô vuông góc dưới bên trái cũng được che phủ bởi 1 hình 2 x 1 đặt nằm ngang.

Phần còn lại chính là 1 hình chữ nhật 2 x 6.

PHUONG PHAP TRUY HOI

Từ đó ta nghĩ đến việc đi xây dựng cách giải dựa vào việc xây dựng công thức truy hồi để tính số cách che phủ một hình chữ nhật có kích thước 2 x n, trong đó n là số tự nhiên lớn hơn 0.

Lời giải:

Gọi Ak là số cách dùng k hình chữ nhật kích thước 2 x 1 để phủ kín hình chữ nhật 2 x k. (với k là số tự nhiên lớn hơn hoặc bằng 2).

Dễ thấy:

A1 = 1;

PHUONG PHAP TRUY HOI  

A2 = 2;

PHUONG PHAP TRUY HOI  

A3 = 3

PHUONG PHAP TRUY HOI  

Xét hình chữ nhật kích thước 2 x n (n  3)

Xét ô vuông góc trên bên trái của hình 2 x n, ta có 2 khả năng sau:

TH1: Ô vuông góc trên bên trái được che bởi hình 2 x 1 đặt thẳng đứng. Khi đó phần còn lại chính là hình 2 x (n – 1)                                                                                              (1)

PHUONG PHAP TRUY HOI  

TH2: Ô vuông góc trên bên trái được che bởi hình 2 x 1 nằm ngang, khi đó ô vuông góc dưới bên trái cũng được che bởi hình 2 x 1 nằm ngang. Khi đó phần còn lại chính là hình 2 x (n – 2)   (2)

PHUONG PHAP TRUY HOI  

Từ (1) và (2) ta xây dựng được công thức truy hồi như sau:

            An = An – 1 + An-2

Từ đó dễ dàng tính viết dược dãy An chính là dãy: 1; 2; 3; 5; 8; 13; 21; 34

Đáp án: A8 = 34

Một số bài toán tương tự:

Bài 1. Có bao nhiêu dãy số gồm toàn các chữ số 1 và 2 và có tổng các số hạng  bằng 15.

Bài 2. Có bao nhiêu số có 8 chữ số, được tạo thành từ các chữ số 1, 2, 3 sao cho không có hai chữ số 1 nào đứng liền nhau.

Bài 3. Có một cầu thang gồm n bậc. Mỗi bước đi có thể bước lên 1 bậc hoặc bước lên 2 bậc. Tìm số các để đi đến bậc thứ n?

Bài 4. a) Cho hình như hình vẽ. Có bao nhiêu cách tô màu các hình tròn bằng 3 màu khác nhau sao cho 2 hình tròn bất kỳ được nối bởi 1 cạnh có màu khác nhau.

PHUONG PHAP TRUY HOI  

b) Có bao nhiêu cách tô màu 5 đỉnh của hình ngũ giác bằng 3 màu sao cho hai đỉnh được nối với nhau bởi 1 cạnh của ngũ giác thì khác màu nhau.

PHUONG PHAP TRUY HOI  

Bài 5. Gọi Sn là số cách tô màu n đỉnh của hình n-giác bằng 3 màu sao cho hai đỉnh được nối với nhau bằng 1 cạnh của đa giác thì khác màu nhau. . Hãy tìm công thức truy hồi để tính Sn.