Есть лестница с 10 ступеньками.
За один шаг можно подняться либо на одну ступеньку, либо на две, либо на три ступеньки.
Сколько существует разных способов подняться на последнюю ступеньку ?
замечание #1 Считать, что варианты 3 + 3 + 3 + 1 и 1 + 3 + 3 + 3 независимыми.
замечание #2 Последний шаг должен приводить ровно на последнюю ступеньку, н-р, недопустим вариант 3 + 3 + 3 + 2.
внимание! комментарии содержат ответ.
3 комментария:
Наверное самое просто решение, как задача о рюкзаке, просто нарисовать граф
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
@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. Вроде так...
Отправить комментарий