为什么斐波那契数在计算机科学显著？

Question

Fibonacci numbers已经成为一种流行的介绍递归计算机科学的学生和有自己天性中坚持一个有力的论据。由于这些原因，我们很多人都熟悉他们。

他们也计算机科学中存在太多的其他地方;在令人惊讶地有效的数据结构和算法基于所述序列。

有迹象表明，首先想到的两个主要的例子：

• Fibonacci heaps具有更好的摊销运行时间比二项堆。
• Fibonacci search这股为O（log N）运行时间与有序阵列上二进制搜索。

有没有办法，让他们比其他数字序列的优势，这些数字的一些特殊性质？它是一个空间的品质？他们可以有什么其他可能的应用？

我觉得奇怪，我因为是发生在其他递归问题的许多自然数列，但我从来没有见过一个Catalan堆。

Answer 1

斐波那契数有各种非常好的数学特性，使得其在计算机科学优秀的。这里有几个：

1. 他们成倍增长快。其中斐波纳契数列出现一个有趣的数据结构是AVL树，自平衡二叉树的一种形式。这棵树背后的直觉是，使左，右子树的高度由至多相差每个节点维护一个平衡因素。正因为如此，可以认为必要得到高度h的AVL树由复发，看起来像N（H + 2）定义的最小数量的节点的〜= N（H）+ N（H + 1），这看起来很像斐波纳契数列。如果你的工作数学，你能证明节点所必需的数量来获得高度h的AVL树是F（H + 2） - 1.由于斐波纳契数列呈指数级增长快，这意味着AVL的高度树是在节点数量最多的对数，给你O（LG n）的查找，我们知道和喜爱平衡二叉树时间。事实上，如果你能结合一些结构与Fibonacci数的大小，你可能会得到一些操作的O（LG n）的运行时间。这是斐波那契堆被称为斐波那契堆的真正原因 - 证明堆出队分钟后，数涉及边界，你可以在一定的深度与Fibonacci数节点的数量。
2. 任何数字都可以写成唯一的斐波那契数的总和。 Fibonacci数的这家酒店是越来越斐波纳契搜索在所有工作的关键;如果你不能唯一斐波那契数加在一起为任何可能的数量，此搜索是行不通的。与很多其他的系列，像3N或Catalan数对比这一点。这也是部分为什么很多算法如的两个大国，我认为。
3. 斐波那契数是高效计算的。该系列可以非常有效地产生的事实（你可以得到的前n项的O（N）或为O任意项（LG N）），那么很多使用它们的算法是不实际。生成Catalan数是相当棘手的计算，IIRC。在此之上，斐波那契数有一个很好的属性，其中，给定任意两个连续的斐波那契数，假设F（k）和F（K + 1），我们可以很容易地通过将两个值计算下一个或前一个斐波那契数（F（K）+ F（K + 1）= F（K + 2））或减去它们（F（K + 1） - F（k）的= F（K - 1））。此属性在几种算法利用，与属性（2）相结合，掰开号码到斐波那契数的总和。例如，搜索斐波纳契使用此定位值存储器，而类似的算法可以被用于快速且有效地计算对数。
4. 他们是有用的教学法。教学递归是棘手的，和斐波纳契数列是介绍它的好方法。介绍该系列时，您能谈谈直递归，关于记忆化，或有关动态编程。此外，惊人的是closed-form for the Fibonacci numbers教授经常在感应锻炼或无穷级数的分析，以及相关的matrix equation for Fibonacci numbers是线性代数普遍引入特征向量和特征值的背后动机。我认为这是他们是如此的入门课程高调的原因之一。

我敢肯定有比这只是更多的理由，但我敢肯定，其中一些原因是主要因素。希望这可以帮助！

Answer 2

Greatest Common Divisor是另一个法宝;看到this太多的魔法。但是，斐波那契数很容易计算;也有一个特定的名称。例如，自然数1,2,3,4,5有太多的逻辑;所有素数都在其中; 1..N的总和是可计算的，每个人都可以用其他的产生，......但没有人需要对他们照顾:)

我忘了一件重要的事情是Golden Ratio，这在现实生活中非常重要的影响（例如你喜欢宽屏显示器:)

Answer 3

如果你有一个可以在一个简单明了mannor在CS和自然地解释用容易理解的例子的算法，有什么更好的教学工具，可能会有人想出？

Answer 4

斐波那契序列确实在自然界/生活中随处可见。他们在动物种群，植物细胞生长，雪花形，株形，加密的造型增长有用，当然还有计算机科学。我听说它被称为大自然的DNA模式。

斐波那契堆的已经提及;在堆中的每个节点的子节点的数量为至多的log（n）。也开始具有m孩子的节点的子树是至少第（m + 2）个Fibonacci数。

洪流就像它们使用节点的系统和超节点使用斐波那契数来决定何时需要新的超级节点，这将有多少子节点管理协议。他们这样做基于斐波那契螺旋（黄金比例）节点管理。见下文节点如何分割照片/合并（从一个大的平方成较小的，反之亦然分区）。见照片：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

Answer 5

我不认为有一个明确的答案，但一种可能性是将一组S为两个分区S1和S2之一的操作，其中然后被分成子分区S11和S12，其中之一的大小与同S2 - 是一个可能的方法来许多算法，并且可以被数值有时被描述为斐波纳契数列。

Answer 6

让我补充另一种数据结构到你：斐波那契树。他们是有趣的，因为在树的下一个位置的计算可以通过仅仅加入先前的节点来完成：

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

它关系以及与由AVL树templatetypedef的讨论（AVL树可以在最坏的情况有斐波纳契结构）。我也看到了延长斐波纳契步骤，而不是在某些情况下，两个大国的缓冲区。

Answer 7

我想补充一个琐事此事，斐波那契数说明兔子的面包屑。你开始（1,1），两只兔子，然后他们的人口呈指数增长。

Answer 8

他们为[0,1]，[1,1]矩阵可以看作是运筹学最原始的问题的功率计算（有点像囚徒困境是博弈论的最原始的问题）。

Answer 9

用频率是连续斐波那契数符号创建最大深度的霍夫曼树，树对应于源符号具有最大长度的二进制代码被编码。非斐波纳契源符号的频率创建更平衡的树，用较短的代码。码长具有在有限状态机，是负责解码给定的霍夫曼码的描述的复杂性直接影响。

---

猜想：所述第一（FIB）的图像将被压缩到38bits，而第二（统一）与50bits。这似乎更接近你的源符号的频率是斐波那契数越短，最终的二进制序列，更好的压缩，在霍夫曼模型也许是最佳的。

延伸阅读：

BÜRO，M。（1993）。上的霍夫曼码的最大长度。信息处理快报，45（5），219-223。 DOI：10.1016 / 0020-0190（93）90207 - 对