HOME SUMMARY

Problem 2

1. Problem

Even Fibonacci numbers

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.

偶斐波那契数

斐波那契数列中的每一项都是前两项的和。由 1 和 2 开始生成的斐波那契数列的前 10 项为:

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

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

2. Solution

根据斐波那契数列公式 f(n+2) = f(n+1) + f(n) 从第 1 项求到第四百万项即可:

(named-let f ((i 1) (j 1) (sum 0))
  (cond
   ((> j 4000000) sum)
   ((cl-evenp j) (f j (+ i j) (+ sum j)))
   (t (f j (+ i j) sum))))
;; 4613732

由于奇奇得偶,奇偶得奇,偶偶得偶,容易观察得出以下规律:

1 1 2 3 5 8 13 21 34 55 89 144
a b c a b c  a  b  c  a  b   c

可见从第一项开始以 3 个数为 1 组,每组的最后一个数都是偶数,我们也可以如此实现:

(named-let f ((a 1) (b 1) (c 2) (sum 0))
  (cond
   ((> sum 4000000) sum)
   (t
    (setq a1 (+ b c)
          b1 (+ a1 c)
          c1 (+ a1 b1))
    (f a1 b1 c1 (+ sum c)))))
;; 4613732

进一步,我们可以推导出步长为 3 的斐波那契数列子列:

F(n) = F(n-1) + F(n-2)
     = F(n-2) + F(n-3) + F(n-2) = 2F(n-2) + F(n-3)
     = 2(F(n-3) + F(n-4)) + F(n-3) = 3F(n-3) + 2F(n-4)
     = 3F(n-3) + F(n-4) + F(n-5) + F(n-6)
     = 4F(n-3) + F(n-6)

G(n) = 4G(n-1) + G(n-2) G(1)=2 G(2)=8

根据这个新数列公式,有如下代码:

(named-let f ((a 0) (b 2) (sum 0))
  (cond
   ((> b 4000000) sum)
   (t (f b (+ (* b 4) a) (+ sum b)))))
;; 4613732