CamCertGeneral method / Cách làm tổng quát
Bước 1: Liệt kê số cách bước lên các bậc đầu tiên.
Bước 2: Tìm ra quy luật: Số cách bước lên một bậc bất kì bằng tổng số cách bước lên các bậc liền trước nó.
Bước 3: Dựa vào quy luật để tính số cách đi hết cầu thang.
Lưu ý: Số cách bước lên bậc bị hỏng bằng 0.
Example / Ví dụ:
A flight of stairs has 9 steps. Peter can go up for 1 step or 2 steps each time. How many ways are there for Peter to go up the stairs?
Một cầu thang có 9 bậc. Peter có thể bước lên trên 1 bậc hoặc 2 bậc mỗi lân. Hỏi có bao nhiêu cách để Peter bước hết cầu thang?
Lời giải
Bước lên bậc thứ 1: 1 cách.
Bước lên bậc thứ 2: cách bước :1-1 hoặc 2. Suy ra có 2 cách.
Bước lên bậc thứ 3: cách bước :1-1-1, 2-1 hoặc 1-2. Suy ra có 3 cách.
Để bước lên bậc thứ 3, ta cần bước lên trực tiếp từ bậc thứ 2 hoặc bậc thứ 1.
Ta gọi bậc thứ 2 và bậc thứ 1 là BẬC LIỀN TRƯỚC của bậc thứ 3.
Vậy số cách bước lên bậc thứ 3 bằng tổng số cách bước lên bậc thứ 2 và bậc thứ 1.
Để bước lên bậc thứ 4, ta cần bước lên trực tiếp từ bậc thứ 3 hoặc bậc thứ 2. (Ta không
thể từ bậc 1 bước thẳng lên bậc 4).
Ta gọi bậc thứ 3 và bậc thứ 2 là BẬC LIỀN TRƯỚC của bậc thứ 4.
Vậy số cách bước lên bậc thứ 4 bằng tổng số cách bước lên bậc thứ 3 và bậc thứ 2.
Tương tự, ta rút ra được quy luật:
Số cách bước lên một bậc bất kì bằng tổng số cách bước lên các BẬC LIỀN TRƯỚC nó (trước 1 bậc hoặc 2 bậc).
Ta có bảng sau:
Vậy có 55 cách bước hết cầu thang.
Đáp số: 55 cách.
Example 2:
A flight of stairs has 9 steps. Peter can go up for 1 step or 3 steps each time. How many ways are there for Peter to go up the stairs?
Một cầu thang có 9 bậc. Peter có thể bước lên trên 1 bậc hoặc 3 bậc mỗi lân. Hỏi có bao nhiêu cách để Peter bước hết cầu thang?
Lời giải
Bước lên bậc thứ 1: 1 cách.
Bước lên bậc thứ 2: cách bước :1-1. Suy ra có 1 cách.
Bước lên bậc thứ 3: cách bước :1-1-1 hoặc 3. Suy ra có 2 cách. 2
Để bước lên bậc thứ 4, ta cần bước lên trực tiếp từ bậc thứ 3 hoặc bậc thứ 1. (Ta không thể từ bậc 2 bước thẳng lên bậc 4).
Ta gọi bậc thứ 3 và bậc thứ 1 là BẬC LIỀN TRƯỚC của bậc thứ 4.
Vậy số cách bước lên bậc thứ 4 bằng tổng số cách bước lên bậc thứ 3 và bậc thứ 1.
Tương tự, ta rút ra được quy luật: Số cách bước lên một bậc bất kì bằng tổng số cách bước lên các BẬC LIỀN TRƯỚC nó (trước 1 bậc hoặc 3 bậc).
Ta có bảng sau:
Đáp số: 19 cách.