29 апр. 2012 г.

Задачка: лестница


Есть лестница с 10 ступеньками.

За один шаг можно подняться либо на одну ступеньку, либо на две, либо на три ступеньки.



Сколько существует разных способов подняться на последнюю ступеньку ?

замечание #1 Считать, что варианты 3 + 3 + 3 + 1 и 1 + 3 + 3 + 3 независимыми.

замечание #2 Последний шаг должен приводить ровно на последнюю ступеньку, н-р, недопустим вариант 3 + 3 + 3 + 2.

внимание! комментарии содержат ответ.

3 комментария:

vasste комментирует...

Наверное самое просто решение, как задача о рюкзаке, просто нарисовать граф

0
1 2 3
1 2 3 1 2 3 1 2 3

и

if (sum) = 10 cnt++
else
steps += node_weight
recursion
steps -= node_weight

Vladimir Dolzhenko комментирует...

@vasste

идея не плохая, но задача даже более математическая, чем программистская

Сергей комментирует...

Если m[n] - это количество шагов, которое требуется для преодоления лестницы из n ступеней, то, очевидно, m[n] = m[n-1]+m[n-2]+m[n-3], где n>=3, m[0]=1 (по определению), m[1] = 1, m[2] = 2. m[10] вручную считать лень, так что пишем простую программу:

int[] m = new int[11];
m[0] = m[1] = 1;
m[2] = 2;
for (int i = 3; i <=10; i++)
m[i] = m[i-1] + m[i-2] + m[i-3];
System.out.println(m[10]);

Выдаёт 274. Вроде так...