Недавно решал олимпиадную задачу, когда я ее "решил" (как я думал) она оказалась очень громоздкой, ну и естественно не правильной. На следующий день поинтересовался у приятеля и он сказал, что задача решается намного проще с помощью метода последовательностей, я долго думал что это, но так и не придумал помогите.
P.S. в задаче нужно было просчитать число вариантов.
Michael_Rybak
24.11.2006 18:44
Никогда не слышал о методе последовательностей
Что за задача-то?
Ну это даже не метод, а как я понял способ. Вот задача:
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через две. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.
Входной файл
Одно число 0<N<30
Выходной файл
Одно число – количество маршрутов.
Michael_Rybak
24.11.2006 19:31
Ну, так это просто видоизмененные числа Фибонначи. Если бы шарик мог прыгать только на следующую или через одну, это и были бы числа Фибонначи, f(n) = f(n - 1) + f(n - 2). А так еще одно слагаемое добавляется
а где можно подробнее узнать о этих числах?
Michael_Rybak
25.11.2006 2:18
спасибо
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста,
нажмите сюда.