Рекуррентные соотношения. Рассмотрим следующую задачу

Рассмотрим следующую задачу. Имеются последовательности длины N, состоящие из 0 и 1. Требуется по заданному числу N (1 < N < 40) определить количество таких последовательностей, в которых никакие две единицы не стоят рядом.

Казалось бы, задача очевидна. При заданном N имеется 2^N последовательностей из нулей и единиц. Действительно, в каждой позиции может находиться два значения, а отдельные разряды независимы. Можно перечислять последовательности и проверять с помощью стандартных функций, имеются ли две единицы рядом. Останется из 2^N последовательностей вычесть число последовательностей с двумя единицами подряд.

Снова обратим внимание на размерность. При N=30 значение 2^N превышает миллиард. А если N еще больше?

Рассмотрим другой подход к решению задачи. Обозначим через F(N) количество последовательностей с заданным свойством. Возможны два случая:

на месте N стоит 0;

на месте N стоит 1.

В первом случае в позициях от 1 до N-1 может находиться любая последовательность без двух единиц рядом, то есть общее число последовательностей составляет F(N-1).

Во втором случае на месте N-1 обязан находиться 0, иначе последовательность закончится двумя единицами подряд. А вот в позициях от 1 до N-2 может находиться любая последовательность без двух единиц рядом. Таким образом, общее число искомых последовательностей составляет F(N-2).

В результате получаем формулу F(N)=F(N-1)+F(N-2), совпадающую с правилом вычисления чисел Фибоначчи. Значение функции F на любом шаге определяется через ее значения на предыдущих шагах. Такие формулы называются рекуррентными.

Легко установить, что F(1)=2, F(2)=3. Поэтому F(3)=F(2)+F(1)=5, F(4)=F(3)+F(2)=8, F(5)=F(4)+F(3)=13 и т. д.

Сейчас вычислений немного, но есть другая трудность. Последовательность Фибоначчи быстро растет, а результатом должно быть целое число, которое при больших N невозможно представить точно стандартными целочисленными типами данных. В таких случаях используют собственные типы данных и процедуры работы с ними. Их в совокупности называют длинной арифметикой. Мы рассмотрим эти проблемы ниже.

Сформулируем еще одну похожую задачу.

Сообщение. В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2,..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Ввод из файла INPUT.TXT. В первой строке содержится последовательность цифр.

Вывод в файл OUTPUT.TXT. Вывести одно число.

Ограничения: цифр не более 100, время 1 с.

Пример

Ввод

Вывод

Обозначим через F(N) количество сообщений, которые можно сформировать из первых N цифр. Попытаемся выразить F(N+1)через значения этой функции на предыдущих шагах. Рассмотрим два случая:

цифры на местах N и N+1 образуют двухзначное число, большее 33;

цифры на местах N и N+1 образуют двухзначное число, не превышающее 33.

В первом случае любое сообщение, зашифрованное первыми N цифрами, может быть дополнено буквой, код которой содержится в позиции N+1. В то же время последние две цифры не могут кодировать какую-либо букву. Значит, в этом случаеF(N+1)=F(N).

Во втором случае помимо этого любое сообщение, представленное первыми N-1 цифрами, может быть дополнено буквой, код которой содержится в позициях N и N+1. В этом случае F(N+1)= F(N)+ F(N-1).

Очевидно, F(1)=1. Правильно считать, что F(0)=1 – пустое сообщение, которое может дополняться. Здесь потребуется использование длинной арифметики.