欧拉计划

欧拉计划是个知名的网站，在任何一种互联网搜索引擎，例如微软的bing，输入project euler能找到它。

以五百年才出现一位的大数学家欧拉冠名的计划，提供了一系列数学相关的计算机编程题。解答每一道题目，不仅需要数学分析，大多数情况下，还要通过计算机编程来完成。对于数学爱好者和程序员，解答欧拉计划列出的题目，对于数学+编程爱好者，是有趣的体验。

欧拉计划第二题

斐波那契数列中的每一项都是前两项的和。我们设初始值为0和1的话，那么第一项等于0 + 1，为1。以此类推。生成的斐波那契数列的前10项为：

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

考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。

分析

根据问题描述，不难发现偶数项的斐波那契数存在一种规律，即设一个斐波那契数所处的第i位置为 N（i），则i符合如下规则：

当i = 2时，得到偶数项 2。然后往下跳过2项，则第三项必为偶数项，以此类推。这个命题可以通过数学，证明出来。你可以自己试试看能不能推到出来？

算法

凭借上述分析，不难得出简单的一个算法。

1. 初始化斐波拉契数，0和1
2. 然后每次迭代，得出新的斐波拉契数，同时更新项所属的位置
3. 当所属位置正好落在规则上，那么就累加新得到的斐波拉契数
4. 当新斐波拉契数小于四百万时，回到步骤2；否则，输出累加值

代码

按照上述算法，用Perl一行搞定。

perl -E '($fib1, $fib2, $count, $timer, $sum) = (0, 1, 0, 2, 0); while ( ($nextFib = $fib1 + $fib2) < 4000000 ) { ($fib1, $fib2) = ($fib2, $nextFib); ++$count; $sum += ($timer == $count) ? $nextFib : 0; $timer += ($timer == $count) ? 3 : 0 } say $sum'

哇喔。只要你的电脑安装了Perl编程语言，拷贝上述命令，粘贴到终端或者命令行提示，回车运行，即可得到答案。

只要分析到位，算法弄清爽了，写代码实现就是水到渠成。

Tags：编程题

微信扫一扫：分享

微信里点“发现”，扫一下

二维码便可将本文分享至朋友圈。