Пусть искомое число способов равно fn. Преодолеть лестницу из одной ступеньки можно единственным способом (f1 = 1), а из двух – двумя: прыжком через ступеньку или двумя шагами по последовательным ступенькам (f2 = 2). Если n > 2, то первым шагом можно ступить на следующую ступеньку, и тогда останется пройти (n – 1) ступенек, а сделать это можно fn – 1способами. Кроме того, можно сразу перепрыгнуть через ступеньку, и тогда останется преодолеть (n – 2) ступенек, а это сделать можно fn – 2 способами. Таким образом, общее число способов fn = fn – 1 + fn – 2. Таким образом, fn равно (n – 1)-му числу Фибоначчи un – 1.
|
Комментариев нет:
Отправить комментарий