Câu hỏi của Nguyễn Đức Hải Đăng

Question

Một cầu thang có 7 bậc. Mỗi lần bước, Bill có thể bước lên 1 bậc hoặc 2 bậc. Hỏi Bill có bao nhiêu cách để đi hết cầu thang?
A. 34 B. 13 C. 21 D. 18

Nguyễn Đức Trí · Accepted Answer

Gọi $F\left(n\right)$ là số cách để Bill đi hết cầu thang $n$ bậc$F\left(1\right)=1$ (Chỉ có $1$ cách đi $1$ bậc)$F\left(2\right)=2$ (Có $2$ cách: $1+1$ hoặc $2$)Đi $1$ bậc từ bậc $n-1$, sau đó đi tiếp $n-1$ bậcĐi $2$ bậc từ bậc $n-2$, sau đó đi tiếp $n-2$ bậc$\Rightarrow F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)$ (Dãy Fibonaci với $n\left(bậc\right)$)$F\left(3\right)=2+1=3$$F\left(4\right)=3+2=5$$F\left(5\right)=5+3=8$$F\left(6\right)=8+5=13$$F\left(7\right)=13+8=21$$\Rightarrow C.21$Câu trả lời: Gọi $F\left(n\right)$ là số cách để Bill đi hết cầu thang $n$ bậc$F\left(1\right)=1$ (Chỉ có $1$ cách đi $1$ bậc)$F\left(2\right)=2$ (Có $2$ cách: $1+1$ hoặc $2$)Đi $1$ bậc từ bậc $n-1$, sau đó đi tiếp $n-1$ bậcĐi $2$ bậc từ bậc $n-2$, sau đó đi tiếp $n-2$ bậc$\Rightarrow F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)$ (Dãy Fibonaci với $n\left(bậc\right)$)$F\left(3\right)=2+1=3$$F\left(4\right)=3+2=5$$F\left(5\right)=5+3=8$$F\left(6\right)=8+5=13$$F\left(7\right)=13+8=21$$\Rightarrow C.21$

Khoá học trên OLM (olm.vn)

Khoá học trên OLM (olm.vn)