ФИБОНАЧЧИ И ЕГО УДИВИТЕЛЬНАЯ ЗАДАЧКА
Фибоначчи задал такие условия: существует пара новорожденных кроликов (самец и самка) такой интересной породы, что они регулярно (начиная со второго месяца) производят потомство – всегда одну новую пару кроликов. Тоже, как можно догадаться, самца и самку.
Эти условные кролики помещены в замкнутое пространство и с увлечением размножаются. Оговаривается также, что ни один кролик не умирает от какой-нибудь загадочной кроличьей болезни.
Надо вычислить, сколько кроликов мы получим через год.
В начале 1 месяца у нас 1 пара кроликов. В конце месяца они спариваются.
Второй месяц – у нас уже 2 пары кроликов (у пара – родители + 1 пара – их потомство).
Третий месяц: Первая пара рождает новую пару, вторая пара спаривается. Итого – 3 пары кроликов.
Четвертый месяц: Первая пара рождает новую пару, вторая пара времени не теряет и тоже рождает новую пару, третья пара пока только спаривается. Итого – 5 пар кроликов (Рис.2)
Рис.2 Задача про зайцев.
Число кроликов в n-ый месяц = число пар кроликов из предыдущего месяца + число новорожденных пар (их столько же, сколько пар кроликов было за 2 месяца до настоящего момента). И все это описывается формулой, которую мы уже привели выше: Fn = Fn-1 + Fn-2.
Таким образом, получаем рекуррентную (пояснение о рекурсии – ниже) числовую последовательность. В которой каждое следующее число равно сумме двух предыдущих:
1. 1 + 1 = 2
2. 2 + 1 = 3
3. 3 + 2 = 5
|
|
|
4. 5 + 3 = 8
5. 8 + 5 = 13
6. 13 + 8 = 21
7. 21 + 13 = 34
8. 34 + 21 = 55
9. 55 + 34 = 89
10. 89 + 55 = 144
11. 144 + 89 = 233
12. 233+ 144 = 377 <…>
Продолжать последовательность можно долго: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 <…>. Но поскольку мы задали конкретный срок – год, нас интересует результат, полученный на 12-ом «ходу». Т.е. 13-ый член последовательности: 377.
Ответ в задаче: 377 кроликов будет получено при соблюдении всех заявленных условий.
ЗАДАЧИ НА КОМБИНАТОРИКУ
Числа Фибоначчи находят широкое применение при решении задач по комбинаторике.
Комбинаторика – это раздел математики, который занимается исследованием выборки некого заданного числа элементов из обозначенного множества, перечислением. Давайте рассмотрим примеры задач по комбинаторике, рассчитанных на уровень старшей школы.
Задача №1:
Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх либо на одну ступеньку, либо на две ступеньки. Сколькими способами Леша может подняться по лестнице?
Решение:
Число способов, которыми Леша может подняться на лестницу из n ступенек, обозначим аn. Отсюда следует, что a1 = 1, a2 = 2 (ведь Леша прыгает либо на одну, либо через две ступеньки).
|
|
|
Оговорено также, что Леша прыгает по лестнице из n > 2 ступенек. Предположим, с первого раза он прыгнул на две ступеньки. Значит, по условию задачи, ему нужно запрыгнуть еще на n – 2 ступеньки. Тогда количество способов закончить подъем описывается как an–2. А если считать, что в первый раз Леша прыгнул только на одну ступеньку, тогда количество способов закончить подъем опишем как an–1.
Отсюда получаем такое равенство: an = an–1 + an–2 (выглядит знакомо, не правда ли?).
Раз мы знаем a1 и a2 и помним, что ступенек по условию задачи 10, вычисли по порядку все аn: a3 = 3, a4 = 5, a5 = 8, a6 = 13, a7 = 21, a8 = 34, a9 = 55, a10 = 89.
Ответ: 89 способов.
Задача №2:
Требуется найти количество слов длиной в 10 букв, которые состоят только из букв «а» и «б» и не должны содержать две буквы «б» подряд.
Решение:
Обозначим за an количество слов длиной в n букв, которые состоят только из букв «а» и «б» и не содержат двух букв «б» подряд. Значит, a1 = 2, a2 = 3.
В последовательности a1, a2, <…>, an мы выразим каждый следующий ее член через предыдущие. Следовательно, количество слов длиной в n букв, которые к тому же не содержат удвоенной буквы «б» и начинаются с буквы «а», это an–1. А если слово длиной в n букв начинается с буквы «б», логично, что следующая буква в таком слове – «а» (ведь двух «б» быть не может по условию задачи). Следовательно, количество слов длиной в n букв в этом случае обозначим как an–2 . И в первом, и во втором случае далее может следовать любое слово (длиной в n – 1 и n – 2 букв соответственно) без удвоенных «б».
|
|
|
Мы смогли обосновать, почему an = an–1 + an–2.
Вычислим теперь a3 = a2 + a1 = 3 + 2 = 5, a4 = a3 + a2 = 5 + 3 = 8, <…>, a10 = a9 + a8 = 144. И получим знакомую нам последовательность Фибоначчи.
Ответ: 144.
1.6 ЗОЛОТОЕ СЕЧЕНИЕ
Золотое сечение – деление целого (например, отрезка) на такие части, которые соотносятся по следующему принципу: большая часть относится к меньшей так же, как и вся величина (например, сумма двух отрезков) к большей части. Первое упоминание о золотом сечении можно встретить у Евклида в его трактате «Начала» (примерно 300 лет до н.э.). В контексте построения правильного прямоугольника. Привычный нам термин в 1835 году ввел в оборот немецкий математик Мартин Ом. Если описывать золотое сечение приблизительно, оно представляет собой пропорциональное деление на две неравных части: примерно 62% и 38% (Рис.3). В числовом выражении золотое сечение представляет собой число 1,6180339887.Золотое сечение находит практическое применение в изобразительном искусстве (картины Леонардо да Винчи и других живописцев Ренессанса), архитектуре, кинематографе («Броненосец «Потемкин» С. Эзенштейна) и других областях. Долгое время считалось, что золотое сечение – наиболее эстетичная пропорция. Такое мнение популярно и сегодня. Хотя по результатам исследований визуально большинство людей не воспринимают такую пропорцию наиболее удачным вариантом и считают слишком вытянутой (непропорциональной).
|
|
|
Рис.3 Пропорции золотого сечения
· Длина отрезка с = 1, а = 0,618, b = 0,382.
· Отношение с к а = 1, 618.
· Отношение с к b = 2,618
А теперь вернемся к числам Фибоначчи. Возьмем два следующих друг за другом члена из его последовательности. Разделим большее число на меньшее и получим приблизительно 1,618. А теперь задействуем то же большее число и следующий за ним член ряда (т.е. еще большее число) – их отношение рано 0,618.
Вот пример: 144, 233, 377.
233/144 = 1,618 и 233/377 = 0,618
Кстати, если вы попробуете проделать тот же эксперимент с числами из начала последовательности (например, 2, 3, 5), ничего не получится. Ну, почти. Правило золотого сечения почти не соблюдается для начала последовательности. Но зато по мере продвижения вдоль ряда и возрастания чисел работает отлично.И для того, чтобы вычислить весь ряд чисел Фибоначчи, достаточно знать три члена последовательности, идущих друг за другом. Можете убедиться в этом сами!
Дата добавления: 2021-04-15; просмотров: 681; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!