Вопрос, который вызвал трудности
В городе Козьмодемьянске, расположенном на холмах, имеется много лестниц. Одним из местных детей является скатывание мяча
Ответ экспертов Учись.Ru
Чтобы дать полноценный ответ, был привлечён специалист, который хорошо разбирается в теме «ЕГЭ (школьный)». Ваш вопрос звучал так: В городе Козьмодемьянске, расположенном на холмах, имеется много лестниц. Одним из местных детей является скатывание мяча
После обсуждения с другими специалистами сервиса мы пришли к выводу, что правильный ответ на ваш вопрос будет звучать следующим образом:
Задача решается методом динамического программирования
Найдем зависимость для S(n) - количества маршрутов для лестницы из n ступенек с количеством маршрутов для лестницы с меньшим количеством ступенек.
Рассмотрим простейшие случаи.
Для лестницы из 1 ступеньки имеется всего один маршрут
Для лесенки из 2 ступенек имеются 2 маршрута.
Для лестницы из n ступенек имеем
S(n)= S(n-1)+ S(n-2)
Используя эти соотношения, последовательно вычисляем S(1), S(2),…. пока не получим значение для лестницы с заданным числом ступенек.
Для хранения значения S необходимо использовать тип long long int в программах на языке С++ и int64 в программах на языке Паскаль.
Найдем зависимость для S(n) - количества маршрутов для лестницы из n ступенек с количеством маршрутов для лестницы с меньшим количеством ступенек.
Рассмотрим простейшие случаи.
Для лестницы из 1 ступеньки имеется всего один маршрут
Для лесенки из 2 ступенек имеются 2 маршрута.
Для лестницы из n ступенек имеем
S(n)= S(n-1)+ S(n-2)
Используя эти соотношения, последовательно вычисляем S(1), S(2),…. пока не получим значение для лестницы с заданным числом ступенек.
Для хранения значения S необходимо использовать тип long long int в программах на языке С++ и int64 в программах на языке Паскаль.