Последовательности, Что это такое? Опции

[SkIv]

Недавно решал олимпиадную задачу, когда я ее "решил" (как я думал) она оказалась очень громоздкой, ну и естественно не правильной. На следующий день поинтересовался у приятеля и он сказал, что задача решается намного проще с помощью метода последовательностей, я долго думал что это, но так и не придумал помогите.
P.S. в задаче нужно было просчитать число вариантов.

[Michael_Rybak]

Никогда не слышал о методе последовательностей
Что за задача-то?

[SkIv]

Ну это даже не метод, а как я понял способ. Вот задача:
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через две. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Входной файл
Одно число 0<N<30

Выходной файл
Одно число – количество маршрутов.

[Michael_Rybak]

Ну, так это просто видоизмененные числа Фибонначи. Если бы шарик мог прыгать только на следующую или через одну, это и были бы числа Фибонначи, f(n) = f(n - 1) + f(n - 2). А так еще одно слагаемое добавляется

[SkIv]

а где можно подробнее узнать о этих числах?

[Michael_Rybak]

Даже не знаю

Сообщение отредактировано: Michael_Rybak - 24.11.2006 22:20

[SkIv]

спасибо