Задача
Скількома способами можна потрапити на $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 |
class Main{ public static void main (String[] args) throws java.lang.Exception { java.util.Scanner i = new java.util.Scanner(System.in); int n = i.nextInt(); long array[] = new long[61]; array[0] = 1; array[1] = 1; array[2] = 2; for(int k = 3; k <= n; k++) { array[k] = array[k-1] + array[k-2] + array[k-3]; } System.out.print(array[n]); } } |
Рішення
Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (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 |
public class Main{ public static long array[] = new long[61]; public static long num_of_ways(int n){ if(array[n] == 0) { array[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3); return array[n]; } else { return array[n]; } } public static void main (String[] args) throws java.lang.Exception { java.util.Scanner i = new java.util.Scanner(System.in); int n = i.nextInt(); array[0] = 1; array[1] = 1; array[2] = 2; System.out.print(num_of_ways(n)); } } |
Посилання
Умова задачі на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone