Составители:
Рубрика:
36
Из условия задачи следует, что через месяц будет две пары кроликов. Через два
месяца приплод даст только первая пара кроликов, и получится 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(12), нам придется последовательно вычислить F(3), F(4), … F(11), что
достаточно долго. А если нам необходимо было бы вычислить F(100), то это займет еще
больше времени. Попробуем выразить закономерность последовательности Фибоначчи с
помощью расчетной формулы (вместо неявного рекуррентного соотношения). Для этого
присвоим двоичный номер каждой паре кроликов. Единицам
соответствуют месяцы
появления на свет одной из пар “предков” данной пары (включая и исходную), а нулями –
все остальные месяцы. Например, последовательность 010010100010 устанавливает такую
“генеалогию” – сама пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца,
“дед” – в конце 5-го месяца, “прадед” – в конце второго месяца. Исходная пара
кроликов
зашифровывается при этом последовательностью 000000000000. в последовательности не
могут идти подряд две единицы, так как кролики приносят приплод только на второй месяц
после рождения.
Тем самым устанавливается связь между числами Фибоначчи и следующей
комбинаторной задачей: найти число n-последовательностей, состоящих из нулей и единиц,
в которых никакие две единицы не идут
подряд. Число таких последовательностей, в
которые входит ровно k единиц и n—k нулей, равно
k
kn
C
1+−
. Так как при этом должно
выполняться неравенство k<=n–k+1, то k изменяется от 0 до целой части числа (n+1)/2.
Применяя правило суммы, получаем F(n)=
p
pnnnn
CCCC
1
2
1
10
1
...
+−−+
++++
, где p – целая часть
числа (n+1)/2.
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
