Комбинаторные алгоритмы для программистов



             

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


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

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

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

Пусть

F_n
- число пар кроликов в популяции по прошествии
n
месяцев, и пусть эта популяция состоит из
N_n
пар приплода и
O_n
"старых" пар, то есть
F_n = N_n + O_n
. Таким образом, в очередном месяце произойдут следующие события:
O_{n + 1} = O_n + N_n = F_n
. Старая популяция в
(n + 1)
-й момент увеличится на число родившихся в момент времени
n
.
N_{n + 1} = O_n
. Каждая старая пара в момент времени
n
производит пару приплода в момент времени
(n + 1)
. В последующий месяц эта картина повторяется:
O_{n+2}=O_{n+1}+N_{n+1}=F_{n+1},

N_{n+2} = O_{n + 1}

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

F_{n+2}=O_{n+2}+N_{n+2}=F_{n+1}+O_{n+1},

F_{n+2}=F_{n+1}+F_n

(7.1)

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

F_0 = 0,F_1 = 1
(иногда
F_0 = F_1 = 1
).

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

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары.


Содержание  Назад  Вперед