▼

29 апр. 2012 г.

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


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

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



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

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

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

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

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

  1. vasste30 апреля, 2012 00:13

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

    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

    ОтветитьУдалить
  2. Vladimir Dolzhenko30 апреля, 2012 00:31

    @vasste

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

    ОтветитьУдалить
  3. Сергей30 апреля, 2012 04:02

    Если 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. Вроде так...

    ОтветитьУдалить