Почему числа Фибоначчи значительны в информатике?

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

Они также существуют в области компьютерных наук в других местах; в удивительно эффективных структурах данных и алгоритмах, основанных на последовательности.

На ум приходят два основных примера:

кучи Фибоначчи, которые лучше амортизированное время работы, чем биномиальное отвалы.
поиск Фибоначчи, который делится O (log N) с двоичным поиск по упорядоченному массиву.

Есть ли какое-то особое свойство этих чисел, которое дает им преимущество перед другими числовыми последовательностями? Это пространственное качество? Какие еще возможные приложения могли бы иметь?

Мне кажется странным, поскольку в других рекурсивных проблемах есть много естественных числовых последовательностей, но я никогда не видел Catalan куча.

Ответ 1

Числа Фибоначчи имеют всевозможные действительно хорошие математические свойства, которые делают их превосходными в информатике. Вот несколько:

Они растут экспоненциально быстро. Одна интересная структура данных, в которой возникает серия Фибоначчи, - это дерево AVL, форма самобалансирующегося двоичного дерева. Интуиция, стоящая за этим деревом, состоит в том, что каждый node поддерживает коэффициент баланса, так что высоты левого и правого поддерева отличаются не более чем на один. Из-за этого вы можете думать о минимальном количестве узлов, необходимых для получения дерева AVL высоты h, определяется повторением, которое выглядит как N (h + 2) ~ = N (h) + N (h + 1), который очень похож на серию Фибоначчи. Если вы выработаете математику, вы можете показать, что количество узлов, необходимых для получения дерева AVL с высотой h, равно F (h + 2) - 1. Так как ряд Фибоначчи растет экспоненциально быстро, это означает, что высота AVL дерево не больше логарифмического числа узлов, что дает нам время поиска O (lg n), которое мы знаем и любим о сбалансированных бинарных деревьях. Фактически, если вы можете связать размер некоторой структуры с числом Фибоначчи, вы, вероятно, получите некоторую рабочую среду O (lg n) при некоторой операции. Это настоящая причина того, что кучи Фибоначчи называются кучами Фибоначчи - доказательством того, что количество куч после минус-мин включает в себя ограничение количества узлов, которые вы можете иметь на определенной глубине с числом Фибоначчи.
Любое число может быть записано как сумма уникальных чисел Фибоначчи. Это свойство чисел Фибоначчи имеет решающее значение для того, чтобы вообще искать работу Фибоначчи; если вы не смогли бы добавить уникальные числа Фибоначчи в любой возможный номер, этот поиск не будет работать. Сравните это с множеством других серий, например 3 ⁿ или каталонскими номерами. Это также частично объясняет, почему многие алгоритмы, такие как полномочия двух, я думаю.
Числа Фибоначчи эффективно вычисляются. Тот факт, что ряд может быть сгенерирован чрезвычайно эффективно (вы можете получить первые n слагаемых в O (n) или любой произвольный член в O (lg n)), то многие алгоритмы, которые их используют, не будут практичными. Генерирование каталонских чисел довольно сложно вычислить, IIRC. Кроме того, числа Фибоначчи имеют хорошее свойство, где, учитывая любые два последовательных числа Фибоначчи, скажем F (k) и F (k + 1), мы можем легко вычислить следующее или предыдущее число Фибоначчи, добавив два значения (F (k) + F (k + 1) = F (k + 2)) или вычитаем их (F (k + 1) - F (k) = F (k - 1)). Это свойство используется в нескольких алгоритмах в сочетании с свойством (2), чтобы разбить числа на сумму чисел Фибоначчи. Например, поиск Fibonacci использует это для определения значений в памяти, тогда как аналогичный алгоритм может быть использован для быстрого и эффективного вычисления логарифмов.
Они педагогически полезны. Преподавание рекурсии сложно, а серия Фибоначчи - отличный способ представить ее. Вы можете говорить о прямой рекурсии, об воспоминаниях или о динамическом программировании при введении серии. Кроме того, удивительная часто преподается как упражнение в индукции или в анализе бесконечных рядов, а связанная с ней матричное уравнение для чисел Фибоначчи обычно вводится в линейную алгебру в качестве мотивации собственных векторов и собственных значений. Я думаю, что это одна из причин того, что они настолько громкие во вводных классах.

Я уверен, что есть больше причин, чем просто это, но я уверен, что некоторые из этих причин являются основными факторами. Надеюсь, это поможет!

Ответ 2

Величайший общий делитель - еще одна магия; см. this для слишком большого количества магов. Но числа Фибоначчи легко вычисляются; также имеет определенное имя. Например, натуральные числа 1,2,3,4,5 имеют слишком много логики; все простые числа внутри них; сумма 1..n вычислима, каждый из которых может быть получен с другими,... но никто не заботится о них:)

Одна из важных вещей, о которых я забыл, - Золотое соотношение, которое имеет очень важное влияние в реальной жизни (например, вам нравятся широкие мониторы:)

Ответ 3

Если у вас есть алгоритм, который можно успешно объяснить простым и лаконичным mannor с понятными примерами в CS и природе, какой лучший инструмент обучения мог бы придумать?

Ответ 4

Последовательности Фибоначчи действительно встречаются повсюду в природе/жизни. Они полезны при моделировании роста популяций животных, роста клеток растений, формы снежинок, формы растений, криптографии и, конечно же, компьютерных наук. Я слышал, что это упоминается как образец ДНК природы.

Куча Фибоначчи уже упомянута; количество детей каждого node в куче не более log (n). Также поддерево, начинающееся с node с m детьми, составляет, по крайней мере, (m + 2) число фибоначчи.

Torrent как протоколы, которые используют систему узлов и супернодов, используют фибоначчи, чтобы решить, когда нужен новый супер node и сколько субнодов он будет управлять. Они выполняют node управление на основе витка фибоначчи (золотое соотношение). См. Фото ниже, как узлы разделены/объединены (разделены от одного большого квадрата на более мелкие и наоборот). Смотрите фото: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Некоторые вхождения в природе

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF

http://img.blogster.com/view/anacoana/post-uploads/finger.gif

http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif

http://2.bp.blogspot.com/-X5II-IhjXuU/TVbHrpmRnLI/AAAAAAAAABU/nv73Y9Ylkkw/s320/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879.jpg

Ответ 5

Я не думаю, что существует окончательный ответ, но одна из возможностей заключается в том, что операция деления множества S на два раздела S1 и S2, один из которых затем делится на подразделы S11 и S12, один из которых имеет такой же размер, как S2, является вероятным подходом ко многим алгоритмам и который иногда может быть численно описан как последовательность Фибоначчи.

Ответ 6

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

http://xw2k.nist.gov/dads/html/fibonacciTree.html

Он хорошо связан с обсуждением templatetypedef на AVL-деревьях (дерево AVL может в худшем случае иметь структуру фибоначчи). Я также видел, что в некоторых случаях буферы расширены в действиях фибоначчи, а не в двух случаях.

Ответ 7

Просто чтобы добавить мелочи об этом, числа Фибоначчи описывают панировку кроликов. Вы начинаете с (1, 1), двух кроликов, а затем их популяция растет экспоненциально.

Ответ 8

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