Задача
Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.
Вхідні дані
Одне число $n$ — номер сходинки $(n \leqslant 60)$.
Вихідні дані
Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.
Тести
| Вхідні дані | Вихідні дані |
|---|---|
| 0 | 1 |
| 5 | 13 |
| 15 | 5768 |
| 32 | 181997601 |
| 60 | 4680045560037375 |
Код № 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { int n; cin >> n; long long arr[61] = {0}; arr[0] = 1; arr[1] = 1; arr[2] = 2; for(int i = 3; i <= n; i++) { arr[i] = arr[i-1] + arr[i-2] + arr[i-3]; } cout << arr[n]; return 0; } |
Рішення
Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).
Код № 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; long long arr[61] = {0}; long long num_of_ways(int n) { if(arr[n]) { return arr[n]; } else { arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3); } return arr[n]; } int main() { int n; cin >> n; arr[0] = 1; arr[1] = 1; arr[2] = 2; cout << num_of_ways(n); return 0; } |
Посилання
Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone