Задача

Скількома способами можна потрапити на $n$ -ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$ .

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$ -ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

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]);
	}
}

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

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));
	}
}

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

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: рекурсія

e-olimp 8234. Сходинки