|
Название задачи: Последовательности из 0 и 1 . |
 |
Условие
Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).
Выходные данные
В выходной файл вывести количество искомых последовательностей.
Пример входного файла
5
Пример выходного файла
13
Решение
Скачать архив тестов и решенийНазовем последовательность из 0 и 1, в которой никакие две единицы не стоят подряд, хорошей. Обозначим число хороших последовательностей длины k через Fk .
Попытаемся теперь выразить количество хороших последовательностей длины k через количества хороших последовательностей меньшей длины. Для этого рассмотрим, как можно построить хорошую последовательность длины k. Если последним символом этой последовательности выбрать 0, то в качестве предыдущих k-1 символов можно взять произвольную хорошую последовательность длины k-1. А таких последовательностей Fk-1 . Если же последним символом выбрать 1, то на (k-1)-ом месте 1 стоять не может и, значит, там стоит 0. Тогда в качестве первых k-2 символов можно взять любую хорошую последовательность длины k-2, а их количество Fk-2 . Таким образом, находим, что Fk = Fk-1 + Fk-2.
Получив эту рекуррентную формулу, нам остается задать первые два значения рассматриваемой последовательности (F0 = 1, F1 = 2), а затем в цикле последовательно вычислить числа F2 , F3 , ..., FN .
Можно вычислять числа Fk и не в цикле, а с помощью рекурсивной функции, основанной на выведенной нами формуле. Однако этот алгоритм неприемлем в данной задаче, т.к. он не сможет за разумное время закончить свою работу. (Заметьте: значение FN-2 эта функция будет вычислять 2 раза – при вычислении FN и FN-1 , FN-3 – 3 раза, а F2 – число раз, по порядку равное FN.)
Рекурсивную функцию, однако, использовать все же можно, если запоминать уже вычисленные значения (например, в статическом массиве) и никогда не вычислять их заново. Этот прием особенно эффективно применять в тех случаях, когда в процессе вычислений числа FN нам нужны не все предыдущие значения Fk , а только некоторые из них, причем заранее сложно указать, какие именно.
Отметим также, что при указанных в условии
задачи ограничениях необходимо
использовать длинную арифметику, т.к. число
F100 имеет в десятичной записи 21 цифру.
Замечание
Рекуррентная формула, полученная нами при
решении этой задачи, совпадает с формулой,
определяющей числа Фибоначчи. Это
объясняет тот факт, что FN совпадает с
(N+1)-м числом Фибоначчи.
