Очередная задачка с собеседования
Сейчас будет математическая задачка, которую мы решим вроде бы варварским методом, но на самом деле по-умному.
Условия: есть лестница с известным количеством ступенек. На каждом шаге мы можем наступать на каждую ступеньку или шагнуть через одну, пройдя сразу 2 ступеньки за один шаг. Нужно найти число способов, которыми можно подняться по лестнице.
Например, если у лестницы 4 ступеньки, то варианты будут такие:
1→1→1→1
1→1→2
1→2→1
2→1→1
2→2
Сами варианты выводить не нужно, достаточно общего количества.
Мы могли бы решить эту задачу какой-то математикой, но мы не будем этого делать. Мы решим её с помощью программирования.
Решение
Вся сложность в этой задаче в том, что на каждом шаге у нас появляется выбор — шагнуть на одну или на две ступеньки.
Чтобы была понятна вся вариативность, нарисуем схему для пяти ступенек:
Если присмотреться к схеме, то видно, что начиная с третьей ступени количество вариантов начинает зависеть от предыдущего и предпредыдущего шага:
- для третьей ступеньки — от количества вариантов на второй и первой;
- для четвёртой ступеньки — от количества вариантов на третьей и второй;
- для пятой ступеньки — от количества вариантов на четвёртой и третьей.
Эта схема отлично укладывается в рекурсию — самоповторяющийся алгоритм, в котором известны только несколько начальных значений, а все остальные считаются на их основе. Единственное, с чем нам осталось разобраться, — с этими начальными значениями.
Если ступенек нет, рекурсия должна вернуть тоже ноль вариантов. Это логично: нет ступенек — нет вариантов, как шагать.
Если ступенька одна, то возвращаем тоже один вариант — это один шаг.
Если ступеньки две, то тут уже два варианта: 1→1 или сразу шагнуть на 2.
А если ступенек 3 и больше, то надо складывать количество вариантов на двух предыдущих этапах. В итоге у нас получилась классическая рекурсия, где на каждом шаге мы вычисляем, сколько вариантов у нас дойти до текущей ступеньки.
Чтобы было удобнее, все расчёты по каждой ступеньке будем хранить в массиве — так проще будет с ними работать. Зная всё это, напишем простую рекурсию на Python:
После запуска программа выдаст число 8 — значит, мы всё сделали правильно и уложились в 10 минут.