Cầu thang có n bậc thang được đánh số từ 1 đến n. Mỗi bước thầy Tiến có thể đi lên 1 bậc thang, 2 bậc thang hoặc 3 bậc thang, có thể đi xuống 1 bậc thang, 2 bậc thang hoặc 3 bậc thang. Hỏi nếu thầy Tiến ở chân cầu thang đi lên đỉnh cầu thang, rồi đi xuống chân cầu thang nhưng chỉ được bước vào các vị trí mà lúc dưới đi lên. Hỏi thầy Tiến có bao nhiêu cách đi với n = 11? Ví dụ n = 3 thì có 9 cách.
Cầu thang có n bậc thang được đánh số từ 1 đến n. Mỗi bước thầy Tiến có thể đi lên 1 bậc thang, 2 bậc thang hoặc 3 bậc thang, có thể đi xuống 1 bậc th
#2
Đã gửi 20-12-2015 - 15:51
Cầu thang có n bậc thang được đánh số từ 1 đến n. Mỗi bước thầy Tiến có thể đi lên 1 bậc thang, 2 bậc thang hoặc 3 bậc thang, có thể đi xuống 1 bậc thang, 2 bậc thang hoặc 3 bậc thang. Hỏi nếu thầy Tiến ở chân cầu thang đi lên đỉnh cầu thang, rồi đi xuống chân cầu thang nhưng chỉ được bước vào các vị trí mà lúc dưới đi lên. Hỏi thầy Tiến có bao nhiêu cách đi với n = 11? Ví dụ n = 3 thì có 9 cách.
Gọi $S_{n}$ là số cách thỏa ycđb.
Muốn lên và xuống thang n bậc ($n> 3$) có 3 cách:
- Bước tới bậc n-1 rồi bước 1 bậc để lên n và xuống 1 bậc: 1 cách.
- Bước tới bậc n-2 rồi bước 2 bậc để lên n, sau đó xuống 2 bậc hoặc bước lên tửng bậc, xuống từng bậc hoặc xuống 2 bậc: 3 cách.
- Bước tới bậc n-3 để lên n rồi xuống thang: 9 cách (lấy theo VD cho nhanh).
Ta có hệ thức truy hồi, với $n> 3$:
$S_{n}=S_{n-1}+S_{n-2}+S_{n-3}$
Khởi tạo: $S_{1}=1, S_{2}=3, S_{3}=9$
Suy ra: $S_{11}=157+289+531=977$ cách.
- nguyendangloc17 yêu thích
Xê ra, để người ta làm Toán sĩ!
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh