Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
ThanhHieu1699

ThanhHieu1699

    Hạ sĩ

  • Thành viên
  • 53 Bài viết

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.


:ukliam2: Khó khăn bạn gặp hôm nay sẽ làm tăng thêm sức mạnh bạn cần cho ngày mai. Đừng bỏ cuộc :ukliam2: 


#2
Kofee

Kofee

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

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.


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