Перед Вами лестница из 100 ступенек. Каждым шагом Вы можете подняться вверх либо на одну ступеньку, либо на две ступеньки. Сколькими различными способами можно подняться по этой лестнице наверх?
Решение
Как мы можем оказаться на верхней, 100-й, ступеньке? Либо поднявшись на одну ступеньку с 99-й, либо на две ступеньки - с 98-й. Если обозначить через F(n) количество способов подняться на лестницу из n ступенек, то можно записать, что F(100) = F(99) + F(98).
Проведя точно такие же рассуждения для 99-й ступеньки, мы придём к выводу, что F(99) = F(98) + F(97).
В общем случае,
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 1
А это ни что иное, как определение последовательности Фибоначчи. Как любят писать в учебниках мат. анализа, вычисление 100-го члена этой последовательности оставляем читателю в качестве упражнения.
Решение
Как мы можем оказаться на верхней, 100-й, ступеньке? Либо поднявшись на одну ступеньку с 99-й, либо на две ступеньки - с 98-й. Если обозначить через F(n) количество способов подняться на лестницу из n ступенек, то можно записать, что F(100) = F(99) + F(98).
Проведя точно такие же рассуждения для 99-й ступеньки, мы придём к выводу, что F(99) = F(98) + F(97).
В общем случае,
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 1
А это ни что иное, как определение последовательности Фибоначчи. Как любят писать в учебниках мат. анализа, вычисление 100-го члена этой последовательности оставляем читателю в качестве упражнения.
куда лучше она формулируется для чисел триббоначи, квардоначчи... и т.п до гуглоначи
ОтветитьУдалить