Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.)

При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").

Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.

Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.

Пусть Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru - число пар кроликов в популяции по прошествии Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru месяцев, и пусть эта популяция состоит из Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru пар приплода и Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru "старых" пар, то есть Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Таким образом, в очередном месяце произойдут следующие события: Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru Старая популяция в Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru -й момент увеличится на число родившихся в момент времени Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru . Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru Каждая старая пара в момент времени Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru производит пару приплода в момент времени Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru В последующий месяц эта картина повторяется: Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Объединяя эти равенства, получим следующее рекуррентное соотношение:

Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru (иногда Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru ).

Рассмотрим эту задачу немного иначе.

Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru количество пар кроликов по истечении Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru месяцев с начала года. Ясно, что через Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru месяцев будут эти Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru пар и еще столько новорожденных пар кроликов, сколько было в конце месяца

Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru , то есть еще Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru пар кроликов. Иными словами, имеет место рекуррентное соотношение Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Так как, по условию, Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru и Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru , то последовательно находим Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru и т.д.

В частности, Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Числа Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru .

Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

Одномерные массивы и алгоритмы работы с ними (нахождение максимального и минимального элементов, суммирование элементов, вставка и удаление элементов, перестановка элементов местами и т.д.)

Массив это структура данных, представленная в виде группы ячеек одного типа, объединенных под одним единым именем. Массивы используются для обработки большого количества однотипных данных. Имя массива является указателем, что такое указатели расскажу немного позже. Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого типа. Массивы могут иметь как одно, так и более одного измерений. В зависимости от количества измерений массивы делятся на одномерные массивы, двумерные массивы, трёхмерные массивы и так далее до n-мерного массива. Чаще всего в программировании используются одномерные и двумерные массивы, поэтому мы рассмотрим только эти массивы.

Одномерные массивы в С++:

Одномерный массив - массив, с одним параметром, характеризующим количество элементов одномерного массива. Фактически одномерный массив - это массив, у которого может быть только одна строка, и n-е количество столбцов. Столбцы в одномерном массиве - это элементы массива. На рисунке 1 показана структура целочисленного одномерного массива a. Размер этого массива - 16 ячеек.

Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.) - student2.ru

Заметьте, что максимальный индекс одномерного массива a равен 15, но размер массива 16 ячеек, потому что нумерация ячеек массива всегда начинается с 0. Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к каждой ячейке массива и выполнять какие-либо действия над ней (ячейкой).

Наши рекомендации