рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Задача Фибоначчи

Задача Фибоначчи - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Итальянский Математик Леонардо Фибоначчи Жил В 13 Столетии И Одним Из Первых ...

Итальянский математик Леонардо Фибоначчи жил в 13 столетии и одним из первых в Европе стал использовать арабские (индийские) цифры. Он придумал несколько искусственную задачу о кроликах, которых выращивают на ферме, причем все они считаются самками, самцы игнорируются. Кролики начинают размножаться после того, как им исполняется два месяца, а потом каждый месяц рожают по кролику. Кролики никогда не умирают.

Нужно определить, сколько кроликов будет на ферме через n месяцев, если в начальный момент времени был только один новорожденный кролик.

Очевидно, что фермер имеет одного кролика в первый месяц и одного кролика – во второй месяц. На третий месяц будет уже два кролика, на четвертый – три и т.д. Обозначим количество кроликов в n месяце как . Таким образом, , , , , , …

Можно построить алгоритм, позволяющий найти при любом n.

Согласно условию задачи общее количество кроликов в n+1 месяце раскладывается на три составляющие:

· одномесячные кролики, не способные к размножению, в количестве

;

· кролики, способные к размножению, в количестве ;

· новорожденные кролики, их количество также равно .

Таким образом, получим

. (8.1)

Формула (8.1) позволяет вычислить ряд чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …

Числа в данной последовательности называются числами Фибоначчи.

Если принять и , то с помощью формулы (8.1) можно определить все остальные числа Фибоначчи. Формула (8.1) называется рекуррентной формулой (recurrence – «возвращение» на латыни).

Пример 8.1.Предположим, что имеется лестница в n ступенек. Мы можем подниматься по ней с шагом в одну ступеньку, либо – с шагом в две ступеньки. Сколько существует комбинаций различных способов подъема?

Если n = 1, имеется только один вариант решения задачи. Для n = 2 существует 2 варианта: два единичных шага либо один двойной. Для n = 3 существует 3 варианта: три единичных шага, либо один единичный и один двойной, либо один двойной и один единичный.

В следующем случае n = 4, имеем 5 возможностей (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2).

Для того чтобы ответить на заданный вопрос при произвольном n, обозначим количество вариантов как , и попробуем определить по известным и . Если мы стартуем с единичного шага, то имеем комбинаций для оставшихся n ступенек. Если стартуем с двойного шага, то имеем комбинаций для оставшихся n–1 ступенек. Общее количество вариантов для n+1 ступенек равно

. (8.2)

Полученная формула как близнец напоминает формулу (8.1). Тем не менее, это не позволяет отождествлять количество комбинаций с числами Фибоначчи . Мы видим, например, что , но . Однако имеет место следующая зависимость:

.

Это справедливо для n = 1, 2, и также справедливо для каждого n. Числа Фибоначчи и количество комбинаций вычисляются по одной и той же формуле, однако начальные значения , и , у них различаются.

Пример 8.2.Этотпример имеет практическое значение для задач помехоустойчивого кодирования. Найдем число всех двоичных слов длины n, не содержащих несколько нулей подряд. Обозначим это число через . Очевидно, , а слова длины 2, удовлетворяющие нашему ограничению, таковы: 10, 01, 11, т.е. . Пусть – такое слово из n символов. Если символ , то может быть произвольным ()-буквенным словом, не содержащим несколько нулей подряд. Значит, число слов с единицей на конце равно .

Если же символ , то обязательно , а первые символа могут быть произвольными с учетом рассматриваемых ограничений. Следовательно, имеется слов длины n с нулем на конце. Таким образом, общее число интересующих нас слов равно

.

С учетом того, что и , полученная последовательность чисел – это числа Фибоначчи.

Пример 8.3.В примере 7.6 мы нашли, что число двоичных слов постоянного веса t (и длиной k) равно . Теперь найдем число двоичных слов постоянного веса t, не содержащих несколько нулей подряд.

Рассуждать можно так. Пусть число нулей в рассматриваемых словах. В любом слове имеется промежутков между ближайшими нулями, в каждом из которых находится одна или несколько единиц. Предполагается, что . В противном случае нет ни одного слова без рядом стоящих нулей.

Если из каждого промежутка удалить ровно по одной единице, то получим слово длины , содержащее нулей. Любое такое слово может быть получено указанным образом из некоторого (и притом только одного) k-буквенного слова, содержащего нулей, никакие два из которых не стоят рядом. Значит, искомое число совпадает с числом всех слов длины , содержащих ровно нулей, т.е. равно .

Пример 8.4.Докажем,что сумма равна числам Фибоначчи для любого целого . Символ обозначает наименьшее целое число, большее или равное . Например, если , то ; а если , то . По-английски эту операцию называют ceil («потолок»). Также встречается символ , который обозначает наибольшее целое число, меньшее или равное . По-английски эту операцию называют floor («пол»).

Если , то . Если , то . Если , то .

Таким образом, для рассмотренных случаев сумма действительно равна числам Фибоначчи. Теперь приведем доказательство для общего случая. Поскольку числа Фибоначчи можно получить с помощью рекуррентного уравнения (8.1), то должно выполняться равенство:

.

И оно действительно выполняется:

Здесь мы использовали полученную ранее формулу (4.4): .

 

 

– Конец работы –

Эта тема принадлежит разделу:

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ... Литература...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Задача Фибоначчи

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Счетные и несчетные числовые множества
Теория множеств появилась в конце 19 века благодаря работам немецкого математика Георга Кантора (1845-1918). Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики.

Позиционные и непозиционные системы
Системой счисления называется метод записи чисел в виде комбинаций графических символов. Число – это некоторая абстрактная сущность для описания количества, а цифры – знаки, ис

Десятичная система
Существуют различные позиционные системы исчисления, отличающиеся между собой количеством используемых знаков. Чтобы различать числа в разных системах исчисления, в конце числа ставят индекс – симв

Двоичная система
Двоичная (бинарная) система счисления является самой простой из всех позиционных систем. Она содержит только два символа 0 и 1, и используется в компьютерной технике благодаря своей простоте и высо

Код Грея
Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является о

Троичная система счисления
Троичная система счисления– позиционная система счисления с целочисленным основанием равным 3. Она существует в двух вариантах: несимметричная и симметричная трои

Восьмеричная и шестнадцатеричная системы счисления
Позиционную систему счисления можно построить по любому основанию. Однако наибольшее практическое значение имеют: двоичная, десятичная, восьмеричная и шестнадцатеричная. Причем, последние две испол

Канторово множество
Математика изобилует парадоксальными объектами. Одним из них является канторово множество. Оно описывается следующим образом. Рассмотрим единичный отрезок, показанный на рис. 3.1. Удалим из

Ковер Серпинского и снежинка Коха
Ковер Серпинского получается из единичного квадрата удалением средней части (1/3, 2/3)*(1/3, 2/3), затем удалением из каждого квадрата (i/3, i+1/3)*(j/3, j+1/3) с

Стохастические фракталы
Стохастические фракталы получаются в том случае, если в итерационном процессе случайным образом менять какие-либо параметры. При этом получаются объекты, очень похожие на природные – несимметричные

Энтропийная размерность
Пусть X – компактное пространство с метрикой d. Тогда множество называется r-плотным

Фрактал Мандельброта
Существует бесконечное множество различных фракталов. Один из них носит имя Мандельброта. Фрактал Мандельброта – это множество точек на комплексной плоскости, для которых итеративная последо

Виды доказательства
Древние греки сформулировали основные правила логического доказательства. Они различали два вида доказательства: дедукцию и индукцию. Дедукция – это доказательство от общего

Переменные и формулы в исчислении высказываний
Переменная, значениями которой являются высказывания, называется пропозициональной переменной. Понятие пропозициональной формулы вводится по индукции

Булевы функции
Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества

Предикаты
Применяемые в математике высказывания обычно представляют собой описание свойств каких-либо математических объектов или описаний отношений, существующих между этими объектами. Для анализа закономер

Семантика исчисления предикатов
Исчисление предикатов (так же как и исчисление высказываний) являются, прежде всего, языками. И эти языки можно применять не только в математике. Используя их слова, фразы и предложения, мы можем п

Равно(плюс(два, три), пять)
«Некоторые люди любят грибы» X(личность(Х)

Правила логического вывода
Возможность логически выводить новые правильные выражения из набора истинных утверждений – это важное свойство исчисления предикатов. Логически выведенные выражения корректны, потому что они совмес

Правило резолюции
Правило резолюции (лат. resolutio – решение ): если выражения PA

Парадокс Рассела
Задание множеств характеристическим предикатом может приводить к противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента. Рассмотрим множество всех множ

Сравнение множеств
Множество содержится в множестве

Свойства операций над множествами
Пусть задан универсум . Тогда

Проблема континуума
Кантор был первым, кто стал рассматривать мощности (кардинальные числа) бесконечных множеств. Мощность счетного множества он обозначил древнееврейской буквой «алеф» с нулевым индексом:

Сумма нечетных чисел
Математическая индукция играет огромную роль в дискретной математике (именно в силу ее дискретного характера). Полученные этим методом доказательства в данной области математики почти столь же наде

Сумма натуральных чисел
А теперь используем метод индукции для доказательства того, что сумма первых n положительных целых чисел равна

Снова считаем подмножества
Доказывая теорему 5.1. мы неявно пользовались методом математической индукции. Теперь пришло время применить его явно. Итак, мы подозреваем, что число всех подмножеств множества из n элемент

Биномиальные коэффициенты
Слово бином означает выражение, состоящее из двух членов, например: x + y. Бином является частным случаем полинома. Биномом Ньютона наз

Треугольник Паскаля
Французский математик Блез Паскаль (1623-1662) составил таблицу из биномиальных коэффициентов. Она получилась треугольной, поскольку с увеличением степени бинома количество коэффициентов также увел

Бином Ньютона для дробных и отрицательных показателей
Формула бинома Ньютона (6.1) для целых положительных показателей была известна задолго до Исаака Ньютона (1643-1727), но им в 1676 году была указана возможность распростране

Гамма-функция
Биномиальная теорема определяет биномиальные коэффициенты через факториалы чисел n и k:

Размещения без повторений
Общее число размещений без повторений из n элементов по k элементов обычно обозначается так:

Сочетания без повторений
Число различных сочетаний без повторений обычно обозначается так: . Или так

Размещения с повторением
Если мы выбираем из множества n элементов размещения с повторениями k элементов, то в данном случае k может превосходить n. Теорема 7.3. Об

Сочетания с повторением
Теорема 7.4. Общее число сочетаний с повторениями k элементов, взятых из совокупности n различных элементов, равно

Формула Стирлинга
Рассматривая комбинаторные задачи, мы часто сталкиваемся с факториалами. Факториал – это очень быстро растущая функция, она растет быстрее экспоненты. При достаточно больших n (n >

Подстановки
Взаимно однозначная функция называется подстановкой на

Сумма чисел Фибоначчи
Определим сумму первых n чисел Фибоначчи. 0 = 0, 0+1 = 1, 0+1+1 = 2, 0+1+1+2 = 4, 0+1+1+2+3 = 7, 0+1+1+2+3+5 = 12, 0+1+1+2+3+5+

Формула для чисел Фибоначчи
Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле .

Простые числа
Все натуральные числа, большие единицы, распадаются на два класса. К первому относятся числа, имеющие ровно два натуральных делителя, единицу и самого себя, ко второму – все остальные. Числа первог

Алфавитное кодирование
Кодирование может сопоставлять код всему сообщению из множества

Помехоустойчивое кодирование
Пусть имеется канал связи C, содержащий источник помех: , где S – множес

Модулярная арифметика
В этом разделе все числа – целые. Говорят, что число a сравнимо по модулю n с числом b (обозначение

Шифрование с открытым ключом
Шифрование с открытым ключом производится следующим образом. 1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги