问题

---

Fibonacci数列的每项都是它的前两项的和。以1和2开始，该数列的前10项为：

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

求出Fibonacci数列项不大于400万的偶数的和。

* 传送门

 

分析

---

Fibonacci数列是通过递归的方式定义的：

\(
Fib(n) =
\begin{cases}
1,& \text{if } n = 1\\
2,& \text{if } n = 2\\
Fib(n-1)+Fib(n-2)
\end{cases}
\)

所以直接从数列项的小到大方向一项一项判断是否为偶数、求和就可以，在一个简单的循环中用两个变量记录着Fibonacci数列相邻的两项便可以，无须写出一个完整的Fibonacci求项函数。如果利用递归写出求项函数，每次求值都相当于遍历一次数列，速度非常慢的。

如果非要利用求项函数解题，那么可以利用Fibonacci的非递归通项公式：

\(
Fib(n) = \frac{1}{\sqrt 5} \cdot [(\frac{1 + \sqrt 5}{2})^{n+1} – (\frac{1 – \sqrt 5}{2})^{n+1}]
\)

* 该公式可以通过递归定义求代数解得到。

 

答案

---

直接利用简单循环判断：

// answer1: simple loop
const start = Date.now()

var sum = 0, a1 = 1, a2 = 2
do {
    if ((a1 % 2) == 0) sum += a1
    const a3 = a1 + a2
    a1 = a2
    a2 = a3
} while (a1 < 4000000)

alert(sum + ', ' + (Date.now() - start) + 'ms')

求值

直接利用非递归通项公式：

// answer2: using formula
const start = Date.now()

const sqrt5 = Math.sqrt(5), x = (1 + sqrt5) / 2, y = (1 - sqrt5) / 2
const fib = (n) => Math.round((Math.pow(x, n+1) - Math.pow(y, n+1)) / sqrt5)

var sum = 0, n = 1, a_n = fib(n)
do {
    if ((a_n % 2) == 0) sum += a_n
    a_n = fib(++n)
} while (a_n < 4000000)

alert(sum + ', ' + (Date.now() - start) + 'ms')

求值

显然，利用通项公式其实需要进行更多的计算，还不如直接简单循环来得高效。

另外，使用简单直接的递归定义的方法也是可以得到结果：

// answer3: using recursion
const start = Date.now()

function fib(n) {
    if (n == 1)
        return 1
    else if (n == 2)
        return 2
    else
        return fib(n-1) + fib(n-2)
}

var sum = 0, n = 1, a_n = fib(n)
do {
    if ((a_n % 2) == 0) sum += a_n
    a_n = fib(++n)
} while (a_n < 4000000)

alert(sum + ', ' + (Date.now() - start) + 'ms')

求值

显然，直白的递归调用计算速度其实是极慢的。

但其实递归也可以很快，现代浏览器的JavaScript都基本有尾递归优化，可以尝试利用：

// answer4: using tail recursion
const start = Date.now()

function fib(n) {
    function fib_n(curr, next, n) {
        if (n == 0)
            return curr
        else
            return fib_n(next, curr+next, n-1)
    }
    return fib_n(1, 1, n)
}

var sum = 0, n = 1, a_n = fib(n)
do {
    if ((a_n % 2) == 0) sum += a_n
    a_n = fib(++n)
} while (a_n < 4000000)

alert(sum + ', ' + (Date.now() - start) + 'ms')

求值

当然，如果编程语言允许使用生成器（genertor），是可以少走很多弯路的：

// answer5: using generator
const start = Date.now()

function* fib() {
    var curr = 1, next = 2
    while (true) {
        yield curr
        const tmp = curr + next
        curr = next
        next = tmp
    }
}

var sum = 0
for (const a_n of fib()) {
    if ((a_n % 2) == 0) sum += a_n
    if (a_n >= 4000000) break
}

alert(sum + ', ' + (Date.now() - start) + 'ms')

求值

原则上讲，使用生成器的方法的效率应该是等价于第一个答案、直接使用普通循环的。而就代码的易读性来说，使用了生成器的方法更言之有物，因为使用简单循环的方法咋一眼看下去，不提醒你，可能都不知道是在使用Fibonacci数列。

打赏作者

由 bruce 于 2017-09-17 18:56 更新