首页 文章

为什么斐波那契数字在计算机科学中具有重要意义?

提问于
浏览
74

Fibonacci numbers已经成为计算机科学学生递归的一个流行的介绍,并且有一个强烈的论据,他们坚持自然 . 出于这些原因,我们很多人都熟悉它们 .

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

我想到了两个主要的例子:

这些数字是否有某些特殊属性可以使它们优于其他数字序列?这是空间质量吗?他们还有哪些其他可能的应用程序?

这对我来说似乎很奇怪,因为在其他递归问题中有许多自然数字序列,但我从未见过Catalan堆 .

8 回答

  • 0

    让我为您添加另一个数据结构:Fibonacci树 . 它们很有趣,因为只需添加以前的节点就可以计算树中的下一个位置:

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

    它与在AVL树上的templatetypedef的讨论很好地结合(AVL树在最坏的情况下可能具有斐波纳契结构) . 在某些情况下,我也看到过在fibonacci步骤中扩展的缓冲区而不是2的幂 .

  • 67

    只是为了增加一个关于这个的琐事,斐波纳契数字描述了兔子的面包屑 . 你从(1,1),两只兔子开始,然后他们的人口呈指数增长 .

  • 1

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

  • 1

    Fibonacci数字具有各种非常好的数学特性,使它们在计算机科学中表现出色 . 这里有几个:

    • They grow exponentially fast. Fibonacci系列出现的一个有趣的数据结构是AVL树,一种自 balancer 二叉树 . 这棵树背后的直觉是每个节点都保持一个 balancer 因子,这样左右子树的高度最多相差一个 . 因此,你可以想到获得高度为h的AVL树所需的最小节点数由一个看起来像N(h 2)〜= N(h)N(h 1)的重现来定义,它看起来像很像Fibonacci系列 . 如果你计算出数学,你可以证明获得高度为h的AVL树所需的节点数是F(h 2) - 1.因为Fibonacci系列呈指数增长,这意味着AVL树的高度在节点数量上最多是对数,为您提供我们所知道的O(lg n)查找时间,并且喜欢 balancer 二叉树 . 实际上,如果您可以使用Fibonacci数绑定某个结构的大小,则可能会在某些操作上获得O(lg n)运行时 . 这就是Fibonacci堆称为Fibonacci堆的真正原因 - 证明了出队时间之后堆的数量涉及使用Fibonacci数限制一定深度的节点数 .

    • Any number can be written as the sum of unique Fibonacci numbers. Fibonacci数的这个属性对于让Fibonacci搜索工作至关重要;如果你不能工作的话 . 与许多其他系列对比,如3n或加泰罗尼亚数字 . 这也是部分原因,我认为很多算法都像2的幂 .

    • The Fibonacci numbers are efficiently computable. 系列可以非常有效地生成(你可以在O(n)或O(lg n)中的任意任意项中得到前n个项),那么很多使用它们的算法都不会说'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 F(k)和F(k 1),我们可以通过加上两个值(F(k)F(k 1)= F(k 2))或减去它们(F(k)来轻松计算下一个或前一个Fibonacci数 . 1) - F(k)= F(k-1)) . 该属性在几个算法中被利用,与property(2)一起使用,将数字分成Fibonacci数的总和 . 例如,Fibonacci搜索使用它来定位内存中的值,而类似的算法可用于快速有效地计算对数 .

    • They're pedagogically useful. 教学递归很棘手,Fibonacci系列是介绍它的好方法 . 在介绍该系列时,您可以谈论直接递归,关于memoization或动态编程 . 另外,惊人的closed-form for the Fibonacci numbers通常被教导为归纳或无限级数分析中的练习,相关的matrix equation for Fibonacci numbers通常作为特征向量和特征值背后的动机引入线性代数 . 我认为这是他们在入门课程中如此高调的原因之一 .

    我确信有更多的理由而不仅仅是这个,但我确信其中一些原因是主要因素 . 希望这可以帮助!

  • 0

    Greatest Common Divisor是另一种魔力;因为有太多魔法,所以请看this . 但Fibonacci数字很容易计算;它也有一个特定的名称 . 例如,自然数1,2,3,4,5有太多逻辑;所有素数都在其中; 1..n的总和是可计算的,每个人可以与其他人一起 生产环境 ,......但没有人照顾他们:)

    我忘了它的一件重要事情是Golden Ratio,它对现实生活有非常重要的影响(例如你喜欢宽屏显示器):)

  • 0

    如果你有一个算法可以用一个简单而简洁的方法成功地解释,在CS和自然界中有可理解的例子,那么有人能提出哪些更好的教学工具?

  • 0

    斐波那契序列确实在自然界/生命中无处不在 . 它们可用于模拟动物种群的增长,植物细胞生长,雪花形状,植物形状,密码学,当然还有计算机科学 . 我听说它被称为自然的DNA模式 .

    Fibonacci堆已经被提到了;堆中每个节点的子节点数最多为log(n) . 此外,以m个子节点开始节点的子树至少是(m 2)个斐波纳契数 .

    像使用节点和超级节点系统的协议一样使用斐波纳契来决定何时需要新的超级节点以及它将管理多少个子节点 . 他们根据斐波纳契螺旋(黄金比率)进行节点管理 . 请参见下面的照片,如何拆分/合并节点(从一个大的广场划分为较小的广场,反之亦然) . 见照片: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

  • 4

    我不认为有确定的答案,但有一种可能性是将一组S分成两个分区S1和S2的操作,其中一个分区然后被分成子分区S11和S12,其中一个分区具有相同的大小 . S2 - 是许多算法的可能方法,有时可以在数值上描述为斐波纳契数列 .

相关问题