为什么斐波那契数在计算机科学中如此重要？

Question

斐波那契数列已经成为计算机科学学生递归的流行入门课程，有强有力的论据表明它们在自然界中存在。因此，我们中的许多人都很熟悉它们。

它们也存在于计算机科学的其他领域；基于这个序列的数据结构和算法具有惊人的效率。

有两个主要的例子：

• 斐波那契堆比二项式堆具有更好的摊销运行时间。
• 斐波那契搜索与有序数组上的二分搜索共享O(log N)的运行时间。

这些数字是否具有比其他数字序列更优越的特殊属性？是一种空间质量吗？它们可能还有哪些其他应用？

对我来说，这似乎很奇怪，因为在其他递归问题中会出现许多自然数序列，但我从未见过卡特兰数堆。

- Ian Bishop

---

熟悉度不是最大的因素吗？ - Cyclone

我认为这种问题适合在 cstheory 或 math SE 上讨论。有趣，但不属于此处讨论范畴。 - Fred Foo

我不同意。这是我最近看到的最有趣的问题之一，它的相关性得到了支持，因为作为程序员，我们在各个领域都可以看到它。 - Mike

这似乎与在math.stackexchange.com上提出的“斐波那契数列的应用”有关。那里还有其他类似的问题，涉及序列的具体应用。那可能是讨论序列“属性”的好地方，以及它如何适用于更一般的算法。我觉得这个问题正在接近计算理论的讨论，可能会在那里得到更好/更多的关注。 - RobertB

我在这件事上和larsmans一致（显然），我同意cstheory也是另一个很好的去处。 - RobertB

Answer 1

斐波那契数列在计算机科学中有许多非常不错的数学特性。以下是其中几个：

1. 它们以指数级增长。 斐波那契数列出现在一种数据结构 AVL 树中，这是一种自平衡的二叉树。这种树的设计思想是每个节点都维护一个平衡因子，使得左右子树的高度之差最多为1。由此可知，得到一个高度为h的AVL树所需的最小节点数是由一个看起来很像斐波那契数列的递归式定义的，即 N(h + 2) ~= N(h) + N(h + 1)。如果你解出了数学公式，就可以证明获得一个高度为 h 的 AVL 树所需的节点数量是 F(h + 2) - 1。由于斐波那契数列以指数级增长，因此 AVL 树的高度最多是节点数的对数级别，这就给了我们关于平衡二叉树 O(lg n) 的查找时间。事实上，如果你能用斐波那契数列限制某些结构的大小，则某些操作的运行时间可能会达到 O(lg n)。这就是斐波那契堆被称为斐波那契堆的真正原因——推导出一个 dequeue min 操作后堆的数量，需要使用斐波那契数列来限制某一深度中节点的数量。
2. 任何数都可以表示为唯一斐波那契数的和。 斐波那契数的这个性质对于让斐波那契查找算法有效至关重要。如果你不能将唯一的斐波那契数相加得到任意可能的数字，那么这种查找就行不通了。相比之下，像3ⁿ或卡特兰数等其他数列则是不具备这个性质的。这也部分解释了为什么很多算法喜欢用2的幂。
3. 斐波那契数列可以高效地计算。这个系列可以非常高效地生成（你可以用O（n）获取前n项或任意项O（lg n）），所以许多使用它们的算法是不实际的。生成卡特兰数非常棘手，如果我没记错的话。此外，斐波那契数列具有一个很好的特性，在给定任何连续的两个斐波那契数F(k)和F(k+1)的情况下，我们可以通过添加这两个值（F(k)+F(k+1)=F(k+2)）或减去它们（F(k+1)-F(k)=F(k-1)）轻松地计算下一个或前一个斐波那契数。该属性与属性（2）结合使用，可以将数字分解为一组斐波那契数之和的几个算法中被利用。例如，斐波那契搜索使用此方法在内存中定位值，而类似的算法可用于快速有效地计算对数。
4. 它们在教学上很有用。教递归很麻烦，斐波那契数列是介绍递归的绝佳方式。您可以在介绍该系列时谈论直接递归，记忆化或动态规划。此外，惊人的斐波那契数列的闭形式通常被教授作为归纳法或无限级数分析的练习，并且相关的矩阵方程斐波那契数列通常在线性代数中介绍，作为特征向量和特征值背后的动机。我认为这是它们在入门课程中如此高调的原因之一。

我相信除了这个原因还有其他原因，但我相信这些原因是主要因素之一。希望这可以帮助！

- templatetypedef

---

这一点也同样适用于2的幂次方 ；-) - Aryabhatta

在＃2中，重要的是要使斐波那契数列不连续，这样总和才能是唯一的。 - kunigami

斐波那契搜索的有用之处在于它们的生成多项式是x^2-x-1。斐波那契搜索与黄金分割搜索寻找连续函数的最小值具有相似性质。 - Alexandre C.

@Alexandre C. - 你能详细解释一下吗？我不知道为什么那个特定的生成多项式很有用。 - templatetypedef

斐波那契数列也可以用于斐波那契素性测试（虽然不是最好的测试方法，但还算实用）...除了p=5之外，p总是会被F(p-1)或F(p+1)中的一个整除，而p对5取模则决定了哪个。它本身是概率性的，但与费马测试等其他概率性测试结合使用，就有了一些确定性模型。 - CogitoErgoCogitoSum

Answer 2

最大公约数是另一种神奇的东西；在这里可以看到太多的魔法。但斐波那契数列很容易计算，而且它有一个特定的名称。例如，自然数1,2,3,4,5之间有太多的逻辑；所有质数都在其中；1..n的和是可计算的；每个数字都可以与其他数字相乘……但没有人关心它们 :)

我忘了一个重要的事情，那就是黄金比例，它在现实生活中有非常重要的影响（例如你喜欢宽屏显示器 :)）

- Saeed Amiri

Answer 3

斐波那契数列确实在自然/生活中随处可见。它们对于模拟动物种群的增长、植物细胞的生长、雪花形状、植物形态、密码学以及计算机科学都非常有用。我听说过它被称为自然界的DNA模式。

已经提到了斐波那契堆；堆中每个节点的子节点数最多为log(n)。此外，具有m个子节点的节点开始的子树至少是第(m+2)个斐波那契数。

类似于Torrent协议的使用节点和超级节点系统使用斐波那契来决定何时需要新的超级节点以及它将管理多少子节点。他们基于斐波那契螺旋（黄金比例）进行节点管理。请参见下面的照片，了解节点如何分裂/合并（从一个大正方形分割成小正方形，反之亦然）。请参见照片：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

- Adrian

Answer 4

如果你有一个算法，可以用简单明了的方式解释，并且提供计算机科学和自然界的易于理解的例子，那么还有什么比这更好的教学工具呢？

- savalia

Answer 5

将它们作为[[0,1],[1,1]]矩阵的幂进行计算，可以被视为运筹学中最原始的问题（有点像囚徒困境是博弈论中最原始的问题）。

- Dmitry Rubanovich

Answer 6

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

---

猜想：第一张（fib）图像将被压缩到38位，而第二张（uniform）则为50位。似乎源符号频率越接近斐波那契数列，最终的二进制序列就越短，压缩效果越好，也许在哈夫曼模型中是最优的。

进一步阅读：

Buro, M. (1993). 关于哈夫曼编码的最大长度。信息处理通讯，45（5），219-223。doi:10.1016/0020-0190(93)90207-p

- FranG

Answer 7

我认为没有一个明确的答案，但其中一种可能是将集合S分成两个分区S1和S2，其中一个分区再分成两个子分区S11和S12，其中一个子分区的大小与S2相同 - 这是许多算法可能采用的方法，并且有时可以数值描述为斐波那契序列。

- DVK

Answer 8

让我给你的数据结构添加另一个：斐波那契树。它们很有趣，因为可以通过简单地将前面节点相加来计算树中下一个位置：

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

这与templatetypedef关于AVL树的讨论非常契合（最坏情况下，AVL树可以具有斐波那契结构）。在某些情况下，我也看到缓冲区是以斐波那契步长而不是二次幂进行扩展的。

- I GIVE CRAP ANSWERS

Answer 9

对我而言，这是关于顺序和空间坐标。

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

斐波那契数列可以计算黄金数字的小数。

黄金数字乘以自身几乎等于黄金数字+1。

因此，我们肯定可以通过使用例如指数来将整数划分为一系列单位的整数。

我在Python中制作了一个初步的天真版本。(poc) 代码将被更新。

https://gitlab.com/numbers/Numbers/-/blob/main/ranging.py

因此，我们可以将计算步骤和内存空间框定、计数和协调到完美的周期性参考框架（时间）中，从而使其成为一种通用的乘法表等效物。对我来说，这明确是一种映射。

这个想法最终是提出一个三进制代码，根据斐波那契计算步骤明确管理内存空间，然后在其中找到所有的数字。

一旦完成，使用这个映射、这个通用表格、这个过滤器：检查可计算操作的协调性、一致性、周期性，例如惠勒实验、正弦、重力等等......

听起来很自负，但实际上并不是这样。没有人创造黄金比例或斐波那契数列。它们就在这里，就像树上的果实一样。

- fredy fredo

---

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

虽然此链接可能回答了问题，但最好在此处包括答案的基本部分并提供参考链接。仅限链接的答案如果链接页面更改可能会失效。- 来自评论 - user16217248

Answer 10

关于这个问题，再补充一点有趣的小知识：斐波那契数列描述了兔子的繁殖。你从两只兔子（1, 1）开始，然后它们的数量呈指数级增长。

- Mihaela