Why are Fibonacci numbers significant in computer science?

Fibonacci numbers have become a popular introduction to recursion for Computer Science students and there's a strong argument that they persist within nature. For these reasons, many of us are familiar with them.

They also exist within Computer Science elsewhere too; in surprisingly efficient data structures and algorithms based upon the sequence.

There are two main examples that come to mind:

  • Fibonacci heaps which have better amortized running time than binomial heaps.
  • Fibonacci search which shares O(log N) running time with binary search on an ordered array.

Is there some special property of these numbers that gives them an advantage over other numerical sequences? Is it a spatial quality? What other possible applications could they have?

It seems strange to me as there are many natural number sequences that occur in other recursive problems, but I've never seen a Catalan heap.

24739 次浏览
小开

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

小开
最佳答案

斐波那契数具有各种非常好的数学性质，这使得它们在计算机科学中非常优秀。这里有一些:

  1. 它们以指数级的速度增长。斐波那契数列出现的一个有趣的数据结构是 AVL 树，一种自平衡二叉树。这棵树背后的直觉是，每个节点都保持一个平衡因子，因此左右子树的高度最多相差一个。正因为如此，你可以想到获得高度为 h 的 AVL 树所需的最小节点数是由一个类似于 N (h + 2) ~ = N (h) + N (h + 1)的递归定义的，这个递归看起来很像斐波那契数列。如果你计算出数学，你可以显示得到高度 h 的 AVL 树所需的节点数是 F (h + 2)-1。因为斐波那契数列以指数形式快速增长，这意味着 AVL 树的高度在节点数上最多是对数，这就给了你我们所知道并喜欢的平衡二叉树的 O (lgn)查找时间。事实上，如果你能用一个斐波那契数列绑定某个结构的大小，你很可能在某个操作上得到一个 O (lgn)运行时。这就是 Fibonacci 堆被称为 Fibonacci 堆的真正原因——这证明了一个 dequeue min 之后的堆的数量涉及到将节点的数量限制在一定深度的斐波那契数列。
  2. 任何数都可以写成唯一斐波那契数的和。斐波那契数的这个属性对于斐波那契搜索的工作至关重要; 如果你不能将唯一的斐波那契数加到任何可能的数中，这个搜索就不会工作。将这个数字与其他很多数字系列相比较，比如3N或者加泰罗尼亚数字。我想，这也是为什么很多算法都喜欢二的幂的部分原因。
  3. 斐波那契数是可有效计算的。事实上，级数可以非常有效地生成(你可以得到 O (n)中的前 n 项或者 O (lgn)中的任意项) ，那么很多使用它们的算法就不实用了。生成加泰罗尼亚数字在计算上是相当棘手的，IIRC。除此之外，斐波那契数还有一个很好的性质，假设有两个连续的斐波那契数，比如 f (k)和 f (k + 1) ，我们可以通过加上两个值(F (k) + F (k + 1) = F (k + 2))或者减去它们(F (k + 1)-F (k) = F (k-1))来轻松计算下一个或前一个斐波那契数列。这个属性在几个算法中被利用，结合属性(2) ，把数字分解成斐波那契数字的和。例如，Fibonacci 搜索使用它来定位内存中的值，而类似的算法可以用来快速有效地计算对数。
  4. 它们在教学上很有用。教授递归是很棘手的，斐波那契数列是一个很好的介绍递归的方法。在介绍本系列文章时，您可以讨论直接递归、制表或动态编程。此外，令人惊叹的 斐波那契数的封闭形式经常被作为归纳或无穷级数分析的练习来教授，而相关的 斐波那契数矩阵方程通常被引入线性代数作为特征矢量背后的动机。我认为这是他们在入门课上如此引人注目的原因之一。

我相信还有更多的原因，但我相信其中的一些原因是主要的因素。希望这个能帮上忙！

小开

最大公约数 是另一种魔法，太多魔法见 这个。但是斐波那契数很容易计算，而且它有一个特定的名字。例如，自然数1、2、3、4、5有太多的逻辑; 所有的素数都在它们之中; 1的和。.N 是可计算的，每个人都可以与其他人一起生产，... ... 但是没有人关心他们:)

我忘记的一件重要的事情是 黄金比率，它在现实生活中有非常重要的影响(例如，你喜欢宽显示器:)

小开

让我为您的数据结构添加另一个数据结构: 斐波那契树。它们之所以有趣，是因为计算树中的下一个位置只需要添加前面的节点:

Http://xw2k.nist.gov/dads/html/fibonaccitree.html

它与 templatetypedef 关于 AVL- 树的讨论(AVL- 树最坏可能具有斐波那契结构)相吻合。我还看到在斐波那契步骤中扩展的缓冲区，而不是某些情况下的二次幂。

小开

如果你有一个算法，可以成功地解释在一个简单和简明的方式与可理解的例子在 CS 和自然，还有什么更好的教学工具可以拿出来呢？

小开

斐波那契数列确实在自然界/生命中随处可见。它们在动物种群生长、植物细胞生长、雪花形状、植物形状、密码学，当然还有计算机科学等方面都非常有用。我听说它被称为自然界的 DNA 模式。

已经提到了 Fibonacci 堆; 堆中每个节点的子节点数最多为 log (n)。另外，以 m 个子节点开始的子树至少是(m + 2)次斐波那契数列。

使用节点和超节点系统的 Torrent 类协议使用斐波那契(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

小开

为了增加一个关于这个的琐事，斐波那契数字描述了兔子的面包。你从(1,1)开始，两只兔子，然后它们的数量成指数增长。

小开

他们的计算作为[0,1] ，[1,1]矩阵的幂可以被认为是运筹学中最原始的问题(有点像囚徒困境是博弈论中最原始的问题)。

小开

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

推测: 第一张图像压缩为38位，第二张图像压缩为50位。似乎你的源符号频率越接近斐波那契数字，最终的二进制序列越短，压缩效果就越好，在 Huffman 模型中可能是最佳的。

huffman.ooz.ie/?text=ABBCCCDDDDDEEEEEEEE

enter image description here

进一步阅读:

关于霍夫曼码的最大长度。信息 处理信件，45(5) ，219-223. doi: 10.1016/0020-0190(93)90207-p

小开

对我来说，这是关于秩序和空间坐标。

斐波那契数列可以用作时钟。

斐波那契数列允许逐个小数计算黄金数。

黄金数乘以它本身几乎等于黄金数 + 1。

所以我们当然可以把一个整数，切割成一系列的整数，单位，例如使用索引。

我在 python 中做了第一个初始版本。(poc)代码要更新。

Https://gitlab.com/numbers/numbers/-/blob/main/ranging.py

因此，我们可以将计算步骤和存储空间框架、计数和协调到这个完全周期性的参考框架(在时间上) ，从而使它成为一种普遍的乘法表等价物。对我来说，它是一个明确的映射。

这个想法是最终提出一个三元代码，根据斐波那契计算步骤显式管理内存空间，然后找到我们所有的数字。

一旦完成，要使用这个映射，这个通用表，这个过滤器: 检查一致性，一致性，周期性的复杂可计算操作，如轮实验，窦，重力等。.

你这么说听起来有点自命不凡。不是的。没有人创造出黄金数或斐波那契数。他们就在这里，像树上的果实一样被赐予。


提交答案