最近看到了Project Euler的问题2，感觉是挺有意思的。然后打算用Haskell做一做。

问题本体如下：

1
2
3
4
5
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

简单来说的话，就是求斐波那契数列中四百万以下的偶数的和。

最初的解法

很直接的想法就是直接写出来。我对于Haskell中取得一个斐波那契数列流的代码印象深刻，因为这是我所见过的最优雅的求斐波那契数列的方式了。

1
Prelude> fib = 1:1:zipWith (+) fib (tail fib)

然后有了这么一个流我们就可以从中取出比4 000 000小，而且是偶数的数字进行求和即可。

首先取小于四百万的数，用takeWhile 函数能很好的完成这个目的，而且返回的已经是一个有限的队列了。

1
2
Prelude> takeWhile (< 4000000) fib
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578]

然后求其中为偶数的：

1
2
Prelude> filter even it
[2,8,34,144,610,2584,10946,46368,196418,832040,3524578]

最后进行求和：

1
2
Prelude> sum it
4613732

这就是最终解了。如果我们把它写在文件中，最终可以只有这么两行：（用列表构造器可以代替filter）

1
2
fib = 1:1:zipWith (+) fib (tail fib)
main = print $ sum [x | x <- (takeWhile (<4000000) fib), even(x)]

另一种方式

虽然已经做完了这个问题，而且我觉得还有改进的空间。

最开始就是陷到了那个求出流的方式中，Haskell是默认惰性求值而且存储中间结果，因而最终我们会得到一系列的存放在内存中的斐波那契数，然而其实我们本来不需要这么多数字，我们只需要最终的求和就好了。于是考虑可以在求出数列的过程中进行筛选并且直接进行加和。

根据奇偶数的规律：

1
2
3
奇 + 奇 = 偶
奇 + 偶 = 奇
偶 + 偶 = 偶

我们可以发现，在斐波那契数列中，偶数的下标都3的倍数。然后再根据数列中的递推规律，可以写出来这种形式的求和：

1
2
3
4
5
6
7
Prelude> :{
Prelude| evenfib y z
Prelude|         | (z > 4000000) = 0
Prelude|         | (otherwise) = z + evenfib (y+2*z) (2*y+3*z)
Prelude| :}
Prelude> evenfib 1 2
4613732

其中里面的z是一个偶数，然后y是偶数前面的斐波那契数。然后这里递归给的参数是求出来的下一个目标的y与z值。

这是我写的第二种解法。但是效率就很难说，因为这里其实相当于把数字算了两遍，这并不是一个非常好的办法。

这后面的方法基本都是官方给出的例子。链接在这里

更好的方法

我是完全没想到居然有这样的公式的：

$$
\begin{equation}
\begin{aligned}
A_{n} &= A_{n-1} + A_{n-2} &= A_{n-3} + 2A_{n-2} \\
&= 3A_{n-3} + 2A_{n-4} &= 3A_{n-3} + A_{n-4} + A_{n-5} + A_{n-6} \\
&= 4A_{n-3} + A_{n-6}
\end{aligned}
\end{equation}
$$

也即：$ A_{n} = 4A_{n-3} + A_{n-6} $。

如果$A_1$为0和$A_2$为4，这条公式就是满足为偶数的斐波那契数列的规律了。

然后我们可以通过斐波那契数列的通项公式估计在4000000以前的项数，可以很粗暴的得到：

1
2
3
4
5
6
7
evenFib 0 = 0, evenFib 1 = 2, evenFib (n+2) = evenFib n + 4 * evenFib (n+1).
problem_2 = sumEvenFibs $ numEvenFibsLessThan 1000000
  where
    sumEvenFibs n = (evenFib n + evenFib (n+1) - 2) `div` 4
    evenFib n = round $ (2 + sqrt 5) ** (fromIntegral n) / sqrt 5
    numEvenFibsLessThan n =
              floor $ (log (fromIntegral n - 0.5) + 0.5*log 5) / log (2 + sqrt 5)

这是一个很粗暴的解法，尽管有效，它的开销也是很大的。

可以由此写出来的类似于第一种的方法如下：

1
2
3
4
5
evenFibs = 2 : 8 : zipWith (+) (map (4*) (tail evenFibs)) evenFibs
sumEvenFibsBelow n = ((last $ take (x+1) evenFibs) +
                      (last $ take x evenFibs) -
                      8 + 6) `div` 4
  where x = length (takeWhile (<= n) evenFibs)

总结

这是一道好像比较简单的小题，但是其实做法还是让我觉得学到了与之相关的不少东西。