Nhờ các anh/chị chỉ giúp

[humalo]

Một người bước lên cầu thang gồm n bậc, mỗi bước lên có thể thực hiện theo một trong 3 cách (bước 1 bậc, bước 2 bậc, bước 3 bậc). Hỏi có bao nhiêu phương án để lên cầu thang đó

[kimduquan]

áp dụng quy tăc nhân ta có 3^n cách.

[cal]

Bài này dạng toán giải bằng đệ qui, kết quả cũng là 1 công thức đệ qui.

Gọi An là số phương án để lên cầu thang n bậc.

Ta có:
A1 = 1 (cầu thang 1 bậc: bước 1 bậc là hết ==> 1 cách)
A2 = 2 (thang 2 bậc: bước 1, 1 hoặc 2 ==> 2 cách)
A3 = 4 (thang 3 bậc: bước 1,1,1 hoặc 1,2 hoặc 2,1 hoặc 3 ==> 4 cách)

Với n >= 4:
Ở bước đầu tiên, người leo cầu thang có 3 cách: bước 1 bậc, bước 2 bậc, hoặc bước 3 bậc.
nếu bước 1 bậc, sẽ có An-1 cách để bước n-1 bậc thang còn lại.
nếu bước 2 bậc, sẽ có An-2 cách để bước n-2 bậc thang còn lại.
nếu bước 3 bậc, sẽ có An-3 cách để bước n-3 bậc thang còn lại.
Vậy số cách sẽ là: An = An-1 + An-2 + An-3, với n >= 4

Tổng hợp:
A1 = 1
A2 = 2
A3 = 4
An = An-1 + An-2 + An-3, với n >= 4

[quangtq]

Không thể là 3^n đâu anh ạ. Ví dụ khi bước mà còn 2 bậc thì chỉ có 2 cách.

[bld]

QHD : bn là số cách lên bậc thang n
bn=bn-1+bn-2+bn-3

[quangtq]

Bài này QHĐ thì dễ rồi. Nhưng nghĩ mãi ko ra cách giải = tay (Toán)

[bld]

bài này giống như dãy f ibonaci vậy . ko biết có công thức nào tính ra ngay dc số f ibonaci thứ n ko . nếu có thì khả năng bài này cũng có

[quangtq]

Tính được, số ****naci thứ n có giá trị là:
X[n] = (1/sqrt(5)) * (((1+sqrt(5))/2)^n - (1-sqrt(5))/2)^n).
Mình đọc ở đâu đó. Ko biết có đúng ko