Question

На земле перед лестницей стоит Петя, который собирается подняться на десятую ступеньку. Петя или шагает на следующую ступеньку или прыгает через одну ступеньку. Сколькими способами Петя может добраться до десятой ступеньки?

Answer 1

Стоит Петя на 0-ой ступеньке. Добраться действиями +1 (шагает на следующую ступеньку) и +2(прыгает через одну ступеньку)  до 10-ой. В кружок обведено кол-во вариантов

Answer 2

Пусть мы рассмотрим количество способов добраться до каждой из ступенек от 1 до 10. Обозначим через F(n) количество способов добраться до n-ой ступеньки.

Для n = 1, очевидно, F(1) = 1, так как есть только один способ - стоять на первой ступеньке.

Для n = 2, также F(2) = 1, потому что есть только один способ - шагнуть на вторую ступеньку.

Для n = 3, существует два способа добраться до третьей ступеньки: шагнуть с первой на третью ступеньку или сначала перейти на вторую, а затем через неё на третью. Таким образом, F(3) = 2.

Для n = 4, у нас есть три способа: шагнуть с первой на четвертую, сначала перейти на вторую, затем на третью и на четвертую, или сначала перейти на третью, затем на вторую и на четвертую. Таким образом, F(4) = 3.

Можно заметить, что F(n) = F(n-1) + F(n-2), то есть количество способов добраться до n-ой ступеньки равно сумме количества способов добраться до (n-1)-ой и (n-2)-ой ступенек.

Продолжая этот ряд, мы можем вычислить F(10) используя предыдущие значения:

F(5) = F(4) + F(3) = 3 + 2 = 5 F(6) = F(5) + F(4) = 5 + 3 = 8 F(7) = F(6) + F(5) = 8 + 5 = 13 F(8) = F(7) + F(6) = 13 + 8 = 21 F(9) = F(8) + F(7) = 21 + 13 = 34 F(10) = F(9) + F(8) = 34 + 21 = 55

Итак, существует 55 различных способов добраться до десятой ступеньки.