问题
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 于 2020-06-8 19:15 更新