Задача про лестницу :)

Когда колено болит и хромаешь, поневоле начинаешь считать ступеньки.

Давайте представим себе, что за один шаг мы можем подняться либо на одну, либо на две ступеньки.

Всего ступенек на лестнице N.

Сколько существует способов подняться по лестнице?

Для решения не нужно ничего, кроме элементарной логики.

Очевидно, что на первую ступеньку можно подняться только одним способом, сделав короткий шаг, а на вторую - двумя, либо два коротких шага, либо один длинный.

Как насчёт третьей ступеньки?

По условию, существует только два варианта попасть на неё - либо мы сделали короткий одиночный шаг со ступеньки 2, либо это был двойной шаг со ступеньки 1.

Мы знаем, что у нас есть только один способ достичь первой ступеньки, и два способа достичь второй. Так как третьей ступеньки мы можем достичь со второй или с первой, сложив эти количества, видим, что подняться на третью ступеньку имеется 3 способа (1-1-1, 1-2, 2-1).

Та же логика применяется и дальше. Попасть на четвёртую ступеньку можно со второй (куда было два способа добраться) или с третьей (куда можно влезть тремя способами). Получается пять способов для ступени 4.

Если кто ещё не догадался, мы встретились с миллион первым применением чисел Фибоначчи, а для них имеется явная формула вычисления N-го члена ряда, известная как формула Бине.

Таким образом, проблема решается со сложностью O(1) и ничего перебирать не надо.

Между прочим, подобную задачу часто предлагали решить соискателям при трудоустройстве программистом в компанию Google :)

30.05.2018, 12:10 [2053 просмотра]