常用算法笔记 > 递归与分治
斐波那契数列

问题描述:

1.兔子繁殖问题

斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

我们不妨拿新出生的一对小兔子分析一下:

第一个月小兔子没有繁殖能力,所以还是一对

两个月后,生下一对小兔对数共有两对

三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

------


依次类推可以列出下表:

经过月数

1

2

3

4

5

6

7

8

9

10

11

12

幼仔对数

1

0

1

1

2

3

5

8

13

21

34

55

成兔对数

0

1

1

2

3

5

8

13

21

34

55

89


总体对数

1

1

2

3

5

8

13

21

34

55

89

144


幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}(n=1,2,3,...)


2.排列组合

有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法……

1,2,3,5,8,13……所以,登上十级,有89种走法。


斐波那契数列数学公式:


golang代码实现:


package main

import (
   "time"
   "fmt"
)

/***
  斐波那契数列
  递归解决
 */

func fn(n int) int {
   if (n <= 2) {
      return 1;
   }
   return fn(n-1) + fn(n-2)
}

/***
   动态规划
 */
func fn2(n int) int {
   if (n <= 2) {
      return 1;
   }
   table := make([]int, n+1)
   table[1], table[2] = 1, 1

   for i := 3; i <= n; i++ {
    table[i] =table[i-1] + table[i-2]
   }
   return table[n]
}

func main() {
   t1 := time.Now()
   result := fn(45)
   t2 := time.Now()
   fmt.Println(result, "used:", t2.Sub(t1))

   result2 := fn2(45)
   t3 := time.Now()
   fmt.Println(result2, "used:", t3.Sub(t2))
}

运行结果对比:

递归 :       1134903170 used: 4.9796857s

动态规划: 1134903170 used: 0s