Рекурсия · 11 из 19
Не считать дважды
На плакате с древом нарисована лестница в архив: столько-то ступенек, и подниматься можно по одной, по две, а у пожилых родственников выходит и по три. Дядя Миша считает, сколькими способами лестницу можно пройти, и на тридцатой ступеньке его программа задумывается на минуты.
Что сделать
Посчитайте, сколькими способами можно подняться по лестнице в архив, — так, чтобы программа не задумывалась на минуты.
Что приходит
vysota— сколько ступенек, целое от нуляshag_maks— на сколько ступенек можно шагнуть за раз, от 1 до этого числаpamyat— служебный аргумент для запомненных ответов; при вызове не передаётся
Что вернуть
Сколькими способами можно подняться; способы, отличные порядком шагов, — разные; высота ноль — 1; на сотне ступенек — мгновенно.
Допишите функцию skolko_putey в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Три ступеньки шагами по 1 и 2: 1+1+1, 1+2, 2+1 — три способа. На десяти ступеньках их уже 89.
skolko_putey(10, 2)
89
Функция принимает высоту лестницы (целое, не меньше нуля) и наибольший шаг (целое больше нуля). Возвращает, сколькими способами можно подняться, если за раз разрешено перешагнуть от одной ступеньки до наибольшего шага. Способы, отличающиеся порядком шагов, считаются разными. Высота ноль даёт один способ — стоять на месте. Функция должна отвечать на высоте в сотню ступенек без заметной задержки.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.