什么是斐波那契数列,还有优化?

简介: 什么是斐波那契数列,还有优化?

什么是斐波拉契数列 (Fibonaccisequence)

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多・斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为 “兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……

使用 Golang 递归实现斐波拉契数列

package main
import (
    "fmt"
)
func fibonacci(n int) (r int) {
    if n <= 2 {
  return 1
    }
    return fibonacci(n-1) + fibonacci(n-2)
}
func main() {
    for i := 0; i < 10; i++ {
  fmt.Printf("%d, ", fibonacci(i))
    }
}

得到结果:

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

斐波拉契数列的递归实现优化

由于上述代码使用了两次递归,为减少递归次数,对递归代码优化如下:

package main
import (
    "fmt"
)
func advanceFibonacii(n int) (r int) {
    if n <= 2 {
  return 1
    }
    result := 1
    for i := 2; n > i; n-- {
  result += advanceFibonacii(n - 2)
    }
    return result
}
func main() {
    for i := 0; i < 10; i++ {
  fmt.Printf("%d, ", advanceFibonacii(i))
    }
}

得到结果

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

斐波那契数列的应用

  • 算法
  • 斐波那契堆
  • 欧几里得算法的时间复杂度
  • 物理学:氢原子能级问题
  • 自然界:植物的生长
  • 波浪理论与股市
  • 斐波那契螺旋
  • 建筑学
  • 据说一个小男孩参考斐波那契数列发明了太阳能电池树
  • 斐波那契螺旋形的摇椅

总结

斐波那契数列非常重要,所有关于数学的书几乎都会提到。

相关文章
【超直白】算法:斐波那契数列
【超直白】算法:斐波那契数列
【超直白】算法:斐波那契数列
斐波那契数列的四种实现算法
斐波那契数列的四种实现算法
185 3
|
8月前
|
精益求精——斐波那契数列的logn解法
精益求精——斐波那契数列的logn解法
117 0
|
9月前
生成斐波那契数列的几种不同的方法
生成斐波那契数列的几种不同的方法
139 0
斐波那契数列(递归+迭代)
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、3
160 0
算法 | 详解斐波那契数列问题
算法 | 详解斐波那契数列问题
189 0
算法 | 详解斐波那契数列问题
斐波那契数列(简单难度)
斐波那契数列(简单难度)
174 0
斐波那契数列(简单难度)
算法练习——(6)斐波那契数列前20个
在数学上有一个著名的斐波那契数列,它的规律为:1,1,2,3,5,8,13,21……,请编程输出其前20个数字。
189 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等