Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 52 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

3. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
При решении многих комбинаторных задач часто пользуются мето-
дом сведения данной задачи к задаче, касающейся меньшего числа пред -
метов. Метод сведения к аналогичной задаче для меньшего числа пред-
метов называется методом рекуррентных соотношений. Пользуясь
рекуррентными соотношениями, можно свести задачу об
n
предметах к
задаче об
1
−
n
предметах, потом к задаче об
2
−
n
предметах и т.д. После-
довательно уменьшая число предметов, доходим до задачи, которую уже
легко решить.
В книге “ Liber Abaci” итальянский математик Фибоначчи среди
многих других задач привел следующую: пара кроликов приносит раз в
месяц приплод из двух крольчат (самки и самца ), причем новорожденные
крольчата через два месяца после рождения уже приносят приплод . Сколь-
ко кроликов появится через год , если в начале года была одна пара кроли-
ков?
Из условия задачи следует , что через месяц будет две пары кроли-
ков. Через два месяца приплод даст только первая пара кроликов, и полу -
чится 3 пары. А еще через месяц приплод дадут и исходная пара , и пара
кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар
кроликов.
Обозначим через )n(F количество пар кроликов по истечении
n
ме-
сяцев с начала года. Мы видим , что через
1
+
n
месяцев будет
)n(F
и еще
столько новорожденных пар кроликов, сколько было в конце месяца
1
−
n
,
то есть еще
)n(F 1
−
пар кроликов. Иными словами, имеет место рекур-
рентное соотношение
).n(F)n(F)n(F 11
−
+
=
+
Так как по условию 10
=
)(F и 21
=
)(F , то последовательно находим
845332
=
=
=
)(F,)(F,)(F и т . д .
Числа
)n(F
называются числами Фибоначчи .
3.1 Решение рекуррентных соотношений
Будем говорить, что рекуррентное соотношение имеет порядок
k
,
если оно позволяет выразить
(
)
knf
+
через
(
)
(
)
(
)
11
−
+
+
knf,,nf,nf K
.
Например,
(
)
(
)
(
)
(
)
11312
2
++−+=+ nfnfnfnf
— рекуррентное соотношение второго порядка , а
(
)
(
)
(
)
(
)
1263
+
+
+
=
+
nfnfnfnf
— рекуррентное соотношение третьего порядка . 
                3. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

      При решении многих комбинаторных задач часто пользуются мето-
дом сведения данной задачи к задаче, касающейся меньшего числа пред-
метов. Метод сведения к аналогичной задаче для меньшего числа пред-
метов называется методом рекуррентных соотношений. Пользуясь
рекуррентными соотношениями, можно свести задачу об n предметах к
задаче об n −1 предметах, потом к задаче об n −2 предметах и т.д. После-
довательно уменьшая число предметов, доходим до задачи, которую уже
легко решить.
      В книге “Liber Abaci” итальянский математик Фибоначчи среди
многих других задач привел следующую: пара кроликов приносит раз в
месяц приплод из двух крольчат (самки и самца), причем новорожденные
крольчата через два месяца после рождения уже приносят приплод. Сколь-
ко кроликов появится через год, если в начале года была одна пара кроли-
ков?
      Из условия задачи следует, что через месяц будет две пары кроли-
ков. Через два месяца приплод даст только первая пара кроликов, и полу-
чится 3 пары. А еще через месяц приплод дадут и исходная пара, и пара
кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар
кроликов.
      Обозначим через F( n ) количество пар кроликов по истечении n ме-
сяцев с начала года. Мы видим, что через n +1 месяцев будет F( n ) и еще
столько новорожденных пар кроликов, сколько было в конце месяца n −1,
то есть еще F( n −1) пар кроликов. Иными словами, имеет место рекур-
рентное соотношение
                          F( n +1) =F( n ) +F( n −1).
Так как по условию F( 0) =1 и F( 1) =2 , то последовательно находим
                    F( 2 ) =3 , F ( 3) =5 , F( 4 ) =8 и т.д.
      Числа F( n ) называются числами Фибоначчи.


                3.1 Решение рекуррентных соотношений

     Будем говорить, что рекуррентное соотношение имеет порядок k ,
если оно позволяет выразить f (n +k ) через f (n ), f (n +1), , f (n +k −1).
Например,
                  f (n +2 ) = f (n ) f (n +1) −3 f 2 (n +1) +1
— рекуррентное соотношение второго порядка, а
                     f (n +3) =6 f (n ) f (n +2 ) + f (n +1)
— рекуррентное соотношение третьего порядка.

Страницы