Bậc thang: đếm số cách bước 1 hoặc 2 bậc
Một chiếc cầu thang n bậc, mỗi bước đi được 1 hoặc 2 bậc. Đếm số cách đi hết cầu
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-loop-basics, python-fibonacci-intro.
Nội dung đề bài
Mô tả bài toán
Một chiếc cầu thang n bậc, mỗi bước đi được 1 hoặc 2 bậc. Đếm số cách đi hết cầu thang là bài quy hoạch động nhỏ nhất có thể: chỉ cần biết hai đáp án liền trước là suy ra đáp án kế tiếp, nên bộ nhớ chỉ cần hai ô.
Yêu cầu
Viết hàm count_ways(n) trả về số cách khác nhau để đi từ chân lên hết n bậc, với mỗi bước dài 1 hoặc 2 bậc. Cách đi được phân biệt bằng dãy độ dài các bước, không phải bằng số bước.
Công thức truy hồi (đã kiểm tra bằng tay): ways(0) = 1 (đứng yên là một cách), ways(1) = 1, và ways(n) = ways(n - 1) + ways(n - 2) với n >= 2.
Quy ước nộp bài
Nộp hàm count_ways trong solution.py. Hệ thống gọi hàm trực tiếp bằng tham số từ khoá n và so giá trị trả về với kết quả đã cho; không đọc stdin và không in ra stdout.
Input
- n: số bậc của cầu thang, số nguyên từ 0 đến 30.
Output
Một số nguyên là số cách đi hết cầu thang.
Ràng buộc
- Mỗi bước chỉ dài 1 hoặc 2 bậc; bước dài 3 bậc là bài toán khác.
- n = 0 là trường hợp biên: đứng yên vẫn tính là một cách, nên trả về 1.
- Đáp án tăng rất nhanh, n = 20 đã là 10946.
Ví dụ 1
Input
count_ways(n=1)
Output
1
Ví dụ 2
Input
count_ways(n=2)
Output
2
Giải thích
Với n = 2 có hai cách: 1 + 1 và 2, nên hàm trả về 2. Với n = 5: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1 — tổng cộng 8 cách.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
