Фибоначчи кролики
Давайте посмотрим, как растёт количество кроликов в первые полгода:
Месяц 1. Одна пара молодых кроликов.
Месяц 2. По‑прежнему одна исходная пара. Кролики ещё не достигли детородного возраста.
Месяц 3. Две пары: исходная, достигшая детородного возраста + пара молодых кроликов, которых она породила.
Месяц 4. Три пары: одна исходная пара + одна пара кроликов, которую она породила в начале месяца + одна пара кроликов, которые появились на свет в третьем месяце, но ещё не достигли половой зрелости.
Месяц 5. Пять пар: одна исходная пара + одна пара, родившаяся в третьем месяце и достигшая детородного возраста + две новые пары, которым они дали жизнь + одна пара, которая появилась на свет в четвёртом месяце, но пока не достигла зрелости.
Месяц 6. Восемь пар: пять пар, живших в прошлом месяце + три новорождённые пары. И так далее.
Чтобы было понятнее, запишем полученные данные в таблицу:
Если внимательно рассмотреть таблицу, можно выявить следующую закономерность. Каждый раз количество кроликов, имеющихся в n‑м месяце, равно числу кроликов в (n − 1)-м, предыдущем месяце, суммированному с числом только что родившихся кроликов. Их количество, в свою очередь, равно общему числу животных по состоянию на (n − 2)-й месяц (который был два месяца назад). Отсюда можно вывести формулу:
Fn = Fn‑1+ Fn‑2,
где Fn — общее количество пар кроликов в n‑й месяц, Fn‑1 — общее количество пар кроликов в предыдущий месяц, а Fn‑2 — общее количество пар кроликов два месяца назад.
Подсчитаем по ней количество животных в последующие месяцы:
Месяц 7. 8 + 5 = 13.
Месяц 8. 13 + 8 = 21.
Месяц 9. 21 + 13 = 34.
Месяц 10. 34 +21 = 55.
Глава 11. Последовательности 258 Задача Фибоначчи о кроликах Пусть в огороженном месте имеется пара кроликов (самка и са- мец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорождённая пара кроликов стано- вится зрелой уже через месяц и затем через месяц даёт жизнь новой паре кроликов. Вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения? Подсчётами можно получить, что число пар в каждый из двенад цати последующих месяцев будет равно: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … . Этот ряд чисел известен как ряд Фибоначчи , а сами числа — числа Фибоначчи , обозначаются как { F n }. Фибоначчи получил, что в конце n -го месяца количество пар кро ликов будет равно количеству пар в предыдущем месяце плюс коли чество новорождённых пар, которых будет столько же, сколько пар было два месяца назад. Говоря проще, число пар кроликов создаёт ряд, каждый член в котором — сумма двух предыдущих. Таким образом: F n = F n –2 + F n –1 , где п целое число, большее 2. Эта формула и была впоследствии названа рекуррентной . Последовательность чисел Фибоначчи связана с золотым сечени- ем — соотношением двух величин а и b , где b > a , когда справедли во равенство b a = a + b a . Отношение b a равно 1+ √ 5 2 или приближённо 1,62. В процентном округлённом значении золотое сечение — это де ление некой величины в отношении примерно 62% и 38%. Под «правилом золотого сечения» в архитектуре и искусстве обыч но понимаются композиции, содержащие пропорции, близкие к зо лотому сечению. При изучении архитектуры пирамиды Хеопса учё ные пришли к выводу, что древнеегипетские строители использовали соотношение золотого сечения при создании пирамиды. Последовательность чисел Фибоначчи связана с процессом распо ложения листьев — филлотаксисом . Например, семечки в соцветии подсолнуха упорядочены в два ряда спиралей, один из которых идёт по часовой стрелке, другой против. Количество семян в каждом слу чае равно 34 и 55.
Страница: 1 2 3 4 5 6 7
|
Содержание Задача 35468 |
|
Сложность: 3 Классы: 8,9 |
Найдите количество слов длины 10, состоящих только из букв «а» и «б» и не содержащих в записи двух букв «б» подряд.
| Прислать комментарий | Решение |
Задача 60560 |
|
Сложность: 3 Классы: 8,9 |
Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод?
| Прислать комментарий | Решение |
Задача 60564 |
|
Сложность: 3 Классы: 8,9,10,11 |
Тождество Кассини. Докажите равенство Fn + 1Fn — 1 — Fn2 = (- 1)n (n > 0).
Будет ли тождество Кассини справедливо для всех целых n?
| Прислать комментарий | Решение |
Задача 104123 |
|
Сложность: 3 Классы: 7,8,9 |
а) Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх либо на одну ступеньку, либо на две ступеньки. Сколькими способами Леша может подняться по лестнице?
б) При спуске с той же лестницы Леша перепрыгивает через некоторые ступеньки (может даже через все 10). Сколькими способами он может спуститься по этой лестнице?
| Прислать комментарий | Решение |
Задача 60576 |
|
Сложность: 3 Классы: 8,9,10,11 |
Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно Fn + 2. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.
Постановка задачи
- F 1 = 1 {\displaystyle F_{1}=1}
- F 2 = 1 {\displaystyle F_{2}=1}
- F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} , n > 2
Рекурсивное решение
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как Φ n {\displaystyle \Phi ^{n}} , где Φ {\displaystyle \Phi } — золотое сечение.
Приведем C++ — код этой функции:
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк. //Функция возвращает n-e число Фибоначчи по данному n. int fib(unsigned int n) { if (n < 2) return n; return fib(n — 1) + fib(n — 2); }
Решение с помощью динамического программирования
Код функции, реализующий восходящее ДП:
//возвращает n-e число Фибоначчи int fib_n(int n) { if (n <= 2) return 1; std::vector<int> dp(n + 1); dp = 1; dp = 1; for (int i = 3; i <= n; i++) { dp = dp + dp; } return dp; }
Код функции на Python, возвращающий последовательность чисел с помощью списка:
def fibo(n): f = for i in range(2, n + 1): f.append(f + f) print(f) n = 10 fibo(n) #
Элегантное решение
Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.
Приведем С++ — код:
//возвращает n-е число Фибоначчи int fib_n(int n) { //F(n) int x = 1; //F(n-1) int y = 0; for (int i = 0; i < n; i++) { x += y; y = x — y; } return y; }
Приведем Python — код:
# возвращает последовательность чисел def fibo(n): a = 0 b = 1 print(a, b, end=’ ‘) for i in range(2, n + 1): c = a + b a, b = b, c print(c, end=’ ‘) n = 10 fibo(n) # 0 1 1 2 3 5 8 13 21 34 55
Решение быстрым возведением матрицы в степень
Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем тождестве:
( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) . {\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}
Для удобства обозначим матрицу, возводимую в степень, как P:
P = ( 1 1 1 0 ) . {\displaystyle P={\begin{pmatrix}1&1\\1&0\end{pmatrix}}.}
Ниже этот алгоритм реализован на языке С. Будем считать, что:
A = ( a b c d ) {\displaystyle A={\begin{pmatrix}a&b\\c&d\end{pmatrix}}} — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей P {\displaystyle P} . R = ( r c r d ) {\displaystyle R={\begin{pmatrix}rc&rd\end{pmatrix}}} — вектор результатов (вторая строка матрицы P n {\displaystyle P^{n}} ), инициализируется как вторая строка единичной матрицы. //возвращает n-е число Фибоначчи int fib(int n) { int a = 1, ta, b = 1, tb, c = 1, rc = 0, tc, d = 0, rd = 1; while (n) { if (n & 1) // Если степень нечетная { // Умножаем вектор R на матрицу A tc = rc; rc = rc*a + rd*c; rd = tc*b + rd*d; } // Умножаем матрицу A на саму себя ta = a; tb = b; tc = c; a = a*a + b*c; b = ta*b + b*d; c = c*ta + d*c; d = tc*tb+ d*d; n >>= 1; // Уменьшаем степень вдвое } return rc; }
То же на языке Python:
1 #возвращает n-е число Фибоначчи 2 def fib(n): 3 a = 1 4 b = 1 5 c = 1 6 rc = 0 7 d = 0 8 rd = 1 9 while n>0: 10 if n%2!=0: #Если степень нечетная 11 # Умножаем вектор R на матрицу A 12 tc = rc 13 rc = rc*a + rd*c 14 rd = tc*b + rd*d 15 #Умножаем матрицу A на саму себя 16 ta = a 17 tb = b 18 tc = c; 19 a = a*a + b*c 20 b = ta*b + b*d 21 c = c*ta + d*c 22 d = tc*tb+ d*d 23 n >>= 1 #Уменьшаем степень вдвое 24 return rc