Cho tổng số bậc thang n. Người có thể nhảy 1, 2 hoặc 3 bậc mỗi lần. Tìm số cách để lên đến đỉnh.
Dùng đệ quy: để đến bậc i, người phải nhảy từ bậc i-1 (bỏ 1), i-2 (bỏ 2) hoặc i-3 (bỏ 3).
Hãy hiểu qua ví dụ.
Đầu vào
N=3 steps
Đầu ra
Count of ways to reach the nth stair using step 1, 2 or 3 are: 4
Giải thích
Có 3 bậc: Nhảy từ đầu (bỏ 3): 3; Từ bậc 1 (bỏ 2): 1+2; Từ bậc 2 (bỏ 1): 2+1; Không bỏ: 1+1+1
Đầu vào
N=6 steps
Đầu ra
Count of ways to reach the nth stair using step 1, 2 or 3 are: 24
Giải thích
Có 6 bậc. Các cách: 1+1+1+1+1+1, 2+1+1+1+1, 3+1+1+1, 3+1+2, 3+2+1, 3+3, v.v.
Phương pháp
- Nhận số nguyên steps.
- Hàm stairs_step(int steps) trả về số cách.
- Khởi tạo count = 0.
- Nếu steps == 0 trả 1.
- Nếu steps == 1 trả 1.
- Nếu steps == 2 trả 2 (1+1 hoặc 2).
- Ngược lại: ways = stairs_step(steps-3) + stairs_step(steps-2) + stairs_step(steps-1).
Ví dụ
#include <iostream> using namespace std; int stairs_step(int steps){ if(steps == 0){ return 1; } else if(steps == 1){ return 1; } else if (steps == 2){ return 2; } else{ return stairs_step(steps - 3) + stairs_step(steps - 2) + stairs_step(steps - 1); } } int main(){ int steps = 5; cout<<"Count of ways to reach the nth stair using step 1, 2 or 3 are: "<<stairs_step(steps); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Count of ways to reach the nth stair using step 1, 2 or 3 are: 13