Рекуррентные соотношения

Рассмотрим следующую задачу. Имеются последовательности длины 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. В первой строке содержится последовательность, содержащая не более 100 цифр.

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

Дата добавления: 2014-01-11