斐波那契数已成为计算机科学专业学生对递归的流行介绍，并且有一个强有力的论点认为它们在自然界中存在。由于这些原因，我们中的许多人都熟悉它们。
它们也存在于其他地方的计算机科学中；在基于序列的令人惊讶的高效数据结构和算法中。
我想到了两个主要的例子：
这些数字是否有一些特殊属性使它们比其他数字序列具有优势？是空间品质吗？他们还有哪些其他可能的应用？
对我来说这似乎很奇怪，因为在其他递归问题中出现了许多自然数序列，但我从未见过加泰罗尼亚堆。
问问题
23223 次
9 回答
69
斐波那契数具有各种非常好的数学特性，使它们在计算机科学中表现出色。这里有几个：
- 它们呈指数级增长。 出现斐波那契数列的一个有趣的数据结构是 AVL 树，一种自平衡二叉树的形式。这棵树背后的直觉是每个节点都维护一个平衡因子，以便左右子树的高度最多相差一个。因此，您可以认为获得高度为 h 的 AVL 树所需的最小节点数由看起来像 N(h + 2) ~= N(h) + N(h + 1) 的递归定义，这看起来很像斐波那契数列。如果您计算出数学，您可以证明获得高度为 h 的 AVL 树所需的节点数为 F(h + 2) - 1。因为斐波那契数列呈指数增长，这意味着 AVL 的高度树的节点数最多为对数，为您提供 O(lg n) 查找时间，我们知道并喜欢平衡二叉树。实际上，如果您可以使用斐波那契数限制某些结构的大小，那么您可能会在某些操作上获得 O(lg n) 运行时间。这就是斐波那契堆被称为斐波那契堆的真正原因 - 证明出队最小值后的堆数量涉及用斐波那契数限制在一定深度内可以拥有的节点数量。
- 任何数字都可以写成唯一斐波那契数的总和。 斐波那契数列的这一特性对于让斐波那契搜索完全发挥作用至关重要；如果您无法将唯一的斐波那契数加到任何可能的数中，则此搜索将不起作用。将此与许多其他系列进行对比，例如 3 n或加泰罗尼亚数字。这也是为什么很多算法喜欢二的幂的部分原因，我认为。
- 斐波那契数是有效可计算的。 事实上，可以非常有效地生成系列（您可以在 O(n) 中获得前 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)，将数字分解为斐波那契数的总和。例如，斐波那契搜索使用它来定位内存中的值，
- 它们在教学上很有用。 递归教学很棘手，斐波那契数列是介绍它的好方法。在介绍该系列时，您可以谈论直接递归、记忆化或动态编程。此外，斐波那契数的惊人封闭形式通常作为归纳或无限级数分析的练习来教授，并且斐波那契数的相关矩阵方程通常作为特征向量和特征值背后的动机在线性代数中引入。我认为这是他们在入门课程中如此引人注目的原因之一。
我敢肯定还有更多的原因，但我敢肯定，其中一些原因是主要因素。希望这可以帮助！
于 2010-12-31T18:46:32.743 回答
1
斐波那契数列确实在自然界/生活中随处可见。它们可用于模拟动物种群的增长、植物细胞的生长、雪花形状、植物形状、密码学，当然还有计算机科学。我听说它被称为自然的 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
于 2011-12-16T15:59:43.750 回答
1
如果你有一个算法可以用简单明了的方式成功地解释，并在 CS 和自然中提供可理解的例子，那么有人能想出什么更好的教学工具呢？
于 2011-01-01T04:32:51.693 回答
0
我认为没有明确的答案，但一种可能性是将集合 S 划分为两个分区 S1 和 S2 的操作，然后将其中一个划分为子分区 S11 和 S12，其中一个的大小与S2 - 可能是许多算法的一种方法，有时可以用数字描述为斐波那契数列。
于 2010-12-31T18:40:24.923 回答
0
让我为您添加另一个数据结构：斐波那契树。它们很有趣，因为树中下一个位置的计算可以仅通过添加先前的节点来完成：
http://xw2k.nist.gov/dads/html/fibonacciTree.html
它与 templatetypedef 对 AVL-trees 的讨论非常吻合（AVL 树在最坏的情况下可以具有斐波那契结构）。在某些情况下，我还看到缓冲区以斐波那契步长而不是 2 次方的形式扩展。
于 2010-12-31T19:38:19.603 回答
0
只是为了添加一个琐事，斐波那契数字描述了兔子的面包屑。你从 (1, 1) 开始，两只兔子，然后它们的数量呈指数增长。
于 2012-02-14T10:45:09.987 回答
0
频率为连续斐波那契数的符号创建最大深度霍夫曼树，该树对应于用最大长度二进制代码编码的源符号。非斐波那契源符号频率创建更平衡的树，代码更短。代码长度直接影响负责解码给定霍夫曼代码的有限状态机的描述复杂性。
猜想：第一个（fib）图像将被压缩为 38bits，而第二个（uniform）图像将被压缩为 50bits。似乎您的源符号频率越接近斐波那契数，最终二进制序列越短，压缩越好，在霍夫曼模型中可能是最佳的。
延伸阅读：
Buro, M. (1993)。关于霍夫曼码的最大长度。信息处理快报，45（5），219-223。doi:10.1016/0020-0190(93)90207-p
于 2019-02-10T14:50:19.113 回答
0
它们作为 [[0,1],[1,1]] 矩阵的幂的计算可以被认为是运筹学中最原始的问题（有点像囚徒困境是博弈论中最原始的问题）。
于 2016-07-18T20:20:41.907 回答