Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




 

Рассмотрим следующую задачу. Имеются последовательности длины 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; Просмотров: 654; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.