Данная головоломка была придумана великим итальянским учёным-математиком Фибоначчи, который жил в XIII веке. Леонардо Пизанский (лат. Leonardo Pisano, около 1170 — 1250, Пиза), более известен миру под прозвищем Фибоначчи. Рекуррентная формула, которую получил автор задачи решая свою же задачу, считается первой рекуррентной формулой в истории математики. Также в этой задаче использованы немалоизвестные числа Фибоначчи.
Кролики Фибоначчи
Условия задачи
«В огороженное место помещены пара кроликов (самка и самец) 1 января. Эта пара кроликов начинает приносить потомство через месяц, то бишь с 1 февраля и даёт приплод ежемесячно по паре новых кроликов. Каждая новая пара кроликов становится половозрелой ровно через месяц и тоже начинает приносить ежемесячно по паре кроликов.
Вопрос: сколько всего кроликов будет через год, то бишь через 12 месяцев с начала размножения?»
Решение задачи
Для упрощения решения задачи обозначим через A пару зрелых кроликов, через B - пару новорожденных кроликов. Тогда процесс "размножения" может быть описан с помощью двух «переходов», которые описывают ежемесячные превращения кроликов в процессе размножения:
А=>AB
B=>A
А=>AB обозначает превращение одной взрослой пары в полноценную семью, то есть рождение ещё пары кроликов.
B=>A - переход молодняка в зрелый возраст.
- 1 месяц (январь) — А (1 пара молодняк)
- 2 месяц (февраль) — АВ (1 пара зрелая + 1 пара молодняк)
- 3 месяц (март) — АВА (2 пары зрелые + 1 пара молодняк)
- 4 месяц (апрель) — АВААВ (3 пары зрелые + 2 пары молодняк)
- 5 месяц (май) — ABAABABA (5 пар зрелые + 3 пары молодняк)
Внимательно изучив последовательности чисел А, В и А+В, видим закономерность: каждый член последовательности равен сумме двух предыдущих. Обозначим количество пар кроликов через С, а через d - порядковый номер месяца. Составляем формулу:
Cd = Cd-1 + Cd-2
Называется она — рекуррентная формула
С помощью полученной формулы рассчитываем количество кроликов по месяцам:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Это так называемые числа Фибоначчи — последовательность чисел, где каждое следующее число, начиная с третьего, получается сложением двух предыдущих чисел.
