ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102778
Темы:    [ Динамическое программирование: классические задачи ]
[ Длинная арифметика как инструмент ]
Сложность: 3
Классы:
Название задачи: Последовательности из 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)-м числом Фибоначчи.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 1
Название Динамическое программирование
Задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .