Кролики. Простая задача.

Dallas

Каждый год появляется новое поколение кроликов. Известно, что способность к размножению имеют только два последних поколения кроликов (кроме поколения, образовавшегося в текущем году). Поколение, появившееся в текущем году, способности к размножению (в этом году) не имеет. Бог наложил ограничение на эту популяцию кроликов: размножаться могут только пары кроликов из разных поколений, причем каждая пара только один раз, в результате сношения одной пары образуется ровно один кролик (он автоматически записывается в следующее поколение после поколений родителей). Взамен Бог снял всякие половые ограничения: теперь в паре размножающихся кроликов может быть любая комбинация половых принадлежностей, и вне зависимости от этой комбинации в результате появляется ровно один (!) кролик. Первые два поколения создал сам Бог, и они оба состоят из двух кроликов. Кролики по максимуму используют возможности, предоставленные Богом.
Обозначим F(n) двоичный логарифм числа кроликов n-ого поколения.
Доказать, что F(n+k) = F(n+1)F(k) + F(n)F(k-1).
Интересует наиболее короткие, простые и красивые решения

chel_1992

так ведь не получаются же числа фибоначчи...

Dallas

Почему? Если G(n) - число кроликов, то G(n) = G(n-1)*G(n-2 или F(n)=F(n-1)+F(n-2)

chel_1992

Поколение, появившееся в текущем году, способности к размножению (в этом году) не имеет

фразу не так поняла, думала через год только могут
а так - да

kachokslava

Может, поможет формула:
F(N)= a*(tau^N-tau^{-N})
?
a=1/sqrt(5)
tau - золотое сечение

DarkDimazzz

Только там (-tau)^{-N}

Dallas

Красивые решения есть в треде jerry. Меня просто интересует связь чисел Фибоначчи с кроликами и размножением. Я наивно полагал, что кто-нибудь раскритикует мой говнокреатив и напишет исходную версию.

Perce

Из книги "Liber abacci" Леонарда Фибоначчи, второе издание, 1228 г.
Сколько пар кроликов в один год от одной пары рождается?
Некто поместил пару кроликов в некоем месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова что через месяц пара кроликов производит на свет другую пару, а рождают кролики со второго месяца после своего рождения. Так как первая пара в первом месяце дает потомство, удвой, и в этом месяце окажутся 2 пары; из них одна пара, а именно первая, рождает и в следующем месяце, так что во втором месяце оказывается 3 пары; из них в следующем месяце 2 пары будут давать потомство, так что в третьем месяце родятся еще 2 пары кроликов, и число пар кроликов в этом месяце достигнет 5 из них в этом же месяце будут давать потомство 3 пары, и число пар кроликов в четвертом месяце достигнет 8; из них 5 пар произведут другие 5 пар, которые, сложенные с 8 парами, дадут в пятом месяце 13 пар; из них 5 пар, рожденных в этом месяце, не дадут в том же месяце потомство, а остальные 8 пар рождают, так что в шестом месяце оказывается 21 пара; сложенные с 13 парами, которые родятся в седьмом месяце, они дают 34 пары; сложенные с 21 парой, рожденной в восьмом месяце, они дают в этом месяце 55 пар; сложенные с 34 парами, рожденными в десятом месяце, они дают 89 пар; сложенные вновь с 55 парами, которые рождаются в десятом месяце, они дают в этом месяце 144 пары; снова сложенные с 89 парами, которые рождаются в одиннадцатом месяце, они дают в этом месяце 233 пары; сложенные вновь с 144 парами, рожденными в последнем месяце, они дают 377 пар; столько пар привела первая пара в данном месте к концу одного года. Действительно, на этих полях ты можешь увидеть, как мы это делаем; именно, мы складываем первое число со вторым, т.е. 1 и 2; и второе с третьим; и третье с четвертым; и четвертое с пятым; и так одно за другим, пока не сложим десятое с одиннадцатым, т. е. 144 с 233; и мы получим общее число упомянутых кроликов, т. е. 377; и так можно делать по порядку до бесконечного числа месяцев.

Dallas

спасибо
Оставить комментарий
Имя или ник:
Комментарий: