已经成为一种流行的介绍递归的计算机科学专业的学生，​​并有一个有力的论据，他们自然在坚持斐波那契数。由于这些原因，我们很多人都熟悉。

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:

斐波那契堆具有更好 摊销运行时间比二项式 堆。 斐波那契搜索这股 O（日志N）的二进制运行时间 搜索有序阵列上。 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.

推荐答案

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

The Fibonacci numbers have all sorts of really nice mathematical properties that make them excellent in computer science. Here's a few:

他们成倍增长很快。的一个有趣的数据，其中，斐波那契数列出现的是AVL树，自动平衡二叉树形式的结构。此树后面的直觉是，每个节点维护一个平衡因子，使得左和右子树的高度相差至多一个。正因为如此，可以认为节点必要得到的高度h的AVL树是由一个复发，看起来像N（H + 2）中所定义的最小数目的〜= N（H）+ N（H + 1），这看起来很像斐波那契数列。如果你的工作算算，你能证明节点所必需的数量得到高度为h的AVL树是F（H + 2） - 1.由于Fibonacci序列呈指数级增长快，这意味着一个AVL的高度树是在对数最多的节点数量，使您的O（LG n）的查找时间，我们知道和喜欢平衡二叉树。事实上，如果你能绑定一些结构与斐波那契数的大小，你可能会得到一些操作的O（LG n）的运行时间。这是斐波那契堆被称为斐波那契堆的真正原因 - 证明了堆出队分钟后数涉及到边界节点的数量，你可以在一定的深度与斐波那契数 任何号码可以写成独特的斐波那契数之和的斐波那契数的这家酒店是一个介绍斐波那契搜索工作在所有的关键。如果你能不是唯一的斐波那契数加在一起为任何可能的数量，此搜索是行不通的。与很多其它系列对比这一点，像3 N 或Catalan数。这也是部分为什么很多像两个大国的算法，我想。 斐波那契数字是有效的计算。，该系列能够非常有效地产生的事实（你可以得到的前n项为O（n）或任意来看在O（LG N） ），则大量的使用它们的算法是不实际。生成Catalan数为pretty的计算技巧，IIRC。在此之上，斐波那契数都在那里，给定任意两个连续的斐波那契数一个很好的属性，让我们说F（k）和F（K + 1），我们可以很容易地计算出通过将一个或previous斐波纳契数这两个值（F（k）的+ F（K + 1）= F（K + 2））或减去它们（F（K + 1） - F（k）的= F（K - 1））。该属性被利用在几种算法，与属性（2）结合使用，以数字分裂成斐波纳契数的总和。例如，斐波搜索使用此定位值在存储器中，而类似的算法可以被用于快速且有效地计算对数。 他们教学上很有用的。的教学递归是棘手的，和斐波那契数列是一个伟大的方式来介绍它。您可以介绍该系列时，谈论直递归，关于记忆化，或对动态规划。此外，令人惊叹的封闭形式的斐波那契数是经常教导作为练习诱导或在无穷级数进行分析，并为Fibonacci数的相关矩阵方程式线性代数如通常引入背后的特征值和特征值动机。我认为这是他们是如此高调的入门课程的原因之一。 They grow exponentially fast. One interesting data structure in which the Fibonacci series comes up is the AVL tree, a form of self-balancing binary tree. The intuition behind this tree is that each node maintains a balance factor so that the heights of the left and right subtree differ by at most one. Because of this, you can think of the minimum number of nodes necessary to get an AVL tree of height h is defined by a recurrence that looks like N(h + 2) ~= N(h) + N(h + 1), which looks a lot like the Fibonacci series. If you work out the math, you can show that the number of nodes necessary to get an AVL tree of height h is F(h + 2) - 1. Because the Fibonacci series grows exponentially fast, this means that the height of an AVL tree is at most logarithmic in the number of nodes, giving you the O(lg n) lookup time we know and love about balanced binary trees. In fact, if you can bound the size of some structure with a Fibonacci number, you're likely to get an O(lg n) runtime on some operation. This is the real reason that Fibonacci heaps are called Fibonacci heaps - the proof that the number of heaps after a dequeue min involves bounding the number of nodes you can have in a certain depth with a Fibonacci number. Any number can be written as the sum of unique Fibonacci numbers. This property of the Fibonacci numbers is critical to getting Fibonacci search working at all; if you couldn't add together unique Fibonacci numbers into any possible number, this search wouldn't work. Contrast this with a lot of other series, like 3n or the Catalan numbers. This is also partially why a lot of algorithms like powers of two, I think. The Fibonacci numbers are efficiently computable. The fact that the series can be generated extremely efficiently (you can get the first n terms in O(n) or any arbitrary term in O(lg n)), then a lot of the algorithms that use them wouldn't be practical. Generating Catalan numbers is pretty computationally tricky, IIRC. On top of this, the Fibonacci numbers have a nice property where, given any two consecutive Fibonacci numbers, let's say F(k) and F(k + 1), we can easily compute the next or previous Fibonacci number by adding the two values (F(k) + F(k + 1) = F(k + 2)) or subtracting them (F(k + 1) - F(k) = F(k - 1)). This property is exploited in several algorithms, in conjunction with property (2), to break apart numbers into the sum of Fibonacci numbers. For example, Fibonacci search uses this to locate values in memory, while a similar algorithm can be used to quickly and efficiently compute logarithms. They're pedagogically useful. Teaching recursion is tricky, and the Fibonacci series is a great way to introduce it. You can talk about straight recursion, about memoization, or about dynamic programming when introducing the series. Additionally, the amazing closed-form for the Fibonacci numbers is often taught as an exercise in induction or in the analysis of infinite series, and the related matrix equation for Fibonacci numbers is commonly introduced in linear algebra as a motivation behind eigenvectors and eigenvalues. I think that this is one of the reasons that they're so high-profile in introductory classes.

我敢肯定有比眼​​前这个原因比较多，但我敢肯定，其中一些原因是主要因素。希望这有助于！

I'm sure there are more reasons than just this, but I'm sure that some of these reasons are the main factors. Hope this helps!